Verkettete Listen: Aufbau und Laufzeiten

Ein Knoten ist ein einzelnes Speicherstück. Er enthält einen Wert, etwa eine Zahl, und gespeicherte Verweise. Ein Verweis, auch Zeiger genannt, zeigt auf einen anderen Knoten. Die Reihenfolge der Liste entsteht durch diese Verbindungen. Die Knoten müssen deshalb nicht auf benachbarten Speicherplätzen liegen.

Wir betrachten hier Listen mit Anfang und Ende, ohne Kreisverbindungen und ohne zusätzliche Hilfsknoten. Der besondere Verweiswert „NULL“ bedeutet: Hier wird auf keinen Knoten verwiesen. NULL ist kein zusätzlicher Knoten.

In einer einfach verketteten Liste enthält jeder Knoten einen Nachfolger-Verweis. Er zeigt auf den nächsten Knoten. Beim letzten Knoten hat dieser Verweis den Wert NULL. Von einem Knoten aus gibt es keinen eigenen Verweis zurück zu seinem Vorgänger.

In einer doppelt verketteten Liste enthält jeder Knoten zwei Verweise: einen zum Nachfolger und einen zum Vorgänger. Der Vorgänger-Verweis des ersten Knotens und der Nachfolger-Verweis des letzten Knotens haben den Wert NULL. So kannst du die Liste vorwärts und rückwärts durchlaufen. Der zweite Verweis braucht zusätzlichen Speicher in jedem Knoten.

Zur Verwaltung gehören gespeicherte Angaben über die ganze Liste. Dazu gehört der Startverweis auf den ersten Knoten. Er liegt außerhalb der einzelnen Knoten. Auch bei einer leeren Liste bleibt der Startverweis gespeichert; sein Wert ist dann NULL. Zusätzlich können ein Endverweis auf den letzten Knoten und die Anzahl der Knoten gespeichert werden.

Beim Einfügen und Löschen änderst du die Verbindungen zwischen Knoten. Die übrigen Knoten bleiben erhalten und behalten ihren Speicherplatz. Ihre Werte werden weder verschoben noch zwischen Knoten getauscht. Beim Löschen nehmen wir genau den gewählten Knoten heraus.

Willst du nach einem direkt bekannten Knoten einen neuen Knoten einfügen, ist dies eine sichere Reihenfolge: Zuerst lässt du den neuen Knoten auf den bisherigen Nachfolger zeigen. Danach lässt du den bekannten Knoten auf den neuen zeigen. So bleibt der bisherige Nachfolger erreichbar. Hatte der Nachfolger-Verweis des bekannten Knotens vorher den Wert NULL, wird der neue Knoten der letzte.

Beim Löschen aus einer einfach verketteten Liste lässt du den Vorgänger auf den Nachfolger des zu löschenden Knotens zeigen. Damit wird der zu löschende Knoten überbrückt. Bei einem Knoten nach dem ersten brauchst du dafür seinen Vorgänger. Beim Löschen des ersten Knotens setzt du stattdessen den Startverweis auf dessen Nachfolger.

Bei doppelter Verkettung musst du beide Richtungen pflegen. Beim Einfügen zwischen zwei Knoten zeigt der neue Knoten auf beide Nachbarn. Der vordere Nachbar zeigt vorwärts auf den neuen Knoten, der hintere rückwärts auf ihn. Ein innerer Knoten hat einen Vorgänger und einen Nachfolger. Beim Löschen eines solchen Knotens verbindest du seine beiden Nachbarn direkt miteinander: vorwärts und rückwärts.

Ändert sich der erste Knoten, passt du den Startverweis an. Ändert sich der letzte Knoten, passt du einen gespeicherten Endverweis an. Eine gespeicherte Anzahl steigt beim Einfügen um eins und sinkt beim Löschen um eins. Nach jeder Änderung gelten wieder die Regeln für Anfang und Ende aus dem Aufbau. Entfernst du den einzigen Knoten, ist die Liste leer: Startverweis und ein gespeicherter Endverweis haben den Wert NULL, die gespeicherte Anzahl ist 0.

Die Laufzeit beschreibt hier, wie die Zahl der Arbeitsschritte von der Listenlänge abhängt. Mit n bezeichnen wir die Anzahl der Knoten. Unser vereinfachtes Modell zählt das Lesen eines Werts sowie das Prüfen und Ändern eines Verweises als einzelne Schritte. Kleine Werte und Speicher für neue Knoten stehen bereit. Das ist ein Modell zum Vergleichen, keine Zeitmessung eines bestimmten Computers.

