Unterschied zwischen einfach verknüpfter Liste und doppelt verknüpfter Liste

Einfach verknüpfte Liste vs. doppelt verknüpfte Liste

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 ihrem eigenen Speicherblock zu, und die Gesamtstruktur wird durch Verknüpfung dieser Elemente als Verknüpfungen in einer Kette erhalten. Eine einfach verknüpfte Liste besteht aus einer Sequenz von Knoten, und jeder Knoten hat eine Referenz auf den nächsten Knoten in der Sequenz. Eine doppelt verknüpfte Liste enthält eine Sequenz von Knoten, in denen jeder Knoten eine Referenz 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 dargestellt. Das Datenfeld enthält die tatsächlich gespeicherten Daten und das nächste Feld enthält die Referenz 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 Element speichern eine Referenz auf das nächste Element. Letztes 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 hat drei Felder, wie in Fig. 3 gezeigt. Ähnlich wie die einfach verknüpfte Liste enthält das Datenfeld die tatsächlich gespeicherten Daten und das nächste Feld enthält die Referenz 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 in seinem nächsten Feld einen Nullwert und das erste Element in der Liste enthält in seinem vorherigen Feld einen Nullwert. Eine doppelt verknüpfte Liste kann durch Befolgen der nächsten Referenzen in jedem Element vorwärts und in ähnlicher Weise mit den vorherigen Referenzen in jedem Element rückwärts durchlaufen werden.

Was ist der Unterschied zwischen einfach verknüpften Listen und doppelt verknüpften Listen??

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 sowohl Verweise auf das nächste Element als auch auf das vorherige Element in der Liste enthält. Doppelt verknüpfte Listen erfordern mehr Platz für jedes Element in der Liste. Elementare Operationen wie Einfügen und Löschen sind komplexer, da sie sich auf zwei Referenzen beziehen müssen. Doppelte Linklisten ermöglichen jedoch eine einfachere Manipulation, da die Liste in Vorwärts- und Rückwärtsrichtung durchlaufen werden kann.