Kotlin 算法与数据结构：实用指南

Kotlin 算法与数据结构：从理论到实践

Kotlin 是一种现代、简洁且安全的语言，广泛用于 Android 开发、后端甚至原生应用。然而，只有正确运用算法和数据结构，才能充分发挥其强大功能。在本文中，我们将通过实践示例剖析关键概念，帮助您编写高效且易于维护的代码。

1. 基础数据结构：列表、栈和队列

我们从基础开始。Kotlin 提供了丰富的标准库，但理解数据结构“底层”的工作原理至关重要。

链表 (LinkedList)

我们手动实现一个简单的单向链表。这有助于理解内存和引用的工作原理。

class Node<T>(var value: T, var next: Node<T>? = null)\n\nclass LinkedList<T> {\n    private var head: Node<T>? = null\n    private var tail: Node<T>? = null\n\n    fun add(value: T) {\n        val node = Node(value)\n        if (head == null) {\n            head = node\n            tail = node\n        } else {\n            tail?.next = node\n            tail = node\n        }\n    }\n\n    fun printAll() {\n        var current = head\n        while (current != null) {\n            print("${current.value} ")\n            current = current.next\n        }\n        println()\n    }\n}\n\n// 使用示例\nfun main() {\n    val list = LinkedList<Int>()\n    list.add(1)\n    list.add(2)\n    list.add(3)\n    list.printAll() // 输出：1 2 3\n}

基于数组的栈

栈遵循后进先出（LIFO）原则。我们使用 Kotlin 的可变列表来实现它。

class Stack<T> {\n    private val elements = mutableListOf<T>()\n\n    fun push(item: T) = elements.add(item)\n    fun pop(): T? = if (elements.isNotEmpty()) elements.removeAt(elements.size - 1) else null\n    fun peek(): T? = elements.lastOrNull()\n    fun isEmpty() = elements.isEmpty()\n}\n\n// 示例：括号匹配检查\nfun isBalanced(expression: String): Boolean {\n    val stack = Stack<Char>()\n    for (char in expression) {\n        when (char) {\n            '(', '{', '[' -> stack.push(char)\n            ')' -> if (stack.pop() != '(') return false\n            '}' -> if (stack.pop() != '{') return false\n            ']' -> if (stack.pop() != '[') return false\n        }\n    }\n    return stack.isEmpty()\n}\n\nfun main() {\n    println(isBalanced("({[]})")) // true\n    println(isBalanced("({[})"))  // false\n}

2. 排序算法：从冒泡排序到快速排序

排序是最常研究的主题之一。我们来看三种经典算法，它们很容易用 Kotlin 实现。

冒泡排序 (Bubble Sort)

简单，但对大型数组效率较低 (O(n²))。

fun bubbleSort(arr: IntArray) {\n    val n = arr.size\n    for (i in 0 until n - 1) {\n        for (j in 0 until n - i - 1) {\n            if (arr[j] > arr[j + 1]) {\n                val temp = arr[j]\n                arr[j] = arr[j + 1]\n                arr[j + 1] = temp\n            }\n        }\n    }\n}\n\nfun main() {\n    val array = intArrayOf(64, 34, 25, 12, 22, 11, 90)\n    bubbleSort(array)\n    println(array.joinToString()) // 11, 12, 22, 25, 34, 64, 90\n}

快速排序 (Quick Sort)

平均情况下最快的算法之一 (O(n log n))。使用递归和数组分区。

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