Liste chaînée
Dernière mise à jour
Une liste chaînée stocke une séquence sous forme de chaîne de nœuds, où chaque nœud contient une valeur et un pointeur vers le nœud suivant. Contrairement à un tableau, les nœuds ne sont pas contigus en mémoire : vous suivez les pointeurs next pour parcourir la liste. Appuyez sur lecture ci-dessus pour voir des nœuds se lier en tête et en queue, une valeur être recherchée en parcourant la chaîne, et un nœud être supprimé en recâblant un pointeur.
Insérer ou supprimer en tête est en O(1) car il suffit de repointer la tête. Atteindre une position au milieu ou en queue est en O(n) car vous devez d'abord y parcourir. Ce compromis -extrémités peu coûteuses, pas d'accès aléatoire- est ce qui distingue une liste chaînée d'un tableau.
Complexité temporelle
| Opération | Complexité | Notes |
|---|---|---|
| Insérer en tête | O(1) | Repointer la tête |
| Insérer en queue | O(n) | Parcourir jusqu'à la fin d'abord (O(1) avec un pointeur de queue) |
| Rechercher | O(n) | Suivre les pointeurs next |
| Supprimer la tête | O(1) | Repointer la tête au-delà d'elle |
| Accès par indice | O(n) | Pas d'accès aléatoire |
Liste chaînée vs tableau
| Aspect | Liste chaînée | Tableau |
|---|---|---|
| Mémoire | Nœuds dispersés + pointeurs | Bloc contigu |
| Accès aléatoire | O(n) | O(1) |
| Insérer/supprimer en tête | O(1) | O(n) (décalage) |
| Compatibilité avec le cache | Mauvaise | Bonne |
Exemple résolu
Construire la liste [10, 20], préfixer 5, puis supprimer 20 :
| Étape | Structure | Action |
|---|---|---|
| Début | head -> null | Liste vide |
| Insérer en tête 10 | head -> 10 -> null | Repointer la tête vers un nouveau nœud dont le next est l'ancienne tête (null) |
| Insérer en queue 20 | head -> 10 -> 20 -> null | Parcourir jusqu'au nœud 10, régler son next sur un nouveau nœud 20 |
| Insérer en tête 5 | head -> 5 -> 10 -> 20 -> null | Le nouveau nœud 5 pointe vers l'ancienne tête 10 ; la tête pointe maintenant vers 5 |
| Supprimer 20 | head -> 5 -> 10 -> null | Parcourir jusqu'à 10, régler son next de 20 sur null ; le nœud 20 est délié |
Quand utiliser une liste chaînée
| À utiliser quand | À éviter quand |
|---|---|
| Vous insérez ou supprimez aux extrémités (ou à un nœud que vous détenez) bien plus que vous n'indexez | Vous avez besoin d'un accès aléatoire rapide par position (indexation O(1)) |
| La taille change beaucoup et vous ne voulez pas de coût de redimensionnement/copie | Vous parcourez des boucles serrées où la localité du cache domine la performance |
| Vous construisez une file, une pile ou une liste d'adjacence | La mémoire est limitée : chaque nœud paie un pointeur supplémentaire par élément |
| Vous avez besoin de références stables vers des nœuds qui survivent à des insertions ailleurs | Vous lisez surtout et modifiez rarement, donc un tableau est plus simple et plus rapide |
Code de Linked List
Une implémentation propre et exécutable de 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 Linked List en Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Code de Linked List en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Code de Linked List en Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Code de Linked List en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Code de Linked List en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}FAQ sur les listes chaînées
Quelle est la différence entre une liste chaînée et un tableau ?
Un tableau stocke les éléments dans un seul bloc contigu, offrant un accès aléatoire
O(1) mais des insertions/suppressions O(n) qui décalent les éléments. Une liste chaînée stocke les nœuds n'importe où en mémoire reliés par des pointeurs, offrant des insertions/suppressions O(1) à une position connue mais un accès O(n) puisque vous devez parcourir la chaîne.Quand devrais-je utiliser une liste chaînée ?
Les listes chaînées brillent lorsque vous insérez ou supprimez fréquemment aux extrémités (ou à un nœud dont vous détenez déjà une référence) et avez rarement besoin d'un accès aléatoire, par exemple les files, les piles, les listes d'adjacence et les caches LRU. Si vous avez besoin d'un accès indexé rapide, un tableau ou un tableau dynamique est généralement préférable.
Quelle est la complexité temporelle d'une liste chaînée ?
Insérer ou supprimer en tête est en
O(1). La recherche, ou atteindre la queue sans pointeur de queue, est en O(n) car vous suivez les pointeurs next un par un. Il n'y a pas d'accès aléatoire O(1) : indexer dans une liste chaînée est en O(n).Quelle est la différence entre une liste simplement et doublement chaînée ?
Une liste simplement chaînée ne stocke qu'un pointeur
next par nœud, vous pouvez donc parcourir dans une seule direction et supprimer un nœud nécessite une référence à son prédécesseur. Une liste doublement chaînée ajoute un pointeur prev, permettant le parcours arrière et la suppression O(1) d'un nœud détenu, au prix d'un pointeur supplémentaire par nœud et de plus de gestion à chaque insertion et suppression.Pourquoi insérer en queue est-il O(n) si insérer en tête est O(1) ?
Insérer en tête ne recâble que le pointeur
head, ce qui est un travail constant. Atteindre la queue signifie suivre les pointeurs next depuis la tête jusqu'à la fin, ce qui est en O(n). Conserver un pointeur tail séparé rend l'insertion en queue également en O(1), c'est pourquoi les listes réelles suivent souvent les deux extrémités.Les listes chaînées ont-elles une insertion O(1) partout ?
Non, c'est une idée reçue courante. L'insertion elle-même n'est en
O(1) qu'une fois que vous détenez déjà un pointeur vers le nœud après lequel vous insérez. Trouver cette position par valeur ou par indice coûte toujours O(n) car vous devez parcourir la chaîne pour y arriver.Ressources associées
Plus de visualisations
