Les tableaux et les listes chaînées stockent tous deux des séquences, mais leurs compromis sur la disposition en mémoire sont opposés, et ce choix détermine quelles opérations sont peu coûteuses.
Tableaux : accès rapide par position
Un tableau range ses éléments côte à côte en mémoire. Trouver l’élément numéro k se résume à un calcul d’adresse, donc l’accès par indice est en O(1). Le coût apparaît à l’insertion ou à la suppression au milieu : tous les éléments suivants doivent être décalés, soit O(n). Le stockage contigu se prête aussi bien aux caches du processeur, ce qui aide en pratique.
Listes chaînées : remaniement rapide
Une liste chaînée range chaque valeur dans un nœud accompagné d’un pointeur vers le nœud suivant. Si vous détenez déjà une référence vers un nœud, insérer ou supprimer après lui revient à réorienter un pointeur, en O(1). En contrepartie, atteindre le k-ième nœud demande de parcourir k étapes, et chaque nœud consomme de la mémoire supplémentaire pour son pointeur.
Les tableaux dynamiques comblent une bonne partie de l’écart
Un tableau dynamique s’agrandit en allouant un bloc plus grand lorsqu’il est plein. Comme la capacité croît de façon multiplicative, l’ajout en fin de tableau est en O(1) amorti. Pour la plupart des programmes courants, c’est le choix par défaut raisonnable.
Guide de décision rapide
- Vous avez besoin d’accès par indice, de recherche dichotomique ou d’une mémoire compacte : choisissez un tableau.
- Vous insérez ou supprimez souvent au milieu, à des positions connues, avec des références de nœuds en main : envisagez une liste chaînée.
- Vous hésitez : commencez par un tableau dynamique et mesurez avant de changer.
Une idée reçue
Les listes chaînées ne sont pas automatiquement plus rapides pour l’insertion. Si vous devez d’abord chercher la position, cette recherche coûte O(n) et peut annuler l’avantage.
Pour aller plus loin
Retrouvez le traitement complet, les exemples et les exercices dans Les algorithmes en clair.
Adapté de Les algorithmes en clair, publié par Choral Software. Texte de l’article et exemples originaux © 2026 Choral Software. Tous droits réservés.