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（后进先出）原则。在 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（先进先出）原则。其实现同样使用 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)