verkettete-liste

LinkedList (Verkettete Liste)

Kurz: Eine Liste, bei der jedes Element (Knoten) einen Verweis auf das nächste (und oft auch vorherige) Element enthält, statt wie bei einem Array zusammenhängend im Speicher zu liegen.

Genauer: Einfügen und Entfernen ist dadurch sehr schnell, sobald man die passende Stelle bereits kennt — es müssen nur die Verweise umgehängt werden, kein Speicherblock verschoben. Der Zugriff über einen Index ist dafür langsam, weil die Liste ab dem Anfang Knoten für Knoten durchlaufen werden muss, um eine bestimmte Position zu erreichen — im Gegensatz zum direkten Zugriff bei einem dynamischen Array.

Im Detail

Jeder Knoten einer verketteten Liste besteht typischerweise aus zwei Teilen: dem eigentlichen Wert und einem Verweis auf den nächsten Knoten (bei einer doppelt verketteten Liste zusätzlich auf den vorherigen):

Knoten {
    wert
    naechster: Knoten | null
}
 
# Liste 1 -> 2 -> 3 -> null
kopf = Knoten(1, Knoten(2, Knoten(3, null)))

Um ein neues Element in der Mitte einzufügen, müssen nur zwei Verweise umgebogen werden — unabhängig davon, wie lang die Liste bereits ist:

# Neues Element zwischen "aktuell" und "aktuell.naechster" einfügen
neuerKnoten.naechster = aktuell.naechster
aktuell.naechster = neuerKnoten

Genau das ist der entscheidende Vorteil gegenüber einem dynamischen Array: Bei einem Array müsste ein Einfügen in der Mitte ALLE nachfolgenden Elemente um eine Position verschieben (Aufwand proportional zur Listenlänge), bei einer verketteten Liste ist es unabhängig von der Gesamtlänge immer gleich schnell — vorausgesetzt, man hat die Einfügestelle bereits als Referenz vorliegen (das Finden dieser Stelle selbst ist bei einer verketteten Liste dagegen langsam, weil man dafür sequenziell von vorn durchlaufen muss).

Eine doppelt verkettete Liste (jeder Knoten kennt zusätzlich seinen Vorgänger) erlaubt es, auch rückwärts zu durchlaufen und ein Element zu entfernen, ohne vorher explizit den vorherigen Knoten separat suchen zu müssen — kostet dafür etwas mehr Speicher pro Knoten für den zusätzlichen Verweis.

In der Praxis ist ein dynamisches Array die deutlich häufiger genutzte Standard-Liste (schnellerer Indexzugriff, bessere Cache-Lokalität, weil die Elemente zusammenhängend im Speicher liegen) — eine verkettete Liste lohnt sich vor allem, wenn sehr häufig an beliebigen Stellen eingefügt/entfernt wird und Indexzugriff selten gebraucht wird, etwa bei bestimmten Warteschlangen- oder Editor-Implementierungen.

Siehe auch: List, ArrayList, Index