Liste doublement chaînée
Dernière mise à jour
Une liste doublement chaînée est une liste chaînée où chaque nœud contient deux pointeurs : next (vers le nœud suivant) et prev (vers le précédent). Ce lien arrière supplémentaire permet de parcourir dans les deux sens et de supprimer un nœud en O(1) lorsque vous en avez déjà une référence, car vous pouvez atteindre directement son prédécesseur au lieu de parcourir depuis la tête. Appuyez sur lecture ci-dessus pour voir les nœuds se lier et se relier dans les deux sens.
Le coût est un pointeur supplémentaire par nœud et davantage de gestion : chaque insertion et suppression doit mettre à jour à la fois next et prev chez les voisins. C'est la structure derrière de nombreuses files doubles (deques) et caches LRU, où la suppression rapide aux deux extrémités compte.
Complexité temporelle
| Opération | Complexité | Notes |
|---|---|---|
| Insérer en tête/queue | O(1) | Avec des pointeurs de tête et de queue |
| Supprimer un nœud connu | O(1) | Atteint prev directement, sans parcours |
| Recherche | O(n) | Toujours un balayage linéaire |
| Accès par indice | O(n) | Pas d'accès aléatoire |
Liste simplement vs doublement chaînée
| Aspect | Simple | Double |
|---|---|---|
| Pointeurs par nœud | 1 (next) | 2 (next + prev) |
| Parcourir en arrière | Non | Oui |
| Supprimer un nœud connu | O(n) (trouver prev) | O(1) |
| Surcoût mémoire | Plus faible | Plus élevé |
Exemple résolu
Construction de [10, 20, 30] par ajout en fin, puis suppression du nœud 20 :
| Étape | Structure | Action |
|---|---|---|
| Début | null | Liste vide : head et tail valent tous deux null |
| Ajouter 10 | 10 | Premier nœud ; head et tail pointent dessus, prev = next = null |
| Ajouter 20 | 10 <-> 20 | On pose 10.next = 20 et 20.prev = 10 ; tail = 20 |
| Ajouter 30 | 10 <-> 20 <-> 30 | On pose 20.next = 30 et 30.prev = 20 ; tail = 30 |
| Supprimer 20 | 10 <-> 30 | En utilisant 20.prev et 20.next : on pose 10.next = 30 et 30.prev = 10 en O(1) |
Quand utiliser une liste doublement chaînée
| À utiliser quand | À éviter quand |
|---|---|
| Vous devez parcourir ou raccorder dans les deux sens | Vous n'avancez que vers l'avant : une liste simple est plus légère |
Vous supprimez des nœuds arbitraires dont vous avez déjà une référence (O(1)) | Vous indexez surtout par position : utilisez un tableau pour un accès O(1) |
| Vous implémentez un deque, un cache LRU ou un historique d'annulation | La mémoire est limitée : le pointeur prev supplémentaire double le surcoût des liens |
| Les insertions et suppressions se font souvent aux deux extrémités | Les données sont petites et changent peu : copier des tableaux coûte moins cher |
Code de Doubly Linked List
Une implémentation propre et exécutable de Doubly Linked List en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Doubly Linked List en Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Code de Doubly Linked List en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Code de Doubly Linked List en Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Code de Doubly Linked List en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Code de Doubly Linked List en C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}FAQ sur les listes doublement chaînées
Quelle est la différence entre une liste simplement et doublement chaînée ?
Une liste simplement chaînée a un pointeur par nœud (
next), vous ne pouvez donc avancer que vers l'avant. Une liste doublement chaînée ajoute un pointeur prev, ce qui permet de parcourir en arrière et de supprimer en O(1) un nœud dont vous avez une référence, au prix d'un pointeur supplémentaire par nœud et de la mise à jour de deux liens à chaque changement.Quand une liste doublement chaînée vaut-elle la mémoire supplémentaire ?
Lorsque vous avez besoin d'un parcours en arrière ou d'une suppression en
O(1) de nœuds arbitraires que vous référencez déjà : les cas classiques sont les files doubles (deques) et les caches LRU, où les entrées sont déplacées et évincées fréquemment aux deux extrémités.Pourquoi une liste doublement chaînée peut-elle supprimer un nœud en O(1) ?
Pour retirer un nœud, il faut relier son prédécesseur à son successeur. Dans une liste simplement chaînée, il faudrait parcourir depuis la tête pour trouver le prédécesseur (
O(n)) ; dans une liste doublement chaînée, le pointeur prev du nœud donne directement le prédécesseur, donc la reconnexion est en O(1).Liste doublement chaînée ou tableau : lequel choisir ?
Utilisez un tableau lorsque vous avez besoin d'un accès
O(1) par indice et d'une itération efficace en cache, et lorsque les insertions se font surtout à la fin. Utilisez une liste doublement chaînée lorsque vous insérez ou supprimez souvent au milieu ou aux deux extrémités avec une référence de nœud, car c'est O(1) contre le décalage O(n) d'un tableau. Les tableaux gagnent en mémoire et en localité ; la liste gagne sur les modifications structurelles.Qu'est-ce qu'un nœud sentinelle dans une liste doublement chaînée ?
Un nœud sentinelle (ou factice) est un marqueur placé avant la tête et/ou après la queue afin que la liste ne soit jamais réellement vide. Il supprime les vérifications de
null pour head, tail et les insertions/suppressions aux bornes, permettant à chaque opération de suivre le même chemin de reconnexion. De nombreuses implémentations de caches LRU en production utilisent deux sentinelles pour éviter de traiter les extrémités comme des cas particuliers.Quel est le bug le plus courant lors d'une suppression dans une liste doublement chaînée ?
Oublier de mettre à jour
head ou tail lors de la suppression du premier ou du dernier nœud, ce qui laisse un pointeur pendant vers un nœud libéré. Vérifiez toujours si node.prev vaut null (mettez à jour head) ou si node.next vaut null (mettez à jour tail) avant de reconnecter les voisins.Ressources associées
Plus de visualisations
