Liste à lien unique vs liste à double lien
La liste lié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 en tant que liens dans une chaîne. Une liste à liaison unique est constitué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 lié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 liée individuellement
Chaque élément d'une liste liée à un seul lien 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 liée est stocké en tant que tête de la liste liée.
La figure 2 représente une liste à lien unique 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 la tête et en suivant le pointeur suivant jusqu'à ce que vous rencontriez l'élément requis.
Liste doublement liée
Chaque élément d'une liste à double liaison comporte trois champs, comme illustré à la figure 3. Semblable à une liste à liaison unique, 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. En outre, le champ précédent contient la référence à l'élément précédent de la chaîne. Le premier élément de la liste liée est stocké en tant que tête de la liste liée.
La figure 4 représente une liste à double lien 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. La liste doublement liée 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 à liaison unique et une liste à liaison double?
Chaque élément de la liste à liaison unique contient une référence à l'élément suivant de la liste, tandis que chaque élément de la liste à double liaison contient des références à l'élément suivant ainsi qu'à l'élément précédent de la liste. Les listes doublement lié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 doublement permettent une manipulation plus facile puisqu'elle permet de parcourir la liste dans les directions avant et arrière.
