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 de programmation moderne qui combine la concision de Python et la puissance de Java. Pour écrire du code efficace, il est nécessaire de comprendre comment fonctionnent les algorithmes et les structures de données. Dans cet article, nous allons analyser les concepts clés avec des exemples en Kotlin qui vous aideront à écrire des programmes rapides et fiables.

Ce contenu sera utile aussi bien aux débutants qu'aux développeurs souhaitant systématiser leurs connaissances. Tous les exemples peuvent être exécutés dans l'environnement IntelliJ IDEA ou un compilateur en ligne.

1. Structures de données de base en Kotlin

La bibliothèque standard de Kotlin fournit un ensemble riche de structures de données. Examinons les principales.

Listes (List, MutableList)

Les listes sont des collections ordonnées d'éléments. Kotlin distingue les listes modifiables et non modifiables.

fun main() {    // Liste non modifiable    val fruits = listOf("Pomme", "Banane", "Orange")        // Liste modifiable    val numbers = mutableListOf(1, 2, 3)    numbers.add(4)    numbers.removeAt(1)        println(fruits[0]) // Pomme    println(numbers)   // [1, 3, 4]}

Ensembles (Set, MutableSet)

Les ensembles stockent des éléments uniques. Utiles pour vérifier les doublons.

fun main() {    val uniqueNumbers = setOf(1, 2, 2, 3, 3, 3)    println(uniqueNumbers) // [1, 2, 3]        val mutableSet = mutableSetOf(\"a\", \"b\")    mutableSet.add(\"c\")    println(mutableSet.contains(\"b\")) // true}

Dictionnaires (Map, MutableMap)

Les dictionnaires stockent des paires clé-valeur. Équivalent d'une table de hachage.

fun main() {    val capitals = mapOf(        \"Russie\" to \"Moscou\",        \"États-Unis\" to \"Washington\",        \"France\" to \"Paris\"    )        println(capitals[\"Russie\"]) // Moscou        // Dictionnaire modifiable    val scores = mutableMapOf(\"Ivan\" to 85)    scores[\"Marie\"] = 92    scores[\"Ivan\"] = 90}

2. Implémentation de structures de données classiques

Parfois, les structures standard ne suffisent pas. Voyons comment implémenter manuellement une pile et une file d'attente.

Pile (Stack)

La pile fonctionne selon le principe LIFO (Last In, First Out). Utilisée dans les analyseurs syntaxiques, l'annulation d'actions et le parcours de graphes.

class Stack<T> {    private val elements = mutableListOf<T>()        fun push(item: T) = elements.add(item)    fun pop(): T? = if (isEmpty()) null else elements.removeAt(elements.size - 1)    fun peek(): T? = elements.lastOrNull()    fun isEmpty() = elements.isEmpty()    fun size() = elements.size}

fun main() {    val stack = Stack<Int>()    stack.push(10)    stack.push(20)    stack.push(30)        println(stack.pop())   // 30    println(stack.peek())  // 20    println(stack.size())  // 2}

File d'attente (Queue)

La file d'attente fonctionne selon le principe FIFO (First In, First Out). Utilisée dans les systèmes de traitement de tâches.

class Queue<T> {    private val elements = mutableListOf<T>()        fun enqueue(item: T) = elements.add(item)    fun dequeue(): T? = if (isEmpty()) null else elements.removeAt(0)    fun peek(): T? = elements.firstOrNull()    fun isEmpty() = elements.isEmpty()}

fun main() {    val queue = Queue<String>()    queue.enqueue(\"Tâche 1\")    queue.enqueue(\"Tâche 2\")    queue.enqueue(\"Tâche 3\")        println(queue.dequeue()) // Tâche 1    println(queue.peek())    // Tâche 2}

3. Algorithmes de tri en Kotlin

Le tri est une opération de base. Analysons trois algorithmes populaires.

Tri rapide (QuickSort)

L'un des algorithmes les plus efficaces avec une complexité moyenne de O(n log n).

fun quickSort(arr: IntArray, low: Int, high: Int) {    if (low < high) {        val pi = partition(arr, low, high)        quickSort(arr, low, pi - 1)        quick