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

Введение в алгоритмы и структуры данных на Kotlin

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

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

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

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

В Kotlin массивы представлены типом Array, а динамические списки — List и MutableList. Списки — наиболее часто используемая структура данных.

fun main() {
    // Неизменяемый список
    val list: List<Int> = listOf(1, 2, 3, 4, 5)
    
    // Изменяемый список
    val mutableList: MutableList<Int> = mutableListOf(10, 20, 30)
    mutableList.add(40)
    mutableList.removeAt(0)
    
    println(mutableList) // [20, 30, 40]
}

1.2. Стек (Stack)

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

fun stackExample() {
    val stack = ArrayDeque<String>()
    
    stack.addLast("Первый")
    stack.addLast("Второй")
    stack.addLast("Третий")
    
    println(stack.removeLast()) // Третий
    println(stack.removeLast()) // Второй
    println(stack.removeLast()) // Первый
}

1.3. Очередь (Queue)

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

fun queueExample() {
    val queue = ArrayDeque<Int>()
    
    queue.addLast(1)
    queue.addLast(2)
    queue.addLast(3)
    
    println(queue.removeFirst()) // 1
    println(queue.removeFirst()) // 2
    println(queue.removeFirst()) // 3
}

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

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

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(10)
    list.add(20)
    list.add(30)
    list.printAll() // 10 20 30
}

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

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

Простой, но неэффективный алгоритм. Сложность O(n²).

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 numbers = mutableListOf(64, 34, 25, 12, 22, 11, 90)
    bubbleSort(numbers)
    println(numbers) // [11, 12, 22, 25, 34, 64, 90]
}

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

Один из самых эффективных алгоритмов. Средняя сложность O(n log n).

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)
    }
}

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 numbers = mutableListOf(10, 7, 8, 9, 1, 5)
    quickSort(numbers, 0, numbers.size - 1)
    println(numbers) // [1, 5, 7, 8, 9, 10]
}

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

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

Проходит по всем элементам. Сложность O(n).

fun linearSearch(arr: List<Int>, target: Int): Int? {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return null
}

fun main() {
    val numbers = listOf(2, 5, 8, 12, 16, 23, 38)
    val result = linearSearch(numbers, 12)
    println("Индекс: $result") // Индекс: 3
}

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

Работает только на отсортированных массивах. Сложность 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 = mid + 1
            else -> right = mid