À retenir
- Permet un parcours bidirectionnel (avant et arrière).
- L'insertion et la suppression sont très rapides si l'on connaît la position.
- Consomme un peu plus de mémoire qu'une liste simple à cause du pointeur supplémentaire.
Une liste doublement chaînée est une structure de données où chaque élément, appelé nœud, contient non seulement une information mais aussi deux « adresses » : l'une pointant vers l'élément suivant et l'autre vers l'élément précédent. Imaginez une cordée d'alpinistes où chaque personne tient une corde reliée à celui de devant et une autre reliée à celui de derrière, permettant de circuler facilement dans les deux sens.
Étymologie
Le terme provient de l'analogie avec une chaîne physique dont les maillons sont imbriqués. L'adjectif « doublement » souligne la présence de deux liens par maillon, contrairement à la liste « simplement » chaînée qui n'en possède qu'un seul. C'est une traduction directe de l'anglais doubly linked list.
Exemples d'usage
- Le système de navigation d'un navigateur web : le bouton « précédent » et le bouton « suivant » utilisent ce principe pour naviguer dans l'historique des pages consultées.
- Un lecteur de musique permettant de passer à la chanson suivante ou de revenir à la précédente.
- La gestion des calques dans un logiciel de retouche d'image (Photoshop, GIMP).
Cas d'usage
On utilise ce concept lorsqu'on a besoin d'insérer ou de supprimer des éléments très rapidement n'importe où dans une séquence, ou quand on doit parcourir des données dans les deux directions. Elle est fondamentale pour créer des structures plus complexes comme les files à deux bouts (deques) ou certains types de mémoires caches.
Bonnes pratiques
Lors de la manipulation (ajout ou suppression), il est crucial de mettre à jour les pointeurs des deux voisins directs, sinon la chaîne est brisée. Il faut aussi toujours prévoir le cas particulier du premier élément (qui n'a pas de précédent) et du dernier (qui n'a pas de suivant) pour éviter que le programme ne plante en cherchant une adresse inexistante (erreur de type null pointer).
Synonymes
Antonymes
Conseil
Si vous débutez, n'hésitez pas à dessiner des boîtes avec des flèches sur une feuille de papier. Visualiser le moment où l'on « débranche » une flèche pour la « rebrancher » sur un nouveau nœud est le meilleur moyen de comprendre la logique du code sans faire d'erreurs.
Questions fréquentes
Quelle est la différence avec un tableau ?
Dans un tableau, les éléments sont côte à côte en mémoire et on y accède par un index. Dans une liste chaînée, les éléments peuvent être éparpillés ; on passe de l'un à l'autre via des liens.
Pourquoi ne pas toujours utiliser une liste doublement chaînée ?
Parce qu'elle demande plus de mémoire (deux liens par élément au lieu d'un) et que l'accès à un élément précis au milieu de la liste oblige à parcourir toute la chaîne depuis le début ou la fin.