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

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

Kotlin est un langage multi-paradigme moderne, activement utilisé pour le développement Android, le backend et même les applications de bureau. Cependant, pour écrire un code efficace et évolutif, il ne suffit pas de connaître la syntaxe — il faut comprendre comment fonctionnent les algorithmes et les structures de données. Dans cet article, nous analyserons les concepts clés en pratique avec des exemples en Kotlin. Vous apprendrez à implémenter des structures et algorithmes de base, ainsi qu'à utiliser les fonctionnalités intégrées du langage pour optimiser le code.

1. Structures de données de base : tableaux et listes

En Kotlin, les tableaux sont représentés par le type Array<T>, et les listes dynamiques par List<T> (immuable) et MutableList<T> (muable). Cependant, dans les tâches réelles, il est souvent nécessaire d'implémenter sa propre liste chaînée pour comprendre les principes de fonctionnement.

Liste chaînée simple en Kotlin

Une liste chaînée est composée de nœuds, chacun contenant des données et une référence au nœud suivant. Voici une implémentation de base :

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(1)    list.add(2)    list.add(3)    list.printAll() // Affichage : 1 2 3}

Cette implémentation illustre les opérations de base : ajout à la fin et parcours. Dans les projets réels, utilisez les collections intégrées de Kotlin, mais comprendre le fonctionnement interne permet d'éviter des erreurs liées à la mémoire et aux performances.

2. Algorithmes de tri en Kotlin

Le tri est l'une des opérations les plus courantes. Kotlin dispose d'une fonction intégrée sorted(), mais pour une compréhension approfondie, il est utile d'implémenter des algorithmes classiques.

Tri rapide (QuickSort)

QuickSort est l'un des algorithmes les plus efficaces avec une complexité moyenne de O(n log n). Implémentation en Kotlin utilisant la récursivité :

fun quickSort(arr: IntArray, low: Int, high: Int) {    if (low < high) {        val pivotIndex = partition(arr, low, high)        quickSort(arr, low, pivotIndex - 1)        quickSort(arr, pivotIndex + 1, high)    }}

fun partition(arr: IntArray, low: Int, high: Int): Int {    val pivot = arr[high]    var i = low - 1    for (j in low until high) {        if (arr[j] <= pivot) {            i++            arr[i] = arr[j].also { arr[j] = arr[i] }        }    }    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }    return i + 1}

fun main() {    val array = intArrayOf(10, 7, 8, 9, 1, 5)    quickSort(array, 0, array.size - 1)    println(array.joinToString()) // Affichage : 1, 5, 7, 8, 9, 10}

Notez l'utilisation de also pour l'échange de valeurs — c'est une manière idiomatique en Kotlin. L'algorithme est stable et fonctionne in-place, ce qui économise de la mémoire.

3. Recherche : binaire et linéaire

La recherche d'éléments dans les structures de données est la deuxième tâche la plus importante. Examinons deux approches.

Recherche linéaire

Algorithme simple mais lent (O(n)). Convient aux données non triées :

fun linearSearch(arr: IntArray, target: Int): Int {    for (i in arr.indices) {        if (arr[i] == target) return i    }    retu