Die Schreibweise O(1) bedeutet: Eine feste Zahl begrenzt die nötigen Schritte, unabhängig von n. Es muss also nicht genau ein Schritt sein. Bei O(n) ist die Schrittzahl für wachsende Listen höchstens ein festes Vielfaches von n. Bei den hier betrachteten Suchvorgängen kann die Zahl der Schritte tatsächlich mit der Listenlänge wachsen.

Bei einer lokalen Änderung passt du die Verweise an der Einfüge- oder Löschstelle und nötige Verwaltungsangaben an. Lokales Einfügen und Löschen braucht O(1), wenn die nötigen Knoten direkt bekannt sind. Direkt bekannt heißt: Du hast bereits einen Verweis auf den Knoten und musst ihn nicht erst suchen. Bei der einfach verketteten Liste genügt zum Einfügen nach einem Knoten dessen Verweis. Zum Löschen eines Knotens nach dem ersten brauchst du den Vorgänger. Für Änderungen ganz vorn genügt der Startverweis.

Bei der doppelt verketteten Liste reicht zum Löschen der direkt bekannte zu löschende Knoten: Seine Verweise führen zu den Nachbarn. Auch direkt vor einem bekannten Knoten kannst du einfügen, weil sein Vorgänger-Verweis zurückführt. Das Anpassen gespeicherter Verwaltungsangaben braucht dabei ebenfalls eine von der Listenlänge unabhängige Zahl von Schritten.

Wir nehmen keine bestimmte Ordnung der Werte an. Suchst du vom Start aus einen Wert, musst du im ungünstigsten Fall alle n Knoten prüfen, etwa wenn der Wert fehlt. Das hat den Aufwand O(n), auch bei doppelter Verkettung. Musst du vor einer Änderung erst die Einfügestelle oder den Vorgänger suchen, kann deshalb der gesamte Vorgang O(n) brauchen.

Ein Array speichert Werte auf aufeinanderfolgenden Plätzen. Jeder Platz hat eine Nummer, den Index. Hier beginnen die Indizes bei 0: Der erste Platz hat Index 0, der zweite Index 1 und der dritte Index 2. Ein gültiger Index bezeichnet hier einen belegten Platz.

Beim Array lässt sich der Speicherplatz aus einem gültigen Index direkt bestimmen. Der Zugriff braucht im betrachteten Modell O(1). Eine verkettete Liste speichert dagegen nicht für jeden Index einen eigenen direkten Verweis. Um einen Platz über seinen Index zu erreichen, kannst du vom Start aus den Nachfolger-Verweisen folgen. Bei doppelter Verkettung und bekanntem Ende kannst du auch vom Ende aus rückwärts gehen. Im ungünstigsten Fall wächst die Zahl der nötigen Schritte mit der Listenlänge. Der Zugriff braucht dann O(n), wobei n die Anzahl der gespeicherten Werte ist. Zwei Verweise pro Knoten ändern an diesem ungünstigsten Fall nichts.

Für das Einfügen betrachten wir ein Array mit genügend freiem Platz. Die belegten Plätze folgen von vorn lückenlos aufeinander; freier Platz liegt am Ende. Fügst du vorn ein, müssen alle bisherigen Werte einen Platz weiterrücken. Im ungünstigsten Fall braucht das O(n). Beim Einfügen am Ende mit freiem Platz müssen dagegen keine vorhandenen Werte verschoben werden.

Eine verkettete Liste kann beim häufigen Einfügen im Inneren passen, wenn die nötigen Knotenverweise schon bekannt sind. Dann änderst du Verweise, statt vorhandene Werte zu verschieben. Soll vor einem bekannten inneren Knoten eingefügt werden, hilft die doppelte Verkettung: Der Vorgänger ist direkt erreichbar. Bei einfacher Verkettung müsstest du ihn ohne eigenen Verweis erst suchen.

Werden häufig Werte an wechselnden Indizes gelesen, passt ein Array gut. Entscheidend ist also, welche Vorgänge häufig vorkommen und welche Verweise bereits vorliegen. Eine verkettete Liste ist nicht bei jeder Aufgabe schneller.