Algorithmen und Datenstrukturen in Kotlin: Ein praktischer Leitfaden

Algorithmen und Datenstrukturen in Kotlin: Von der Theorie zur Praxis

Kotlin ist eine moderne, prägnante und sichere Sprache, die aktiv für die Entwicklung von Android-Apps, Backend und sogar nativen Anwendungen eingesetzt wird. Ihre volle Stärke entfaltet sich jedoch erst bei der richtigen Anwendung von Algorithmen und Datenstrukturen. In diesem Artikel behandeln wir die wichtigsten Konzepte anhand praktischer Beispiele, die Ihnen helfen, effizienten und wartbaren Code zu schreiben.

1. Grundlegende Datenstrukturen: Listen, Stapel und Warteschlangen

Beginnen wir mit den Grundlagen. Kotlin bietet eine umfangreiche Standardbibliothek, aber das Verständnis der Funktionsweise von Datenstrukturen „unter der Haube“ ist entscheidend.

Verkettete Liste (LinkedList)

Wir implementieren manuell eine einfache einfach verkettete Liste. Dies hilft, die Prinzipien der Arbeit mit Speicher und Referenzen zu verstehen.

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// Verwendung\nfun main() {\n    val list = LinkedList<Int>()\n    list.add(1)\n    list.add(2)\n    list.add(3)\n    list.printAll() // Ausgabe: 1 2 3\n}

Stapel basierend auf einem Array

Ein Stapel arbeitet nach dem LIFO-Prinzip (Last In, First Out). Wir implementieren ihn mit einer veränderbaren Kotlin-Liste.

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// Beispiel: Klammerprüfung\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. Sortieralgorithmen: Von Bubble Sort zu Quick Sort

Sortierung ist eines der am häufigsten behandelten Themen. Wir betrachten drei klassische Algorithmen, die sich leicht in Kotlin implementieren lassen.

Bubble Sort

Einfach, aber für große Arrays ineffizient (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

Einer der schnellsten Algorithmen im Durchschnittsfall (O(n log n)). Verwendet Rekursion und Array-Aufteilung.

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