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

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

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

Материал будет полезен как новичкам, так и разработчикам, которые хотят систематизировать знания. Все примеры можно запустить в среде IntelliJ IDEA или онлайн-компиляторе.

1. Базовые структуры данных в Kotlin

Стандартная библиотека Kotlin предоставляет богатый набор структур данных. Рассмотрим основные из них.

Списки (List, MutableList)

Списки — упорядоченные коллекции элементов. Kotlin разделяет изменяемые и неизменяемые списки.

fun main() {
    // Неизменяемый список
    val fruits = listOf("Яблоко", "Банан", "Апельсин")
    
    // Изменяемый список
    val numbers = mutableListOf(1, 2, 3)
    numbers.add(4)
    numbers.removeAt(1)
    
    println(fruits[0]) // Яблоко
    println(numbers)   // [1, 3, 4]
}

Множества (Set, MutableSet)

Множества хранят уникальные элементы. Полезны для проверки дубликатов.

fun main() {
    val uniqueNumbers = setOf(1, 2, 2, 3, 3, 3)
    println(uniqueNumbers) // [1, 2, 3]
    
    val mutableSet = mutableSetOf("a", "b")
    mutableSet.add("c")
    println(mutableSet.contains("b")) // true
}

Словари (Map, MutableMap)

Словари хранят пары ключ-значение. Аналог хеш-таблицы.

fun main() {
    val capitals = mapOf(
        "Россия" to "Москва",
        "США" to "Вашингтон",
        "Франция" to "Париж"
    )
    
    println(capitals["Россия"]) // Москва
    
    // Изменяемый словарь
    val scores = mutableMapOf("Иван" to 85)
    scores["Мария"] = 92
    scores["Иван"] = 90
}

2. Реализация классических структур данных

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

Стек (Stack)

Стек работает по принципу LIFO (Last In, First Out). Используется в парсерах, отмене действий и обходе графов.

class Stack<T> {
    private val elements = mutableListOf<T>()
    
    fun push(item: T) = elements.add(item)
    fun pop(): T? = if (isEmpty()) null else elements.removeAt(elements.size - 1)
    fun peek(): T? = elements.lastOrNull()
    fun isEmpty() = elements.isEmpty()
    fun size() = elements.size
}

fun main() {
    val stack = Stack<Int>()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    
    println(stack.pop())   // 30
    println(stack.peek())  // 20
    println(stack.size())  // 2
}

Очередь (Queue)

Очередь работает по принципу FIFO (First In, First Out). Используется в системах обработки задач.

class Queue<T> {
    private val elements = mutableListOf<T>()
    
    fun enqueue(item: T) = elements.add(item)
    fun dequeue(): T? = if (isEmpty()) null else elements.removeAt(0)
    fun peek(): T? = elements.firstOrNull()
    fun isEmpty() = elements.isEmpty()
}

fun main() {
    val queue = Queue<String>()
    queue.enqueue("Задача 1")
    queue.enqueue("Задача 2")
    queue.enqueue("Задача 3")
    
    println(queue.dequeue()) // Задача 1
    println(queue.peek())    // Задача 2
}

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

Сортировка — базовая операция. Разберём три популярных алгоритма.

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

Один из самых эффективных алгоритмов со средней сложностью 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++
            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 numbers = intArrayOf(10, 7, 8, 9, 1, 5)
    quickSort(numbers, 0, numbers.size - 1)
    println(numbers.joinToString()) // 1, 5, 7, 8, 9, 10
}

Сортировка слиянием (MergeSort)

Стабильный алгоритм с гарантированной сложностью O(n log n).

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr
    
    val mid = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until mid))
    val right = mergeSort(arr.sliceArray(mid until arr.size))
    
    return merge(left, right)
}

fun merge(left: IntArray, right: IntArray): IntArray {
    var i = 0; var j = 0; var k = 0
    val result = IntArray(left.size + right.size)
    
    while (i < left.size && j < right.size) {
        result[k++] = if (left[i] <= right[j]) left[i++] else right[j++]
    }
    while (i < left.size) result[k++] = left[i++]
    while (j < right.size) result[k++] = right[j++]
    
    return result
}

fun main() {
    val numbers = intArrayOf(38, 27, 43, 3, 9, 82, 10)
    val sorted = mergeSort(numbers)
    println(sorted.joinToString()) // 3, 9, 10, 27, 38, 43, 82
}

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

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

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

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right