Liste simplement liée vs liste doublement liée
Liste chaînée est une structure de données linéaire utilisée pour stocker une collection de données. Une liste chaînée alloue de la mémoire à ses éléments séparément dans son propre bloc de mémoire et la structure globale est obtenue en reliant ces éléments comme des maillons dans une chaîne. Une liste chaînée simple est composée d'une séquence de nœuds et chaque nœud a une référence au nœud suivant dans la séquence. Une liste doublement chaînée contient une séquence de nœuds dans laquelle chaque nœud contient une référence au nœud suivant ainsi qu'au nœud précédent.
Liste chaînée simple
Chaque élément d'une liste liée individuellement comporte deux champs, comme illustré à la figure 1. Le champ de données contient les données réelles stockées et le champ suivant contient la référence à l'élément suivant de la chaîne. Le premier élément de la liste chaînée est stocké en tant que tête de la liste chaînée.
La figure 2 représente une liste chaînée simple avec trois éléments. Chaque élément stocke ses données et tous les éléments sauf le dernier stockent une référence à l'élément suivant. Le dernier élément contient une valeur nulle dans son champ suivant. Tout élément de la liste est accessible en commençant par l'en-tête et en suivant le pointeur suivant jusqu'à ce que vous rencontriez l'élément requis.
Liste doublement chaînée
Chaque élément d'une liste doublement liée comporte trois champs, comme illustré à la figure 3. Semblable à une liste à liaison simple, le champ de données contient les données réelles stockées et le champ suivant contient la référence à l'élément suivant de la chaîne. De plus, le champ précédent contient la référence à l'élément précédent dans la chaîne. Le premier élément de la liste chaînée est stocké en tant que tête de la liste chaînée.
La figure 4 représente une liste doublement chaînée avec trois éléments. Tous les éléments intermédiaires stockent des références aux éléments premier et précédent. Le dernier élément de la liste contient une valeur nulle dans son champ suivant et le premier élément de la liste contient une valeur nulle dans son champ précédent. Une liste à double liaison peut être parcourue vers l'avant en suivant les références suivantes dans chaque élément et de la même manière peut être parcourue vers l'arrière en utilisant les références précédentes dans chaque élément.
Quelle est la différence entre une liste chaînée simple et une liste chaînée double ?
Chaque élément de la liste simplement liée contient une référence à l'élément suivant de la liste, tandis que chaque élément de la liste doublement liée contient des références à l'élément suivant ainsi qu'à l'élément précédent de la liste. Les listes doublement chaînées nécessitent plus d'espace pour chaque élément de la liste et les opérations élémentaires telles que l'insertion et la suppression sont plus complexes car elles doivent traiter deux références. Mais les listes de liens doubles permettent une manipulation plus facile car elles permettent de parcourir la liste en avant et en arrière.
