Différence entre la liste simple liée et la liste double liée

Singly Linked List vs Doubly Linked List

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 liant ces éléments sous forme de liens dans une chaîne. Une liste à liaison unique est composée d'une séquence de nœuds et chaque nœud est référencé au nœud suivant de 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 des liens simples

Comme indiqué à la figure 1, chaque élément d'une liste à liens simples comporte deux champs. 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 qu'en tête de la liste liée..

La figure 2 décrit une liste à lien unique comportant 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. Vous pouvez accéder à n'importe quel élément de la liste en commençant par l'en-tête et en suivant le pointeur suivant jusqu'à ce que vous rencontriez l'élément requis..

Liste doublée

Comme le montre la figure 3, chaque élément d'une liste à double liaison comporte trois champs. Comme pour la liste à un seul lien, 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é en tant qu'en tête de la liste liée..

La figure 4 décrit une liste doublement liée composée de trois éléments. Tous les éléments intermédiaires stockent des références aux premier et précédent éléments. 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. Les listes doublement chaînées peuvent être parcourues en avant en suivant les références suivantes dans chaque élément et de la même manière en arrière en utilisant les références précédentes dans chaque élément.

Quelle est la différence entre une liste simple et une liste double??

Chaque élément de la liste à lien unique contient une référence à l'élément suivant de la liste, tandis que chaque élément de la liste à lien double contient des références à l'élément suivant ainsi qu'à l'élément précédent de la liste. Les listes à double liaison 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. Doublement, les listes de liens permettent une manipulation plus facile, car elles permettent de parcourir la liste dans les deux sens..