Liste Chaînée

Les listes chaînées sont très utilisés en algorithmie lorsque l'on a uniquement besoin de parcourir une suite d'éléments et que l'on souhaite pouvoir supprimer ou ajouter un élément quelconque de cette liste en temps constant.

Pour réussir à supprimer/ajouter un élément en temps constant on va découper la liste en éléments indépendants, appelés maillons, collés les uns aux autres.

Maillon

Commençons par définir un Maillon :

structure Maillon<Type>:
    attributs:
        valeur: Type

        suivant: Maillon ← ∅
        précédent: Maillon ← ∅

Chaque maillon contient :

• sa valeur
• le maillon précédent de la chaîne
• le maillon suivant de la chaîne

Un maillon est une liste chaînée de 1 élément :

M ← Maillon {valeur: 1}

L ← M

Chaîne de maillons

Si on veut ajouter un maillon à la chaîne, on le peut le rajouter avant ou après l'élément comme le montre l'exemple suivant qui crée une chaîne de deux maillons :

M ← Maillon {valeur: 1}

# ajout d'un maillon après M
M2 ← Maillon {valeur: 3}
M2.précédent  ← M
M.suivant  ← M2

On peut même insérer un élément :

# insert d'un élément après M

M3 ← Maillon {valeur: 2}

M3.précédent ← M
M3.suivant ← M.suivant

M.suivant ← M3

À la fin de l'exemple on a une liste chaînée commençant au maillon M et constitué de 3 maillons.

De la remarque précédente on peut en déduire l'algorithme permettant de déterminer le nombre de maillons (ie la longueur) après un maillon donné :

algorithme taille(L: Maillon<T>) → entier:
    t ← 0
    tant que L ≠ ∅:
        t ← t + 1
        L ← L.suivant
    rendre t

Structure

On a coutume de définir la liste chaînée via un type récursif :

On peut écrire cette structure en ajoutant juste deux méthodes à notre maillon :

structure Maillon<Type>:
    attributs:
        valeur: Type

        suivant: Maillon ← ∅
        précédent: Maillon ← ∅
    méthodes:
        fonction append(L: Maillon<Type>) → ∅:  # ajoute L après self
            si L ≠ ∅: 
                L.précédent ← self
            self.suivant ← L

        fonction pop() → Maillon<Type>:  # supprime self de la liste 

            L ← self.suivant 

            self.suivant ← ∅ 
            si L ≠ ∅:
                L.précédent ← ∅

            rendre L

algorithme concatène(L1: Maillon<T>, L2: Maillon<T>) → Maillon<T>:
    si L1 == ∅:
        rendre L2
    rendre L1.append(concatène(L1.suivant, L2))

complexité

Le principal intérêt des liste chaînée est :

Ce qui en fait une structure très malléable. En revanche ceci à un coût :

Utilisation

On utilise les listes chaînées lorsque l'on doit très souvent insérer ou supprimer des éléments à l'intérieur d'une liste ou lorsque l'on construit une liste par étapes.

Stockage sur disque

Les listes chaînées sont utilisées pour stocker des fichiers sur un disque physique.

Algorithmes récursifs

C'est cette dernière utilisation fait que cette structure est plébiscité par les approches récursives où l'on construit petit à petit nos listes. Voyons ça avec quelques exercices qui reprennent avec des listes chaînées des exercices que l'on a déjà vu avec des tableaux, vous verrez que les algorithmes sont de complexité linéaire ce qui n'était pas le cas avec des tableaux.

algorithme maximum(L: Maillon<entier>) → entier:
    si L.suivant == ∅:
        rendre L.valeur
    rendre max(L.valeur, maximum(L.suivant))

algorithme supprime(L: Maillon<T>, v: T) → Maillon<T>:
    si L == ∅:
        rendre ∅
    si L.valeur == v:
        rendre supprime(L.suivant, v)
    rendre L.append(supprime(L.suivant, v))

algorithme retourne(L: Maillon<T>) → Maillon<T>:
    si L == ∅:
        rendre ∅
    L2 ← L.pop()
    rendre concaténation(retourne(L2), L)

algorithme retourne(L: Maillon<T>, acc: Maillon<T>) → Maillon<T>:
    si L == ∅:
        rendre acc
    L2 ← L.pop()
    L.append(acc)
    rendre retourne(L2, L)

retourne([1, 2, 3], ∅)  = 
retourne([2, 3], [1])   =
retourne([3], [2, 1])   =
retourne([], [3, 2, 1]) = [3, 2, 1]