03 — Listes chaînées simples et doubles

Ce que tu vas apprendre

• Comment une liste chaînée stocke ses éléments avec des nœuds et des pointeurs
• L'insertion et la suppression en O(1) quand on tient le nœud
• La différence entre liste simplement et doublement chaînée
• Pourquoi le tableau dynamique gagne souvent malgré une moins bonne complexité

Prérequis

• 02 — File de priorité et tas
• L'aperçu des listes chaînées dans le coût des structures

La série Complexité a donné les coûts de la liste chaînée sans la construire. On comble ce manque. La liste chaînée est l'opposé du tableau : là où le tableau range ses éléments côte à côte en mémoire, la liste les éparpille et les relie par des pointeurs. Ce choix inverse complètement le profil de coûts, et explique des cas où la liste brille, ainsi que la raison pour laquelle, en pratique, on lui préfère souvent le tableau.

Nœuds et pointeurs

Une liste chaînée est une suite de nœuds. Chaque nœud contient une valeur et un pointeur vers le nœud suivant. Le dernier pointe vers rien (null). On garde une référence vers le premier nœud, la tête.

typescriptclass Noeud<T> {
  valeur: T;
  suivant: Noeud<T> | null = null;
  constructor(valeur: T) { this.valeur = valeur; }
}

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

  // insertion en tête : O(1)
  insererTete(valeur: T): void {
    const noeud = new Noeud(valeur);
    noeud.suivant = this.tete;
    this.tete = noeud;
  }
}

Comme les nœuds ne sont pas contigus, il n'y a pas de calcul d'adresse par index. Pour atteindre le k-ième élément, il faut suivre les pointeurs depuis la tête, un par un : l'accès par index est O(n). C'est le prix structurel de la liste chaînée.

La force : insertion et suppression en O(1)

L'intérêt de la liste vient de la modification. Insérer ou supprimer un nœud ne demande pas de décaler quoi que ce soit, contrairement au tableau. Il suffit de rebrancher des pointeurs. Si tu tiens déjà le nœud concerné (ou celui qui le précède), l'opération est en O(1).

python# supprimer le nœud qui suit `precedent` : O(1)
def supprimer_apres(precedent):
    if precedent.suivant is not None:
        precedent.suivant = precedent.suivant.suivant  # on saute le nœud

C'est là que la liste bat le tableau : insérer ou supprimer en début de séquence est O(1) pour la liste, O(n) pour le tableau (qui doit tout décaler). Pour une file (article 01) ou pour toute structure où l'on ajoute et retire beaucoup en tête, la liste chaînée est un bon support.

La nuance importante : ce O(1) suppose qu'on tient déjà le nœud. Si on doit d'abord le trouver par sa valeur ou son index, la recherche est O(n), et le gain disparaît. La liste chaînée est rapide à modifier, pas à localiser.

Liste simple ou double

Dans une liste simplement chaînée, chaque nœud ne connaît que son suivant. On ne peut parcourir que dans un sens, et pour supprimer un nœud il faut connaître son prédécesseur.

Dans une liste doublement chaînée, chaque nœud a aussi un pointeur vers le précédent. On peut parcourir dans les deux sens, et supprimer un nœud dont on a la référence directe en O(1), sans connaître son prédécesseur. Le prix : un pointeur de plus par nœud, donc plus de mémoire.

typescriptclass NoeudDouble<T> {
  valeur: T;
  suivant: NoeudDouble<T> | null = null;
  precedent: NoeudDouble<T> | null = null;
  constructor(valeur: T) { this.valeur = valeur; }
}

La liste doublement chaînée est la base de structures comme le cache LRU (où l'on déplace et supprime des nœuds en O(1)) et de la deque qui sert de file efficace (article 01).

Pourquoi le tableau gagne souvent

Sur le papier, la liste chaînée a de meilleures complexités pour l'insertion. En pratique, le tableau dynamique est souvent plus rapide, pour deux raisons matérielles.

D'abord, la localité mémoire. Les éléments d'un tableau sont contigus, ce qui exploite parfaitement le cache du processeur : lire un élément précharge les suivants. Les nœuds d'une liste sont dispersés, chaque accès est un saut en mémoire qui rate souvent le cache. Sur du parcours, le tableau peut être plusieurs fois plus rapide à complexité égale.

Ensuite, le surcoût mémoire. Chaque nœud stocke, en plus de sa valeur, un ou deux pointeurs (8 octets chacun sur une machine 64 bits). Pour une liste d'entiers, c'est doubler ou tripler la mémoire utilisée.

En conséquence, on utilise rarement une liste chaînée à la main en TypeScript ou en Python. On la rencontre surtout comme brique interne (la deque de Python, les implémentations de files), comme support d'un cache LRU, ou dans les langages systèmes pour des cas précis. Mais comprendre son fonctionnement éclaire le compromis fondamental contiguïté contre flexibilité des pointeurs.

L'article suivant passe aux structures arborescentes, en commençant par l'arbre binaire de recherche, qui maintient les éléments triés tout en permettant une recherche rapide.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 10.2 "Linked Lists". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.3. Addison-Wesley.
• Bentley, J. (2000). Programming Pearls (2nd ed.), Colonne 9 (localité mémoire et cache). Addison-Wesley.