Einfügen und Löschen an Positionen

Einfügen nach einem bekannten Knoten p: neuer Knoten bekommt p.next, danach zeigt p.next auf den neuen Knoten. Löschen des Nachfolgers von p: p.next = p.next.next.

Ohne Vorgängerknoten muss man von head aus suchen. Das macht Löschen in der Mitte $O(n)$.

Fehlerquelle: Reihenfolge der Zuweisungen. Wird p.next zu früh überschrieben, geht die alte Nachfolgerkette verloren.

Beispiel: Liste A-B-C. Einfügen von X nach A ergibt A-X-B-C.

Zyklus erkennen: Linked List Cycle [1].

Wo gebraucht

Wenn die Position schon als Knotenreferenz vorliegt, sind Einfügen und Löschen $O(1)$ Zeigerupdates. Genau deshalb nutzen Hash-Tabellen und Caches verkettete Buckets. Ohne Referenz bleibt die Suche $O(n)$; dann gewinnt ArrayList für wahlfreien Zugriff.

Vertiefung

Für eine Änderung an Position i benötigt eine einfach verkettete Struktur meist den Vorgänger. Einfügen verbindet zuerst den neuen Knoten mit dem bisherigen Nachfolger und danach den Vorgänger mit dem neuen Knoten. Diese Reihenfolge erhält die Erreichbarkeit.

Die eigentliche Verweisänderung ist lokal, doch das Finden der Position kostet linear viele Schritte. Eine bekannte Knotenreferenz kann daher einen konstanten Umbau erlauben, während dieselbe Operation über einen Index linear bleibt.

Kopfposition und leere Liste sind Sonderfälle, weil kein Vorgänger existiert. Ein Wächterknoten kann diese Fälle vereinheitlichen, fügt aber einen internen Knoten hinzu, der nicht als Nutzwert erscheinen darf.

Schwierigkeitsstufen

1. Verweise für Einfügen und Löschen korrekt umordnen.
2. Suchkosten von Umbaukosten trennen.
3. Einen Wächterknoten zur Vereinfachung der Randfälle einsetzen.

Fallstricke

Wird beim Einfügen zuerst der Vorgänger umgebogen, ohne den alten Nachfolger zu sichern, kann der Rest der Liste unerreichbar werden. Bei Positionen sind ausserdem Grenzen zwischen Knoten- und Lückenindizes zu beachten.