04 — Listes et Listes Chaînées : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~55 min

---

Table des matières

1. Introduction
2. Liste simplement chaînée
3. Sentinelles
4. Liste doublement chaînée
5. Liste circulaire
6. Skip list
7. Applications réelles
8. Tableaux vs listes chaînées
9. Implémentation multi-langages
10. Résumé

---

1. Introduction

Les listes chaînées (linked lists) sont la famille de structures de données fondée sur les nœuds et les références. Chaque élément est un nœud contenant une valeur et un ou plusieurs pointeurs vers d'autres nœuds. Contrairement au tableau (bloc contigu), les nœuds peuvent être dispersés en mémoire.

Diagramme en cours de génération...

Rappel (chapitre 03) : l'intérêt est l'insertion/suppression O(1) avec nœud en main, au prix d'un accès O(n).

---

2. Liste simplement chaînée

2.1 Définition

Nœud = { valeur, suivant }. La liste garde une référence tete.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None

class ListeSimple:
    def __init__(self):
        self.tete = None
        self.taille = 0

2.2 Opérations fondamentales

2.3 Code des opérations

def add_first(self, x):
    n = Noeud(x)
    n.suivant = self.tete
    self.tete = n
    self.taille += 1

def add_last(self, x):
    n = Noeud(x)
    if self.tete is None:
        self.tete = n
        return
    cur = self.tete
    while cur.suivant:
        cur = cur.suivant
    cur.suivant = n
    self.taille += 1

def remove_first(self):
    if self.tete is None:
        raise IndexError
    self.tete = self.tete.suivant
    self.taille -= 1

def get(self, i):
    if i >= self.taille:
        raise IndexError
    cur = self.tete
    for _ in range(i):
        cur = cur.suivant
    return cur.valeur

2.4 Cas particulier : la suppression est asymétrique

Dans une liste simplement chaînée, supprimer le nœud cur exige de connaître son prédécesseur (pour relier pred.suivant = cur.suivant). Or on ne peut pas remonter. Deux options :

1. Parcourir depuis la tête jusqu'au prédécesseur : O(n).
2. Astuce de copie : copier cur.suivant.valeur dans cur, puis relier cur.suivant = cur.suivant.suivant — O(1) mais invalide si cur est le dernier nœud, et casse l'identité des nœuds (problème si les nœuds sont référencés ailleurs).

C'est la raison d'être de la liste doublement chaînée et des sentinelles.

---

3. Sentinelles

3.1 Problème des cas limites

Sans sentinelle, chaque insertion/suppression doit gérer : liste vide, premier nœud, dernier nœud. Le code est pollué de if self.tete is None.

3.2 Solution : nœud sentinelle

Une sentinelle (nœud fantôme) ne contient pas de donnée mais unifie les cas limites.

class ListeSent:
    def __init__(self):
        self.sentinelle = Noeud(None)   # tête fantôme
        self.taille = 0

• La sentinelle reste toujours le premier nœud ; la « vraie » tête est sentinelle.suivant.
• Insertion/suppression après un nœud donné devient uniforme : pas de cas vide.

def inserer_apres(self, noeud, x):
    n = Noeud(x)
    n.suivant = noeud.suivant
    noeud.suivant = n
    self.taille += 1

def add_first(self, x):
    self.inserer_apres(self.sentinelle, x)

3.3 Bénéfices

• Code plus simple et sans bug de cas limite.
• Permet la double chaînée circulaire avec sentinelle : chaque nœud a toujours un prédécesseur et un successeur → suppression O(1) sans cas spéciaux.
• Utilisé dans les bibliothèques réelles (ex. std::list en pratique avec nœud-sentinelle).

---

4. Liste doublement chaînée

4.1 Définition

Nœud = { valeur, precedent, suivant }.

class NoeudDouble:
    def __init__(self, valeur):
        self.valeur = valeur
        self.precedent = None
        self.suivant = None

Diagramme en cours de génération...

4.2 Opérations en O(1)

4.3 Suppression O(1) — le cœur de la valeur ajoutée

def retirer(self, noeud):
    if noeud.precedent:
        noeud.precedent.suivant = noeud.suivant
    else:
        self.tete = noeud.suivant
    if noeud.suivant:
        noeud.suivant.precedent = noeud.precedent
    else:
        self.queue = noeud.precedent
    self.taille -= 1

Avec une sentinelle circulaire, la gestion de tete/queue disparaît : chaque nœud a un prédécesseur/successeur non nul.

4.4 Double chaînée circulaire avec sentinelle

class ListeDoubleSent:
    def __init__(self):
        self.sentinelle = NoeudDouble(None)
        self.sentinelle.suivant = self.sentinelle
        self.sentinelle.precedent = self.sentinelle
        self.taille = 0

    def inserer_apres(self, noeud, x):
        n = NoeudDouble(x)
        n.suivant = noeud.suivant
        n.precedent = noeud
        noeud.suivant.precedent = n
        noeud.suivant = n
        self.taille += 1

    def retirer(self, noeud):
        noeud.precedent.suivant = noeud.suivant
        noeud.suivant.precedent = noeud.precedent
        self.taille -= 1

