Stefan Röttger

← Knoten aus Liste Löschen | ● | Binäre Bäume →

Ein Knoten einer doppelt verketteten Liste enthält einen Vorgänger-Zeiger prev und einen Nachfolger-Zeiger next.

Dies benötigt mehr Speicher pro Knoten für die Zeiger. Dies lohnt sich deshalb nur bei schwergewichtigen Nutzdaten (heavy weight).

         -------     -------     -------     -------
head --> |d|p|n| --> |d|p|n| --> |d|p|n| --> |d|p|n| --> null
         -------     -------     -------     -------
            |  ^        |  ^        |  ^        |  ^
null <------/  \--------/  \--------/  \--------/  \---- tail

Im Vergleich mit dynamischen Arrays verbrauchen die doppelt verketteten Listen mehr Speicher. Dafür ist die Dauer einer Listenmanipulation (Einfügen & Löschen) unabhängig von der Anzahl k der Knoten, d.h. konstant.

Q Läßt sich eine Suchoperation in weniger als durchschnittlich $\frac{k}{2}$ Schritten durchführen?

Dazu benötigt man Binaere Baeume.

← Knoten aus Liste Löschen | ● | Binäre Bäume →