Les listes chaînées

Ajouter une valeur au début d'une liste chaînée modifie deux pointeurs, que la liste contienne 4 valeurs ou 4 millions.

Des valeurs qui pointent vers la suivante

Un tableau garde ses valeurs côte à côte, et c'est pour cela que modifier le début coûte cher. Une liste chaînée abandonne cette règle. Chaque valeur vit dans son propre petit enregistrement appelé nœud, et les nœuds peuvent se trouver n'importe où en mémoire. Les notes du cours 6.006 du MIT décrivent un nœud avec deux champs : l'élément, et next, un pointeur vers le nœud suivant. La liste elle-même ne retient que le premier nœud, appelé la tête (head). Le next du dernier nœud vaut null, ce qui marque la fin.

Pour lire la liste, on part de head et on suit les pointeurs next un par un, comme on suivrait une série de messages indiquant chacun où est caché le suivant. Cela a un coût. Il n'existe pas de formule pour l'adresse du quatrième nœud : obtenir la valeur à la position i oblige donc à visiter i + 1 nœuds. Le MIT indique que get at(i) est en O(n) pour une liste chaînée, alors que le tableau le faisait en une étape.

// un nœud par valeur : { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// parcourir la liste
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Modifier la liste en refaisant les liens

L'avantage apparaît quand on modifie la liste. Pour placer une nouvelle valeur au début, on crée un nœud dont le next est la tête actuelle, puis on fait pointer head vers le nouveau nœud. Deux changements de pointeur, et rien d'autre ne bouge. Supprimer le premier nœud demande un seul changement : faire pointer head vers head.next. Compare avec le tableau, où les mêmes opérations déplaçaient toutes les valeurs.

Au milieu, le travail consiste à trouver l'endroit. Pour insérer à la position i, on avance jusqu'au nœud juste avant (i visites), puis on fait les deux mêmes changements de pointeur : new.next = prev.next, puis prev.next = new. L'ordre compte. Si l'on modifie prev.next en premier, le reste de la liste est perdu, car plus rien ne pointe vers lui. Dans le labo, une étape est un nœud visité ou un pointeur modifié : insérer à la position 2 d'une liste de 4 nœuds coûte donc 2 visites plus 2 changements, soit 4 étapes.

Quand l'utiliser

Une liste chaînée convient bien quand la plupart des modifications ont lieu à un endroit vers lequel on a déjà un pointeur, comme le début, et qu'on a rarement besoin de la position i. On peut construire des files et des piles avec des listes chaînées, et aussi les chaînes d'une table de hachage, dans l'unité suivante. Il existe des variantes. Une liste doublement chaînée donne aussi à chaque nœud un pointeur prev : on peut alors parcourir la liste à l'envers et supprimer un nœud en une étape une fois qu'on l'a. Garder un pointeur tail en plus de head rend l'ajout à la fin bon marché.

En JavaScript de tous les jours, on écrit rarement une liste chaînée, car les tableaux sont bien optimisés et les caches des processeurs modernes favorisent les valeurs stockées côte à côte. L'idée compte quand même : les arbres, les graphes et de nombreuses structures des bibliothèques sont construits exactement ainsi, avec des nœuds et des pointeurs.