À retenir
- Navigation possible dans les deux sens (avant et arrière).
- Consomme un peu plus de mémoire qu'une liste simple car chaque maillon stocke deux adresses au lieu d'une.
- Idéale pour les ajouts et suppressions fréquents au milieu de la structure.
Une liste doublement liée est une structure de données organisée comme une chaîne d'éléments où chaque maillon connaît à la fois son voisin précédent et son voisin suivant. C'est comme une file de personnes qui se tiennent la main : chaque personne utilise sa main gauche pour tenir celle de la personne devant elle, et sa main droite pour celle de la personne derrière elle.
Étymologie
Traduction directe de l'anglais doubly linked list. Le terme vient du latin lista (bordure, bande) et du verbe lier, indiquant la connexion bidirectionnelle entre les données.
Exemples d'usage
- La gestion de l'historique d'un navigateur web (boutons Page précédente et Page suivante).
- La liste de lecture d'un lecteur de musique (permettant de passer à la piste suivante ou de revenir à la précédente).
- Le système d'annulation (Undo/Redo) dans un logiciel d'édition de texte.
Cas d'usage
On l'utilise principalement lorsqu'on a besoin de parcourir des données dans les deux sens de manière efficace, ou pour insérer et supprimer des éléments rapidement n'importe où dans la liste sans avoir à décaler tous les autres éléments (contrairement à un tableau).
Bonnes pratiques
Lors de l'ajout ou de la suppression d'un maillon, il est crucial de mettre à jour les liens des deux voisins pour éviter de casser la chaîne. Il faut également toujours vérifier si le lien précédent ou suivant est vide (valeur null), ce qui indique qu'on est arrivé au début ou à la fin de la liste.
Synonymes
Antonymes
Conseil
Si vous débutez, dessinez les maillons avec des flèches sur papier pour visualiser comment les liens se croisent. C'est le meilleur moyen de comprendre pourquoi il faut modifier quatre pointeurs lors d'une insertion au milieu de la liste.
Questions fréquentes
Quelle est la différence avec une liste simplement liée ?
Dans une liste simple, on ne peut avancer que vers l'élément suivant. Dans une liste double, on peut aussi revenir en arrière.
Est-ce que cela prend plus de place en mémoire ?
Oui, car chaque élément doit enregistrer une information supplémentaire : l'emplacement du maillon précédent.