Listenstrukturen

Arrays speichern Elemente in einem zusammenhängenden Speicherblock. Die Reihenfolge ist implizit durch die Speicherposition gegeben. Verkettete Listen speichern Elemente verstreut im Speicher. Die Reihenfolge wird explizit durch Referenzen (Zeiger) auf das jeweils nächste Element hergestellt. Beispiel: Array [1,2,3] liegt an Adressen 100, 104, 108. Liste 1->2->3 könnte an 100 (next->500), 500 (next->200), 200 (next->null) liegen.

1. Effizienter Index-Zugriff: O(1) für Zugriff auf das i-te Element (Random Access). 2. Speichereffizienz: Kein Overhead für Zeiger pro Element (nur Nutzdaten). 3. Cache-Freundlichkeit: Bessere Lokalität durch zusammenhängenden Speicher. Beispiel: array[500] ist eine einfache Speicheradressberechnung. Bei einer Liste müsste man 500 Zeiger verfolgen (O(N)).

1. Dynamische Größe: Speicher wird nach Bedarf allokiert, keine Umkopieraktionen bei Wachstum nötig. 2. Effizientes Einfügen/Löschen: O(1), wenn die Position (Referenz) bereits bekannt ist (kein Verschieben von Nachfolgern nötig). Beispiel: Einfügen am Anfang einer Liste ist immer O(1). Beim Array ist es O(N), weil alle Elemente verschoben werden müssen.

Ein Knoten besteht aus zwei Teilen: 1. Nutzdaten (payload): Der eigentliche Wert (z.B. int, String). 2. Nachfolger-Referenz (next): Verweis auf den nächsten Knoten oder null beim letzten Element. Beispiel (Java): class Node { int payload

1. Nur Vorwärts-Traversierung: Man kann nicht effizient zum Vorgänger zurückgehen. 2. Löschen ist aufwendig: Um einen Knoten zu löschen, braucht man Zugriff auf den Vorgänger, was O(N) Suche erfordert (außer man hat diesen bereits). 3. Zugriff am Ende: Ohne separaten tail-Zeiger ist Einfügen am Ende O(N). Beispiel: Um das vorletzte Element zu finden, muss man vom Kopf aus die ganze Liste durchlaufen.

1. Neuen Knoten erzeugen. 2. next-Zeiger des neuen Knotens auf den aktuellen Listenanfang (head) setzen. 3. head-Referenz auf den neuen Knoten umbiegen. Laufzeit: O(1). Beispiel: Liste: head -> [A], Neu: [B]. 1. [B].next = head (zeigt auf A). 2. head = [B]. Ergebnis: head -> [B] -> [A].

Basisfall: Wenn Liste leer (head == null), gib neuen Knoten zurück. Rekursionsschritt: Setze head.next = addLast(head.next, value) und gib head zurück. Die Rekursion läuft bis zum Ende durch und verknüpft beim Rücklauf die Elemente neu (bzw. bestätigt die Verknüpfung). Laufzeit: O(N) (da bis zum Ende abgestiegen werden muss). Speicher: O(N) Stack-Tiefe.

Basisfall: Wenn Liste leer, passiert nichts (return null). Treffer: Wenn head.payload gleich dem gesuchten Wert ist, gib head.next zurück (überspringe aktuellen Knoten). Rekursion: Setze head.next = remove(head.next, value) und gib head zurück. Beispiel: Um B aus A->B->C zu löschen: A.next wird das Ergebnis von remove(B). Da B der Treffer ist, gibt remove(B) C zurück. A.next zeigt nun auf C.

Jeder Knoten hat zwei Referenzen: 1. next: Zeigt auf Nachfolger. 2. prev: Zeigt auf Vorgänger. Zusätzlich speichert die Liste oft Referenzen auf head (Anfang) und tail (Ende). Vorteil: Bidirektionale Traversierung, Löschen eines Knotens in O(1) möglich (wenn Referenz auf Knoten bekannt), Zugriff auf Ende in O(1). Nachteil: Höherer Speicherbedarf pro Knoten (zwei Zeiger).

Ein Dummy-Element ist ein leeres Knotenelement am Anfang (und oft auch Ende) der Liste, das keine echten Daten enthält. Zweck: Es vereinfacht die Implementierung, indem Sonderfälle für 'leere Liste' oder 'Einfügen am Anfang/Ende' vermieden werden. Jeder echte Knoten hat somit immer garantiert einen Vorgänger und Nachfolger. Beispiel: Leere Liste mit Dummies: [DummyHead] <-> [DummyTail]. Einfügen passiert immer zwischen zwei existierenden Knoten.

1. addLast(): Einfügen am Ende (kein Durchlaufen nötig). 2. removeLast(): Löschen am Ende (direkter Zugriff via tail und prev). 3. getLast(): Zugriff auf das letzte Element. Vergleich: Bei einfach verketteter Liste (ohne Tail) wären diese Operationen O(N).

Array: O(1) (direkte Adressberechnung). Verkettete Liste: O(N) (man muss i Zeiger vom Start aus verfolgen).

Verkettete Liste: O(1) (nur Zeiger umbiegen). Array: O(N) (alle existierenden Elemente müssen um eine Position nach rechts verschoben werden, um Platz zu machen).

Beide O(N). Man muss in beiden Fällen im Worst Case alle Elemente durchlaufen, bis der Wert gefunden wird oder das Ende erreicht ist.

Eine Liste ist rekursiv definiert: Eine Liste ist entweder 1. leer (null) oder 2. besteht aus einem Kopf (Nutzdaten) und einer Restliste (wieder eine Liste). Code-Muster: Methoden rufen sich selbst auf der Restliste (next) auf, bis der Basisfall (leer) erreicht ist.

Wegen des Stack Overflows. Jeder rekursive Aufruf belegt Speicher auf dem Call-Stack. Bei Listen mit zehntausenden Elementen ist der Stack schnell erschöpft. Iterative Lösungen nutzen den Heap und sind daher für große Datenmengen in Java robuster.

Man nutzt drei Zeiger: prev, current, next. In einer Schleife: 1. Speichere current.next temporär. 2. Setze current.next auf prev (Richtung umdrehen). 3. Rücke prev auf current und current auf das gespeicherte next vor. Am Ende wird head auf prev gesetzt. Laufzeit: O(N).