Une liste doublement chaînée donne à chaque nœud deux pointeurs — next et prev — ce qui vous permet de traverser dans les deux directions et de supprimer un nœud en O(1) lorsque vous disposez déjà d'une référence à celui-ci (pas besoin de parcourir depuis la tête pour trouver le prédécesseur).
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
Dans une liste simplement chaînée, supprimer un nœud nécessite de d'abord trouver son prédécesseur → O(n).
| Aspect | Simplement | Doublement |
|---|---|---|
| Pointeurs par nœud | 1 (next) | 2 (next, prev) |
| Traverser en arrière | non | oui |
| Supprimer nœud connu | O(n) | O(1) |
| Surcharge mémoire | plus faible | plus élevée |
L'extraction O(1) d'un nœud connu est la propriété clé qui fait des listes doublement chaînées la partenaire des tables de hachage dans un cache LRU.
Le pointeur supplémentaire prev échange de la mémoire contre la flexibilité du mouvement bidirectionnel et de la suppression en temps constant.