Einfach verknüpfte Liste vs. Doppelt verknüpfte Liste
Verknüpfte Liste ist eine lineare Datenstruktur, die verwendet wird, um eine Sammlung von Daten zu speichern. Eine verkettete Liste weist ihren Elementen getrennt Speicher in ihrem eigenen Speicherblock zu, und die Gesamtstruktur wird erh alten, 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 verkettete Liste enthält eine Folge von Knoten, wobei jeder Knoten sowohl eine Referenz auf den nächsten als auch 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 verkettete 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 einen Nullwert in seinem nächsten Feld. Sie können auf jedes Element in der Liste zugreifen, indem Sie am Anfang beginnen und dem nächsten Zeiger folgen, bis Sie auf das erforderliche Element treffen.
Doppelt verknüpfte Liste
Jedes Element in einer doppelt verknüpften Liste hat drei Felder, wie in Abbildung 3 gezeigt. Ähnlich wie bei einer einfach verknüpften Liste enthält das Datenfeld die tatsächlich gespeicherten Daten und das nächste Feld enthält den Verweis auf das nächste Element in der Kette. Zusätzlich 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 verkettete Liste mit drei Elementen. Alle Zwischenelemente speichern Verweise auf die ersten und vorherigen Elemente. Das letzte Element in der Liste enthält einen Nullwert in seinem nächsten Feld und das erste Element in der Liste enthält einen Nullwert in seinem vorherigen Feld. Eine doppelt verknüpfte Liste kann vorwärts durchlaufen werden, indem den nächsten Referenzen in jedem Element gefolgt wird, und kann in ähnlicher Weise rückwärts durchlaufen werden, indem die vorherigen Referenzen in jedem Element verwendet werden.
Was ist der Unterschied zwischen einer einfach verknüpften Liste und einer doppelt verknüpften Liste?
Jedes Element in der einfach verketteten Liste enthält einen Verweis auf das nächste Element in der Liste, während jedes Element in der doppelt verketteten 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 Einfügen und Löschen sind komplexer, da sie mit zwei Referenzen umgehen müssen. Listen mit doppelten Links ermöglichen jedoch eine einfachere Manipulation, da sie das Durchlaufen der Liste in Vorwärts- und Rückwärtsrichtung ermöglichen.