---

5. Liste circulaire

5.1 Définition

Le dernier nœud pointe vers la tête (ou la sentinelle). Utile pour les parcours en boucle (rounds).

Diagramme en cours de génération...

5.2 Applications

• Round-robin : partage du temps CPU, serveurs de charge.
• Tours de jeu (cartes, tournois).
• File circulaire : structure FIFO sur tableau circulaire (chapitre 05).
• Mémoire circulaire : buffers (audio, réseau).

5.3 File circulaire sur tableau

On réutilise un tableau avec deux indices tete et queue modulo la capacité :

class FileCirculaire:
    def __init__(self, capacite):
        self.data = [None] * capacite
        self.tete = 0
        self.taille = 0

    def enfiler(self, x):
        if self.taille == len(self.data):
            raise OverflowError("file pleine")
        pos = (self.tete + self.taille) % len(self.data)
        self.data[pos] = x
        self.taille += 1

    def defiler(self):
        if self.taille == 0:
            raise IndexError("file vide")
        x = self.data[self.tete]
        self.tete = (self.tete + 1) % len(self.data)
        self.taille -= 1
        return x

• enqueue/dequeue : O(1) garanti (pas de décalage, pas de réallocation).
• C'est l'implémentation classique des files en C et dans de nombreuses bibliothèques.

---

6. Skip List

6.1 Idée

Une skip list est une liste chaînée avec plusieurs niveaux de raccourcis : une liste ordonnée où chaque nœud est promu au niveau suivant avec probabilité p (typiquement 1/2).

Diagramme en cours de génération...

Niveau le plus haut = raccourcis rares ; niveau 0 = liste complète.

6.2 Recherche — O(log n) attendu

On descend depuis le niveau le plus haut : à chaque niveau, on avance tant que le suivant est ≤ cible, puis on descend d'un niveau.

import random

class NoeudSkip:
    def __init__(self, valeur, niveaux):
        self.valeur = valeur
        self.suivants = [None] * niveaux   # un pointeur par niveau

class SkipList:
    def __init__(self, proba=0.5, max_niveaux=16):
        self.proba = proba
        self.max_niveaux = max_niveaux
        self.tete = NoeudSkip(None, max_niveaux)   # sentinelle
        self.niveaux_actuels = 1

    def _niveau_aleatoire(self):
        niveau = 1
        while random.random() < self.proba and niveau < self.max_niveaux:
            niveau += 1
        return niveau

    def rechercher(self, cible):
        cur = self.tete
        for niv in range(self.niveaux_actuels - 1, -1, -1):
            while cur.suivants[niv] and cur.suivants[niv].valeur < cible:
                cur = cur.suivants[niv]
        cur = cur.suivants[0]
        return cur if cur and cur.valeur == cible else None

    def inserer(self, valeur):
        niveau = self._niveau_aleatoire()
        if niveau > self.niveaux_actuels:
            self.niveaux_actuels = niveau
        nouveau = NoeudSkip(valeur, niveau)
        cur = self.tete
        preds = [self.tete] * self.max_niveaux
        for niv in range(self.niveaux_actuels - 1, -1, -1):
            while cur.suivants[niv] and cur.suivants[niv].valeur < valeur:
                cur = cur.suivants[niv]
            preds[niv] = cur
        for niv in range(niveau):
            nouveau.suivants[niv] = preds[niv].suivants[niv]
            preds[niv].suivants[niv] = nouveau

6.3 Analyse

• Probabiliste : l'équilibre est probabiliste (une pièce de monnaie), pas garanti comme l'AVL.
• Facilité : nettement plus simple à implémenter qu'un arbre équilibré.
• Utilisé par : Redis (ZADD, sorted sets), MemSQL, LevelDB (variante), KV stores.

Comparaison : « skip list = arbre équilibré sans rotations, avec des pièces de monnaie ».

---

7. Applications réelles

7.1 LRU Cache (Least Recently Used)

Le LRU cache combine une hash map (trouver une clé en O(1)) et une liste doublement chaînée (suivre l'ordre d'utilisation).

Diagramme en cours de génération...

• get(k) : hash → nœud (O(1)), déplacer le nœud en tête (O(1)).
• put(k, v) : insérer en tête ; si dépassement, supprimer la queue (LRU) et retirer de la hash.
• Coût : O(1) pour get et put.

C'est l'implémentation des caches : Redis (approximé), caches HTTP, CPU page tables.

