Verkettete Listen

Einen Wert vorn in eine verkettete Liste einzufügen, ändert zwei Zeiger, ob die Liste 4 Werte enthält oder 4 Millionen.

Werte, die auf den nächsten zeigen

Ein Array hält seine Werte Seite an Seite, deshalb ist eine Änderung am Anfang teuer. Eine verkettete Liste verzichtet auf diese Regel. Jeder Wert wohnt in einem eigenen kleinen Datensatz, einem Knoten, und die Knoten können irgendwo im Speicher liegen. Die Unterlagen von MIT 6.006 beschreiben einen Knoten mit zwei Feldern: dem Element und next, einem Zeiger auf den folgenden Knoten. Die Liste selbst merkt sich nur den ersten Knoten, den head (Kopf). next des letzten Knotens ist null, das markiert das Ende.

Um die Liste zu lesen, beginnst du bei head und folgst den next-Zeigern einem nach dem anderen, wie bei einer Kette von Zetteln, auf denen jeweils steht, wo der nächste versteckt ist. Das hat seinen Preis. Für die Adresse des vierten Knotens gibt es keine Formel, also heißt der Wert an Position i, i + 1 Knoten zu besuchen. MIT gibt get at(i) für eine verkettete Liste mit O(n) an, wo das Array einen Schritt brauchte.

// ein Knoten pro Wert: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// die Liste durchlaufen
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Die Liste durch Umhängen ändern

Der Gewinn kommt, wenn du die Liste änderst. Um einen neuen Wert vorn einzufügen, leg einen Knoten an, dessen next der aktuelle head ist, und lass dann head auf den neuen Knoten zeigen. Zwei Zeigeränderungen, und sonst bewegt sich nichts. Den vordersten Knoten zu löschen, ist eine Änderung: head auf head.next zeigen lassen. Vergleich das mit dem Array, wo dieselben Operationen jeden Wert verschoben haben.

In der Mitte besteht die Arbeit darin, die Stelle zu finden. Um an Position i einzufügen, läufst du zum Knoten direkt davor (i Besuche) und machst dann dieselben zwei Zeigeränderungen: new.next = prev.next, dann prev.next = new. Die Reihenfolge ist wichtig. Setzt du zuerst prev.next, geht der Rest der Liste verloren, weil nichts mehr auf ihn zeigt. Im Labor ist ein Schritt ein besuchter Knoten oder ein geänderter Zeiger, also kostet Einfügen an Position 2 einer Liste mit 4 Knoten 2 Besuche plus 2 Änderungen, 4 Schritte.

Wann man sie nimmt

Eine verkettete Liste passt gut, wenn die meisten Änderungen an einer Stelle passieren, auf die du schon einen Zeiger hast, etwa vorn, und du selten Position i brauchst. Warteschlangen und Stapel lassen sich aus verketteten Listen bauen, ebenso die Ketten in einer Hashtabelle aus der nächsten Einheit. Es gibt Varianten. Eine doppelt verkettete Liste gibt jedem Knoten zusätzlich einen prev-Zeiger, sodass man rückwärts laufen und einen Knoten, den man schon hat, in einem Schritt löschen kann. Wer neben head auch einen tail-Zeiger führt, kann billig am Ende anfügen.

Im JavaScript-Alltag schreibst du selten eine verkettete Liste, weil Arrays gut optimiert sind und die Caches moderner Prozessoren Werte bevorzugen, die nebeneinander gespeichert sind. Die Idee zählt trotzdem: Bäume, Graphen und viele Bibliotheksstrukturen sind genau so aus Knoten und Zeigern gebaut.