Différence entre la liste liée individuellement et la liste doublement liée
Liste liée individuellement vs Liste doublement liée
La liste liée est une structure de données linéaire utilisée pour stocker une collection de données. Une liste liée alloue 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 liée individuellement 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 liée contient une séquence de nœuds dans lesquels 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 individuellement a 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 de la chaîne. Le premier élément de la liste liée est stocké comme le chef de la liste liée.
La figure 2 illustre une liste liée individuellement à trois éléments. Chaque élément stocke ses données et tous les éléments à l'exception du dernier stockage une référence à l'élément suivant. Last Element détient une valeur nulle dans son prochain champ. Tout élément de la liste peut être accessible en commençant à 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 doublement liée a trois champs comme le montre la figure 3. Semblable à la liste liée individuellement, 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 de la chaîne. Le premier élément de la liste liée est stocké comme le chef de la liste liée.
La figure 4 illustre une liste doublement liée à trois éléments. Tous les éléments intermédiaires stockent des références aux premiers et précédents éléments. Le dernier élément de la liste contient une valeur nul dans son prochain champ 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 traversée en suivant les références suivantes dans chaque élément et peut également être traversée à l'envers en utilisant les références précédentes dans chaque élément.
Quelle est la différence entre la liste liée individuellement et la liste doublement liée?
Chaque élément de la liste liée individuellement 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 liées nécessitent plus d'espace pour chaque élément de la liste et des opérations élémentaires telles que l'insertion et la suppression sont plus complexes car elles doivent faire face à deux références. Mais les listes de liens doublement permettent une manipulation plus facile car elle permet de traverser la liste dans les directions avant et arrière.