class LRUCache:
    def __init__(self, capacite):
        self.capacite = capacite
        self.hash = {}
        self.tete = None    # MRU
        self.queue = None   # LRU
        self._nœuds = {}

    def _retirer(self, noeud):
        if noeud.precedent: noeud.precedent.suivant = noeud.suivant
        else: self.tete = noeud.suivant
        if noeud.suivant: noeud.suivant.precedent = noeud.precedent
        else: self.queue = noeud.precedent

    def _deplacer_en_tete(self, noeud):
        self._retirer(noeud)
        noeud.suivant = self.tete
        noeud.precedent = None
        if self.tete: self.tete.precedent = noeud
        self.tete = noeud
        if self.queue is None: self.queue = noeud

    def get(self, cle):
        if cle not in self.hash: return -1
        noeud = self.hash[cle]
        self._deplacer_en_tete(noeud)
        return noeud.valeur

    def put(self, cle, valeur):
        if cle in self.hash:
            self.hash[cle].valeur = valeur
            self._deplacer_en_tete(self.hash[cle])
            return
        noeud = NoeudDouble(valeur)
        self.hash[cle] = noeud
        self._deplacer_en_tete(noeud)
        if len(self.hash) > self.capacite:
            lru = self.queue
            self._retirer(lru)
            for c, n in list(self.hash.items()):
                if n is lru:
                    del self.hash[c]

⚠️ En Python, on utiliserait OrderedDict (ou collections.OrderedDict.move_to_end) — la version ci-dessus montre le mécanisme.

7.2 Undo / Redo d'un éditeur

• Undo stack : pile d'actions (chapitre 05).
• Avec redo : deux piles (undo et redo) ; la liste chaînée est une alternative pour les implémentations avec curseur dans l'historique (listes d'états).

7.3 Playlist de musique

• Lecture suivante/précédente : liste doublement chaînée — O(1) pour passer au nœud précédent/suivant.
• Lecture en boucle : liste circulaire.
• Shuffle : nécessite un accès aléatoire → tableau. Compromis classique.

7.4 Autres applications

---

8. Tableaux vs listes chaînées

8.1 Comparaison directe

8.2 Règles pratiques

1. Par défaut, utilisez un tableau (ou deque).
2. Choisissez une liste chaînée si : insertions/suppressions au milieu très fréquentes avec nœud en main (LRU, playlist, éditeur).
3. Fuyez les listes chaînées pour : parcours massifs, accès aléatoires, accès fréquents — le cache domine.

8.3 Mesure d'illustration

---

9. Implémentation multi-langages

9.1 Go

type Noeud struct {
    valeur  int
    suivant *Noeud
}

func AddFirst(tete *Noeud, x int) *Noeud {
    return &Noeud{valeur: x, suivant: tete}
}

func Parcourir(tete *Noeud) []int {
    var resultat []int
    for cur := tete; cur != nil; cur = cur.suivant {
        resultat = append(resultat, cur.valeur)
    }
    return resultat
}

9.2 C++

struct Noeud {
    int valeur;
    Noeud* suivant;
    Noeud(int v) : valeur(v), suivant(nullptr) {}
};

void addFirst(Noeud*& tete, int x) {
    Noeud* n = new Noeud(x);
    n->suivant = tete;
    tete = n;
}

void liberer(Noeud* tete) {
    while (tete) {
        Noeud* suivant = tete->suivant;
        delete tete;
        tete = suivant;
    }
}

9.3 TypeScript

interface Noeud<T> {
  valeur: T;
  suivant: Noeud<T> | null;
}

class Liste<T> {
  tete: Noeud<T> | null = null;

  addFirst(x: T): void {
    this.tete = { valeur: x, suivant: this.tete };
  }

  *itérer(): Generator<T> {
    let cur = this.tete;
    while (cur) {
      yield cur.valeur;
      cur = cur.suivant;
    }
  }
}

9.4 Java

public class ListeSimple<T> {
    private static class Noeud<T> {
        T valeur;
        Noeud<T> suivant;
        Noeud(T v) { valeur = v; }
    }
    private Noeud<T> tete;

    public void addFirst(T x) {
        Noeud<T> n = new Noeud<>(x);
        n.suivant = tete;
        tete = n;
    }
}

9.5 Python

Voir sections 2-7 (implémentation de référence).

---

10. Résumé

1. Simplement chaînée : insertion en tête O(1), suppression d'un nœud O(n) (pas de précédent).
2. Sentinelles : suppriment les cas limites ; indispensables pour la double chaînée propre.
3. Doublement chaînée : suppression et déplacement O(1) — la base du LRU cache.
4. Circulaire : rounds, round-robin, file circulaire (O(1) garanti).
5. Skip list : O(log n) attendu, simple à implémenter, probabiliste — utilisée par Redis.
6. LRU cache = hash map + double chaînée : get/put O(1).
7. Règle d'or : tableau par défaut ; chaînée seulement pour insertions au milieu fréquentes avec nœud en main.

---

Exercices d'auto-évaluation

1. Pourquoi supprimer un nœud est-il O(n) dans une liste simple ?
2. À quoi sert une sentinelle ?
3. Pourquoi la double chaînée permet-elle une suppression O(1) ?
4. Dans quel cas la file circulaire est-elle préférable à un deque ?
5. Expliquer pourquoi la recherche dans une skip list est O(log n) en moyenne.
6. Décrire le mécanisme de get() d'un LRU cache.
7. Citer deux cas où une playlist utiliserait une liste chaînée et un où elle utiliserait un tableau.

Passez au quiz puis aux TP.