Алгоритмы и структуры данных на Kotlin: полный гайд для начинающих

Введение: зачем изучать алгоритмы и структуры данных на Kotlin?

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

Зачем это нужно новичку? Во-первых, знание базовых структур (списки, стеки, очереди, хеш-таблицы) помогает писать более эффективный и быстрый код. Во-вторых, алгоритмы — это основа для решения технических задач на собеседованиях. В-третьих, это просто интересно: вы начинаете видеть за кодом логику и математику.

В этой статье мы разберём ключевые алгоритмы и структуры данных на Kotlin с нуля. Все примеры будут простыми, понятными и готовыми к запуску. Поехали!

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

Массивы и списки

В Kotlin есть два основных типа коллекций: Array (фиксированный размер) и List (динамический). Для большинства задач удобнее использовать List.

fun main() {
    // Массив фиксированного размера
    val numbersArray = arrayOf(1, 2, 3, 4, 5)
    println("Массив: ${numbersArray.joinToString()}")

    // Изменяемый список
    val mutableList = mutableListOf(10, 20, 30)
    mutableList.add(40)
    println("Список после добавления: $mutableList")

    // Неизменяемый список
    val immutableList = listOf(100, 200, 300)
    println("Неизменяемый список: $immutableList")
}

Стек (Stack)

Стек работает по принципу LIFO (Last In, First Out) — последний пришёл, первый ушёл. В Kotlin нет встроенного класса Stack, но его легко реализовать с помощью MutableList.

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(1)
    stack.push(2)
    stack.push(3)

    println("Верхний элемент: ${stack.peek()}") // 3
    println("Извлекаем: ${stack.pop()}")        // 3
    println("Теперь верхний: ${stack.peek()}")  // 2
}

Очередь (Queue)

Очередь работает по принципу FIFO (First In, First Out) — первый пришёл, первый ушёл. В Kotlin для этого удобно использовать LinkedList из Java.

import java.util.LinkedList

class Queue<T> {
    private val elements = LinkedList<T>()

    fun enqueue(item: T) = elements.add(item)
    fun dequeue(): T? = elements.poll()
    fun peek(): T? = elements.peek()
    fun isEmpty() = elements.isEmpty()
    fun size() = elements.size
}

fun main() {
    val queue = Queue<String>()
    queue.enqueue("Первый")
    queue.enqueue("Второй")
    queue.enqueue("Третий")

    println("Обслуживаем: ${queue.dequeue()}") // Первый
    println("Следующий: ${queue.peek()}")      // Второй
}

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

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

Простой, но медленный алгоритм. Подходит для обучения, но не для реальных проектов.

fun bubbleSort(arr: MutableList<Int>) {
    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 list = mutableListOf(64, 34, 25, 12, 22, 11, 90)
    bubbleSort(list)
    println("Отсортировано пузырьком: $list")
}

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

Один из самых эффективных алгоритмов. Работает по принципу "разделяй и властвуй".

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

private fun partition(arr: MutableList<Int>, 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 list = mutableListOf(10, 7, 8, 9, 1, 5)
    quickSort(list, 0, list.size - 1)
    println("Быстрая сортировка: $list")
}

3. Алгоритмы поиска

Линейный поиск (Linear Search)

Самый простой способ найти элемент — пройтись по всему списку.

fun linearSearch(arr: List<Int>, target: Int): Int? {
    for ((index, value) in arr.withIndex()) {
        if (value == target) return index
    }
    return null
}

fun main() {
    val numbers = listOf(5, 3, 8, 1, 9, 2)
    val target = 8
    val result = linearSearch(numbers, target)
    println("Индекс числа $target: ${result ?: "не найден"}")
}

Бинарный поиск (Binary Search)

Работает только на отсортированных данных. Делит массив пополам на каждом шаге, что даёт скорость O(log n).

fun binarySearch(arr: List<Int>, target: Int): Int? {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left