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

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

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

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

В Kotlin массивы представлены типом Array<T>, а динамические списки — List<T> (неизменяемый) и MutableList<T> (изменяемый). Однако в реальных задачах часто требуется реализовать собственный связный список для понимания принципов работы.

Односвязный список на Kotlin

Связный список состоит из узлов, каждый из которых содержит данные и ссылку на следующий узел. Рассмотрим базовую реализацию:

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

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

    fun add(value: T) {
        val newNode = Node(value)
        if (head == null) {
            head = newNode
        } else {
            var current = head
            while (current?.next != null) {
                current = current.next
            }
            current?.next = newNode
        }
    }

    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
}

Эта реализация демонстрирует базовые операции: добавление в конец и обход. В реальных проектах используйте встроенные коллекции Kotlin, но понимание внутреннего устройства помогает избегать ошибок при работе с памятью и производительностью.

2. Алгоритмы сортировки на Kotlin

Сортировка — одна из самых частых операций. В Kotlin есть встроенная функция sorted(), но для глубокого понимания полезно реализовать классические алгоритмы.

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

QuickSort — один из самых эффективных алгоритмов со средней сложностью O(n log n). Реализация на Kotlin с использованием рекурсии:

fun quickSort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 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++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    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
}

Обратите внимание на использование also для обмена значений — это идиоматичный способ в Kotlin. Алгоритм стабилен и работает in-place, что экономит память.

3. Поиск: бинарный и линейный

Поиск элементов в структурах данных — вторая по важности задача. Рассмотрим два подхода.

Линейный поиск

Простой, но медленный алгоритм (O(n)). Подходит для несортированных данных:

fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return -1
}

Бинарный поиск

Работает только на отсортированных массивах, но за O(log n). Реализация на Kotlin с использованием рекурсии:

fun binarySearch(arr: IntArray, target: Int, left: Int, right: Int): Int {
    if (left > right) return -1
    val mid = (left + right) / 2
    return when {
        arr[mid] == target -> mid
        arr[mid] < target -> binarySearch(arr, target, mid + 1, right)
        else -> binarySearch(arr, target, left, mid - 1)
    }
}

fun main() {
    val sortedArray = intArrayOf(1, 3, 5, 7, 9, 11)
    val index = binarySearch(sortedArray, 7, 0, sortedArray.size - 1)
    println("Индекс элемента: $index") // Вывод: 3
}

В Kotlin также есть встроенная функция binarySearch() для списков, но ручная реализация помогает понять механизм деления пополам.

4. Деревья и хеш-таблицы

Двоичные деревья поиска (BST) и хеш-таблицы — основа многих сложных структур данных, таких как HashMap в стандартной библиотеке Kotlin.

Двоичное дерево поиска (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)
        when {
            value < node.value -> node.left = insertRec(node.left, value)
            value > node.value -> node.right = insertRec(node.right, value)
        }
        return node
    }

    fun contains(value: T): Boolean {
        return containsRec(root, value)
    }

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