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

Introduction aux algorithmes et structures de données en Kotlin

Kotlin est un langage de programmation moderne qui allie concision et puissance. L'étude des algorithmes et des structures de données en Kotlin ouvre la voie à l'écriture de code efficace et évolutif. Que vous développiez des applications Android, des services backend ou des programmes de bureau, la compréhension des structures et algorithmes de base est une compétence essentielle pour tout développeur professionnel.

Dans cet article, nous allons analyser les structures de données et algorithmes clés en Kotlin avec des exemples de code pratiques. Vous apprendrez à implémenter le tri, la recherche, le travail avec les listes, les piles, les files d'attente, les arbres et les graphes.

1. Structures de données de base en Kotlin

1.1. Tableaux et listes

En Kotlin, les tableaux sont représentés par le type Array, et les listes dynamiques par List et MutableList. Les listes sont la structure de données la plus couramment utilisée.

fun main() {    // Liste immuable    val list: List<Int> = listOf(1, 2, 3, 4, 5)        // Liste mutable    val mutableList: MutableList<Int> = mutableListOf(10, 20, 30)    mutableList.add(40)    mutableList.removeAt(0)        println(mutableList) // [20, 30, 40]}

1.2. Pile (Stack)

La pile fonctionne selon le principe LIFO (Last In, First Out). En Kotlin, on peut implémenter une pile à l'aide de ArrayDeque.

fun stackExample() {    val stack = ArrayDeque<String>()        stack.addLast("Premier")    stack.addLast("Deuxième")    stack.addLast("Troisième")        println(stack.removeLast()) // Troisième    println(stack.removeLast()) // Deuxième    println(stack.removeLast()) // Premier}

1.3. File d'attente (Queue)

La file d'attente fonctionne selon le principe FIFO (First In, First Out). L'implémentation utilise également 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. Liste chaînée (LinkedList)

Une liste chaînée est une séquence de nœuds, chacun contenant des données et une référence au nœud suivant. Implémentons une simple liste chaînée.

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. Algorithmes de tri en Kotlin

2.1. Tri à bulles (Bubble Sort)

Algorithme simple mais inefficace. Complexité 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. Tri rapide (Quick Sort)