Listes chaînées : rapide à modifier, lent à parcourir
L'inverse exact du tableau — et une bonne partie des pièges classiques.
Une liste chaînée est une suite de nœuds, chacun contenant une valeur et un pointeur vers le nœud suivant (simple) ou vers le suivant ET le précédent (doublement chaînée). Contrairement au tableau, les éléments ne sont pas contigus en mémoire.
Insérer ou supprimer en tête, ou en un point déjà atteint, coûte O(1) : il suffit de rebrancher des pointeurs. C'est l'inverse du tableau, où insérer en tête coûte O(n). En contrepartie, l'accès par index coûte O(n) : il faut parcourir la liste depuis le début.
Technique la plus fondamentale à maîtriser : inverser une liste chaînée en changeant itérativement le sens des pointeurs (`prev`, `curr`, `next`), en O(n) temps et O(1) espace.
Le pattern pointeur lent/rapide, déjà vu avec le two pointers, est central sur les listes chaînées : trouver le milieu (le rapide avance de 2, le lent de 1), détecter un cycle (algorithme de Floyd), ou trouver le n-ième nœud avant la fin (deux pointeurs espacés de n).
Piège classique : perdre la référence vers le reste de la liste en réassignant un pointeur `next` trop tôt. Toujours sauvegarder le nœud suivant dans une variable temporaire avant de modifier `next`.
Vidéo
Reverse Linked List — Iterative AND Recursive (Leetcode 206) — NeetCodeQuiz
1. Pourquoi insérer en tête d'une liste chaînée est-il O(1) alors que c'est O(n) sur un tableau ?
2. Accéder au k-ième élément d'une liste chaînée simple coûte en général :
3. Le pointeur lent/rapide sur une liste chaînée sert notamment à :
4. En inversant une liste chaînée itérativement, quel piège faut-il absolument éviter ?