À retenir
- La taille est dynamique : elle s'adapte en temps réel aux besoins.
- L'accès aux données est séquentiel : pour atteindre le 10ème élément, l'ordinateur doit obligatoirement lire les 9 premiers.
- Elle consomme un peu plus de mémoire qu'un tableau car il faut stocker les liens (pointeurs) en plus des données.
Une liste chaînée est une structure de données composée d'une série de maillons reliés les uns aux autres. Contrairement à un tableau classique, les éléments ne sont pas rangés côte à côte dans la mémoire de l'ordinateur ; chaque élément contient sa donnée et une « adresse » (un pointeur) qui indique où se trouve le suivant, comme une chasse au trésor où chaque indice donne l'emplacement du prochain.
Étymologie
Le terme est une métaphore directe de la chaîne physique : chaque donnée est un maillon lié au suivant. En anglais, on utilise le terme linked list. Ce concept est apparu dans les années 1950, notamment avec le langage LISP, pour permettre une gestion plus souple de la mémoire vive.
Exemples d'usage
- Une liste de lecture audio (playlist) où chaque chanson pointe vers la suivante.
- Le système de gestion des blocs de données sur un disque dur (certaines structures de fichiers).
- L'historique de navigation d'un navigateur web, permettant de reculer ou d'avancer entre les pages visitées.
Cas d'usage
On utilise les listes chaînées lorsqu'on ignore à l'avance la quantité de données à stocker ou que l'on doit fréquemment ajouter ou supprimer des éléments au milieu de la liste sans vouloir déplacer physiquement toutes les autres données en mémoire.
Bonnes pratiques
Il faut toujours veiller à ce que le dernier élément de la liste pointe vers une valeur vide (NULL) pour signaler la fin du parcours. Lors de la suppression d'un maillon, il est crucial de reconnecter le maillon précédent directement au maillon suivant pour ne pas « casser » la chaîne et perdre l'accès au reste des données.
Synonymes
Antonymes
Conseil
Pour bien comprendre les listes chaînées, essayez de les dessiner sur papier avec des boîtes pour les données et des flèches pour les liens. C'est l'exercice idéal pour se familiariser avec la notion de pointeurs et de gestion dynamique de la mémoire.
Questions fréquentes
Quelle est la différence avec un tableau ?
Dans un tableau, on accède instantanément à n'importe quel élément (accès direct), mais changer sa taille est complexe. Dans une liste chaînée, l'accès est plus lent (il faut suivre la chaîne), mais l'ajout/suppression est très rapide.
C'est quoi une liste doublement chaînée ?
C'est une variante où chaque maillon possède deux liens : l'un vers l'élément suivant et l'autre vers l'élément précédent, permettant de parcourir la liste dans les deux sens.