Einfach verkettete Liste und Knoten

In einer einfach verketteten Liste trägt jeder Knoten einen Wert und eine Referenz next auf den Nachfolger. Der Listenkopf head zeigt auf den ersten Knoten; das Ende hat next == null.

Einfügen am Anfang ist $O(1)$: neuer Knoten zeigt auf den alten head, head wird aktualisiert. Suche nach dem k-ten Element ist O(k), weil von vorne gelaufen werden muss.

Beispiel: head -> [A] -> [B] -> null. Nach Einfügen von C am Anfang: head -> [C] -> [A] -> [B] -> null.

Randfall: leere Liste (head == null) und einelementige Liste müssen beim Löschen separat behandelt werden.

Zeiger umdrehen: Reverse Linked List [1].

Wo gebraucht

Grundform für Hash-Chaining, Adjazenzlisten, Undo-Ketten und viele Lock-free Strukturen. In der JDK selten als öffentliche API, aber intern und in Systemcode ständig. Verständnis der Zeigerlogik überträgt sich auf Graphen und Bäume.

Vertiefung

Eine einfach verkettete Struktur besteht aus Knoten mit Nutzwert und Verweis auf den Nachfolger. Die Invariante verlangt, dass vom Kopf aus genau die enthaltenen Knoten erreichbar sind und die Kette schliesslich bei null endet.

Anfügen am Listenanfang ändert nur einen Verweis und ist unabhängig von der Listenlänge. Der Zugriff auf Position i erfordert dagegen das Folgen von i Verweisen. Die Struktur tauscht direkten Indexzugriff gegen lokale strukturelle Änderungen.

Knotenidentität und gespeicherter Wert sind verschieden. Zwei Knoten können gleiche Werte tragen und dennoch unterschiedliche Positionen und Nachfolger besitzen. Diese Unterscheidung ist für Löschen, Teilen und Zusammenführen wichtig.

Schwierigkeitsstufen

1. Knoten und Verweise einer kurzen Liste zeichnen.
2. Kopf-Einfügen und linearen Positionszugriff analysieren.
3. Erreichbarkeit als Repräsentationsinvariante formulieren.

Fallstricke

Beim Ersetzen des Kopfes geht die alte Kette verloren, wenn der alte Kopf nicht vorher als Nachfolger gespeichert wird. Wertgleichheit darf zudem nicht mit Knotenidentität verwechselt werden.