Алгоритмы и структуры данных на Kotlin: практическое руководство

Алгоритмы и структуры данных на Kotlin: от теории к практике

Kotlin — современный, лаконичный и безопасный язык, который активно используется для разработки под Android, бэкенда и даже нативных приложений. Однако его мощь раскрывается полностью только при правильном применении алгоритмов и структур данных. В этой статье мы разберем ключевые концепции на практических примерах, которые помогут вам писать эффективный и поддерживаемый код.

1. Базовые структуры данных: списки, стеки и очереди

Начнем с фундамента. Kotlin предоставляет богатую стандартную библиотеку, но понимание того, как работают структуры данных «под капотом», критически важно.

Связный список (LinkedList)

Реализуем простой односвязный список вручную. Это поможет понять принципы работы с памятью и ссылками.

class Node<T>(var value: T, var next: Node<T>? = null)

class LinkedList<T> {
    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    fun add(value: T) {
        val node = Node(value)
        if (head == null) {
            head = node
            tail = node
        } else {
            tail?.next = node
            tail = node
        }
    }

    fun printAll() {
        var current = head
        while (current != null) {
            print("${current.value} ")
            current = current.next
        }
        println()
    }
}

// Использование
fun main() {
    val list = LinkedList<Int>()
    list.add(1)
    list.add(2)
    list.add(3)
    list.printAll() // Вывод: 1 2 3
}

Стек на основе массива

Стек работает по принципу LIFO (Last In, First Out). Реализуем его с помощью изменяемого списка Kotlin.

class Stack<T> {
    private val elements = mutableListOf<T>()

    fun push(item: T) = elements.add(item)
    fun pop(): T? = if (elements.isNotEmpty()) elements.removeAt(elements.size - 1) else null
    fun peek(): T? = elements.lastOrNull()
    fun isEmpty() = elements.isEmpty()
}

// Пример: проверка скобок
fun isBalanced(expression: String): Boolean {
    val stack = Stack<Char>()
    for (char in expression) {
        when (char) {
            '(', '{', '[' -> stack.push(char)
            ')' -> if (stack.pop() != '(') return false
            '}' -> if (stack.pop() != '{') return false
            ']' -> if (stack.pop() != '[') return false
        }
    }
    return stack.isEmpty()
}

fun main() {
    println(isBalanced("({[]})")) // true
    println(isBalanced("({[})"))  // false
}

2. Алгоритмы сортировки: от пузырька до быстрой

Сортировка — одна из самых изучаемых тем. Рассмотрим три классических алгоритма, которые легко реализовать на Kotlin.

Пузырьковая сортировка (Bubble Sort)

Простая, но неэффективная для больших массивов (O(n²)).

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

fun main() {
    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    bubbleSort(array)
    println(array.joinToString()) // 11, 12, 22, 25, 34, 64, 90
}

Быстрая сортировка (Quick Sort)

Один из самых быстрых алгоритмов в среднем случае (O(n log n)). Использует рекурсию и разделение массива.

fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

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

fun main() {
    val array = intArrayOf(10, 7, 8, 9, 1, 5)
    quickSort(array, 0, array.size - 1)
    println(array.joinToString()) // 1, 5, 7, 8, 9, 10
}

3. Деревья и хеш-таблицы: ключ к быстрому поиску

Эти структуры данных обеспечивают эффективный доступ к данным. Рассмотрим бинарное дерево поиска и простую хеш-таблицу.

Бинарное дерево поиска (BST)

Каждый узел имеет не более двух потомков. Левый потомок меньше родителя, правый — больше.

class TreeNode<T : Comparable<T>>(var value: T) {
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

class BinarySearchTree<T : Comparable<T>> {
    private var root: TreeNode<T>? = null

    fun insert(value: T) {
        root = insertRec(root, value)
    }

    private fun insertRec(node: TreeNode<T>?, value: T): TreeNode<T> {
        if (node == null) return TreeNode(value)
        if (value < node.value) node.left = insertRec(node.left, value)
        else if (value > node.value) node.right = insertRec(node.right, value)
        return node
    }

    fun search(value: T): Boolean {
        return searchRec(root, value)
    }

    private fun searchRec(node: TreeNode<T>?, value: T): Boolean {
        if (node == null) return false
        return when {
            value == node.value -> true
            value < node.value -> searchRec(node.left, value)
            else -> searchRec(node.right, value)
        }
    }

    fun inorder() {
        inorderRec(root)
        println()
    }

    private fun inorderRec(node: TreeNode<T>?) {
        if (node != null) {
            inorderRec(node.left)
            print("${node.value} ")
            inorderRec(node.right)
        }
    }
}

fun main() {
    val bst = BinarySearchTree<Int>()
    bst.insert(50)
    bst.insert(30)
    bst.insert(70)
    bst.insert(20)
    bst.insert(40)
    bst.inorder() // 20 30 40 50 70