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.
| 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 |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
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.
Une bibliothèque de questions d'entretien IT avec des réponses détaillées — du Junior au Senior.
Faire un don