Les deux stockent des séquences, mais ils ont des profils de coûts opposés. Un tableau est une mémoire contiguë avec une indexation en O(1) ; une liste chaînée est constituée de nœuds dispersés reliés par des pointeurs, avec un insertion/suppression en O(1) aux extrémités mais sans indexation.
Comparaison côte à côte
| Opération | Tableau (dynamique) | Liste chaînée |
|---|---|---|
| Accès par index | O(1) | O(n) |
| Recherche | O(n) | O(n) |
| Insertion/suppression en tête | O(n) | O(1) |
| Insertion/suppression en queue | O(1) amorti | O(1) avec pointeur de queue |
| Insertion/suppression au milieu | O(n) | O(n) recherche + O(1) épissure |
| Surcharge mémoire | faible | élevée (pointeur par nœud) |
| Localité du cache | excellente | mauvaise |
Image
text
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Quand choisir laquelle
- Tableau quand vous avez besoin d'accès aléatoire, itérez souvent, ou voulez une performance cache-friendly (le choix par défaut usuel).
- Liste chaînée quand vous insérez/supprimez fréquemment en tête ou épissez des nœuds auxquels vous tenez déjà une référence, et rarement indexez.
Pourquoi c'est important
En pratique les tableaux gagnent la plupart du temps car la localité du cache éclipse les différences de Big-O pour des tailles typiques.
Connaître les deux vous permet de justifier votre choix en entretiens au lieu de choisir par défaut aveuglément — et d'expliquer pourquoi "insertion en O(1)" ne bat rarement un tableau contigu.