Algoritmos e Estruturas de Dados em Kotlin: Guia Prático

Algoritmos e Estruturas de Dados em Kotlin: da Teoria à Prática

Kotlin é uma linguagem moderna, concisa e segura, amplamente utilizada para desenvolvimento Android, backend e até aplicações nativas. No entanto, seu poder é totalmente revelado apenas com a aplicação correta de algoritmos e estruturas de dados. Neste artigo, exploraremos conceitos-chave com exemplos práticos que o ajudarão a escrever código eficiente e sustentável.

1. Estruturas de Dados Básicas: Listas, Pilhas e Filas

Vamos começar pelo fundamento. Kotlin oferece uma biblioteca padrão rica, mas entender como as estruturas de dados funcionam "por baixo dos panos" é crucial.

Lista Encadeada (LinkedList)

Vamos implementar uma lista simplesmente encadeada manualmente. Isso ajudará a entender os princípios de gerenciamento de memória e referências.

class Node<T>(var value: T, var next: Node<T>? = null)\n\nclass LinkedList<T> {\n    private var head: Node<T>? = null\n    private var tail: Node<T>? = null\n\n    fun add(value: T) {\n        val node = Node(value)\n        if (head == null) {\n            head = node\n            tail = node\n        } else {\n            tail?.next = node\n            tail = node\n        }\n    }\n\n    fun printAll() {\n        var current = head\n        while (current != null) {\n            print("${current.value} ")\n            current = current.next\n        }\n        println()\n    }\n}\n\n// Uso\nfun main() {\n    val list = LinkedList<Int>()\n    list.add(1)\n    list.add(2)\n    list.add(3)\n    list.printAll() // Saída: 1 2 3\n}

Pilha Baseada em Array

A pilha opera no princípio LIFO (Last In, First Out). Vamos implementá-la usando uma lista mutável do Kotlin.

class Stack<T> {\n    private val elements = mutableListOf<T>()\n\n    fun push(item: T) = elements.add(item)\n    fun pop(): T? = if (elements.isNotEmpty()) elements.removeAt(elements.size - 1) else null\n    fun peek(): T? = elements.lastOrNull()\n    fun isEmpty() = elements.isEmpty()\n}\n\n// Exemplo: verificação de parênteses\nfun isBalanced(expression: String): Boolean {\n    val stack = Stack<Char>()\n    for (char in expression) {\n        when (char) {\n            '(', '{', '[' -> stack.push(char)\n            ')' -> if (stack.pop() != '(') return false\n            '}' -> if (stack.pop() != '{') return false\n            ']' -> if (stack.pop() != '[') return false\n        }\n    }\n    return stack.isEmpty()\n}\n\nfun main() {\n    println(isBalanced("({[]})")) // true\n    println(isBalanced("({[})"))  // false\n}

2. Algoritmos de Ordenação: Da Bolha ao Quick Sort

Ordenação é um dos tópicos mais estudados. Vamos analisar três algoritmos clássicos que são fáceis de implementar em Kotlin.

Bubble Sort (Ordenação por Bolha)

Simples, mas ineficiente para arrays grandes (O(n²)).

fun bubbleSort(arr: IntArray) {\n    val n = arr.size\n    for (i in 0 until n - 1) {\n        for (j in 0 until n - i - 1) {\n            if (arr[j] > arr[j + 1]) {\n                val temp = arr[j]\n                arr[j] = arr[j + 1]\n                arr[j + 1] = temp\n            }\n        }\n    }\n}\n\nfun main() {\n    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90)\n    bubbleSort(array)\n    println(array.joinToString()) // 11, 12, 22, 25, 34, 64, 90\n}

Quick Sort (Ordenação Rápida)

Um dos algoritmos mais rápidos no caso médio (O(n log n)). Usa recursão e particionamento do array.

fun quickSort(arr: IntArray, low: Int, high: Int) {\n    if (low < high) {\n        val pi = partition(arr, low, high)\n        quickSort(arr, low, pi - 1)\n        quickSort(arr, pi + 1, high)\n    }\n}\n\nfun partition(arr: IntArray, low: Int, high: Int): Int {\n    val pivot = arr[high]\n    var i = low - 1\n    for (j in low until high) {\n