Einfach verknüpfte Liste vs doppelt verknüpfte Liste
Die verknüpfte Liste ist eine lineare Datenstruktur, in der eine Sammlung von Daten gespeichert wird. Eine verknüpfte Liste ordnet ihren Elementen Speicher separat in einem eigenen Speicherblock zu, und die Gesamtstruktur wird erhalten, indem diese Elemente als Glieder in einer Kette verknüpft werden. Eine einfach verknüpfte Liste besteht aus einer Folge von Knoten, und jeder Knoten hat einen Verweis auf den nächsten Knoten in der Folge. Eine doppelt verknüpfte Liste enthält eine Folge von Knoten, in denen jeder Knoten einen Verweis auf den nächsten Knoten sowie auf den vorherigen Knoten enthält.
Einfach verknüpfte Liste
Jedes Element in einer einfach verknüpften Liste hat zwei Felder, wie in Abbildung 1 gezeigt. Das Datenfeld enthält die tatsächlich gespeicherten Daten und das nächste Feld enthält den Verweis auf das nächste Element in der Kette. Das erste Element der verknüpften Liste wird als Kopf der verknüpften Liste gespeichert.
Abbildung 2 zeigt eine einfach verknüpfte Liste mit drei Elementen. Jedes Element speichert seine Daten und alle Elemente außer dem letzten speichern einen Verweis auf das nächste Element. Das letzte Element enthält im nächsten Feld einen Nullwert. Auf jedes Element in der Liste kann zugegriffen werden, indem Sie am Kopf beginnen und dem nächsten Zeiger folgen, bis Sie das gewünschte Element erreichen.
Doppelt verknüpfte Liste
Jedes Element in einer doppelt verknüpften Liste enthält drei Felder, wie in Abbildung 3 dargestellt. Ähnlich wie bei einer einfach verknüpften Liste enthält das Datenfeld die tatsächlich gespeicherten Daten und das nächste Feld den Verweis auf das nächste Element in der Kette. Darüber hinaus enthält das vorherige Feld den Verweis auf das vorherige Element in der Kette. Das erste Element der verknüpften Liste wird als Kopf der verknüpften Liste gespeichert.
Abbildung 4 zeigt eine doppelt verknüpfte Liste mit drei Elementen. Alle Zwischenelemente speichern Verweise auf das erste und das vorherige Element. Das letzte Element in der Liste enthält einen Nullwert im nächsten Feld und das erste Element in der Liste enthält einen Nullwert im vorherigen Feld. Eine doppelt verknüpfte Liste kann vorwärts verfolgt werden, indem den nächsten Referenzen in jedem Element gefolgt wird, und kann auf ähnliche Weise rückwärts durchlaufen werden, indem die vorherigen Referenzen in jedem Element verwendet werden.
Was ist der Unterschied zwischen einfach verknüpfter Liste und doppelt verknüpfter Liste?
Jedes Element in der einfach verknüpften Liste enthält einen Verweis auf das nächste Element in der Liste, während jedes Element in der doppelt verknüpften Liste Verweise auf das nächste Element sowie das vorherige Element in der Liste enthält. Doppelt verknüpfte Listen benötigen mehr Platz für jedes Element in der Liste, und elementare Operationen wie das Einfügen und Löschen sind komplexer, da sie sich auf zwei Referenzen beziehen müssen. Doppelte Verknüpfungslisten ermöglichen jedoch eine einfachere Bearbeitung, da die Liste in Vorwärts- und Rückwärtsrichtung durchlaufen werden kann.
