Différence entre la liste à liaison unique et la liste à double liaison
La liste chaînée est une structure de données linéaire utilisée pour stocker une collection de données. Une liste lié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 liant ces éléments comme des 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 de la séquence. Une liste doublement liée contient une séquence de noeuds dans laquelle chaque noeud contient une référence au noeud suivant ainsi qu'au noeud précédent.
Chaque élément d'une liste à liaison unique comporte deux champs, comme le montre 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 dans la chaîne. Le premier élément de la liste liée est stocké en tant que tête de la liste chaînée.
La figure 2 représente une liste individuellement liée 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 prochain champ. Tout élément de la liste peut être consulté 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
La figure 4 représente une liste doublement lié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 NULL dans son champ suivant et le premier élément de la liste contient une valeur NULL dans son champ précédent. La liste doublement chaînée peut être parcourue en suivant les références suivantes dans chaque élément et peut également être parcourue en arrière en utilisant les références précédentes de chaque élément.
Quelle est la différence entre Singly Linked List et Doubly Linked List?
Chaque élément de la liste à liaison unique contient une référence à l'élément suivant de la liste, alors que chaque élément de la liste doublement chaînée 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 en avant et en arrière.
