wake-up-neo.net

unterschied zwischen doppelendigen verknüpften Listen und doppelt verknüpften Listen

Ich verstehe den Unterschied zwischen einer doppelendigen und einer doppelt verknüpften Liste nicht.

Was ist der Hauptunterschied zwischen den beiden?

8
pycod333

In einer doppelt verknüpften Liste hat jeder Knoten zwei Zeiger. Einer zu seinem nächsten Knoten und einer zu seinem vorherigen Knoten.

enter image description here

In einer doppelendigen verknüpften Liste hat jeder Knoten nur einen Zeiger, der auf seinen nächsten Knoten zeigt. Der Unterschied zur einseitig verbundenen Liste besteht darin, dass sie anstelle eines einzigen "Kopf" -Knotens zwei Zeiger dieser Art enthält ("erster" und "letzter"), sodass jemand Elemente an beiden Enden von einfügen kann es.

enter image description here

(Letztes Bild ist nicht so klar, fängt aber den Punkt der beiden Enden ein.)

10
Kapoios

Eine doppelt verknüpfte Liste ist eine Liste, in der die Elemente sowohl vor als auch nach dem Element in der Liste Zeiger haben. 

Eine doppelendige Liste ist meines Erachtens wie eine Deque. Dies ist eine Warteschlange, aus der Sie sowohl oben als auch unten Elemente hinzufügen und entfernen können.

2
Einar Sundgren

Einzeln verknüpft ist es eine Einbahnrichtung und es wird weniger Speicherplatz benötigt, und die Einfügung ist komplex (O (n)). Während die Doppelverknüpfung in zwei Richtungen verläuft (nächste und vorherige), benötigt sie mehr Speicher als die einzelne Liste, und die Komplexität des Einfügens und Löschens ist O (n).

1
PAULINAK

Eine doppelseitige Liste ähnelt einer gewöhnlichen verknüpften Liste, hat jedoch eine zusätzliche Funktion: einen Verweis auf den letzten Link sowie auf den ersten. In einer doppelt verknüpften Liste hat jeder Link zwei Verweise auf andere Links statt eines Der erste ist der nächste Link, wie in gewöhnlichen Listen. Die zweite ist zum vorherigen Link.

0