Algorithmes et structures de données en Kotlin : guide pratique

Algorithmes et structures de données en Kotlin : de la théorie à la pratique

Kotlin est un langage moderne, concis et sûr, activement utilisé pour le développement Android, le backend et même les applications natives. Cependant, sa puissance se révèle pleinement seulement avec une application correcte des algorithmes et des structures de données. Dans cet article, nous analyserons les concepts clés avec des exemples pratiques qui vous aideront à écrire un code efficace et maintenable.

1. Structures de données de base : listes, piles et files

Commençons par les fondamentaux. Kotlin fournit une riche bibliothèque standard, mais comprendre comment fonctionnent les structures de données « sous le capot » est crucial.

Liste chaînée (LinkedList)

Implémentons une simple liste chaînée manuellement. Cela aidera à comprendre les principes de gestion de la mémoire et des références.

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

Pile basée sur un tableau

La pile fonctionne selon le principe LIFO (Last In, First Out). Implémentons-la avec une liste mutable de 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// Exemple : vérification des parenthèses\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. Algorithmes de tri : du bulle au rapide

Le tri est l’un des sujets les plus étudiés. Examinons trois algorithmes classiques faciles à implémenter en Kotlin.

Tri à bulles (Bubble Sort)

Simple, mais inefficace pour les grands tableaux (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}

Tri rapide (Quick Sort)

L’un des algorithmes les plus rapides en moyenne (O(n log n)). Utilise la récursion et le partitionnement du tableau.

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