LinkedList (Verkettete Liste)

Eine verkettete Liste ist eine Datenstruktur aus Knoten, von denen jeder seinen Wert plus einen Pointer/Referenz (in Java/Python eher als Referenz, in C/C++ als Pointer) auf den nächsten Knoten kennt. Anders als beim Array, wo alles zusammenhängend im Speicher liegt, sind LinkedList-Knoten überall im Heap verstreut. Du lernst hier die Vor-/Nachteile gegenüber Arrays (Insertion am Anfang O(1) bei LinkedList vs O(n) bei Array; Indexzugriff O(1) bei Array vs O(n) bei LinkedList), die Unterschiede zwischen Singly Linked List (nur next), Doubly Linked List (next + prev) und Java's LinkedList (doppelt-verkettete Implementierung), wie Pointer-Umbiegungen bei prepend/insertAfter/deleteHead aussehen, warum Append am Ende ohne Tail-Referenz O(n) kostet (mit Tail wieder O(1)), und warum man in Klausuren mit eigener MyLinkedList-Implementierung statt Bibliotheks-Klassen üben sollte.

Die Klausur-relevanten Eigenschaften:

• Singly Linked List: jeder Knoten kennt nur den Nachfolger
• Doubly Linked List: jeder Knoten kennt Vorgänger und Nachfolger, dadurch O(1) Löschen wenn man den Knoten kennt
• Einfügen am Kopf: O(1), nur Pointer umhängen
• Suchen / Zugriff per Index: O(n), durch die Liste laufen
• Speicher-Overhead: Singly Linked List = ein zusätzlicher next-Pointer pro Knoten. Doubly Linked List = zwei Pointer (next + prev) plus Node-Objekt-Overhead je nach Sprache/Runtime. Java LinkedList ist doppelt verkettet.

In Klausuren wirst du oft gefragt: zeichne den Pointer-Zustand nach Einfügen/Löschen oder vergleiche LinkedList mit Array nach Komplexitätsklassen. Faustregel: oft am Anfang einfügen, selten per Index zugreifen → LinkedList. Sonst Array.

Das Problem mit dem Array

Du hast schon Arrays/Listen kennengelernt. Sie sind super, aber:

• Am Ende anhängen: schnell ✅
• Am Anfang einfügen: langsam ❌, alle anderen Elemente müssen eine Position nach rechts rutschen
• Größe muss vorher reserviert werden (statisch) oder das Array muss intern neu kopiert werden, wenn es voll ist (dynamisch)

Was wenn du oft am Anfang Sachen einfügen willst und die Größe nicht vorher kennst? Dann gibt es eine andere Idee.

Die Idee in einem Bild

Stell dir eine Schnitzeljagd vor: jeder Hinweis-Zettel hat zwei Sachen drauf:

1. Den Wert (z.B. "Anna" oder "5")
2. Eine Adresse, wo der nächste Zettel zu finden ist

[ 5 | →📍 ] → [ 8 | →📍 ] → [ 3 | →📍 ] → [ 9 | null ]
   ↑
  head

head ist der Start, die Adresse des ersten Zettels. Der letzte zeigt auf null (nichts mehr danach).

Du brauchst keinen zusammenhängenden Speicher. Jeder Zettel kann irgendwo liegen, solange er weiß, wo der nächste hängt.

Das ist eine LinkedList. Auf Deutsch: verkettete Liste.

Die Fachbegriffe

Was geht schneller, was langsamer?

Hier wird's spannend. Vergleich zwischen Array (ArrayList) und LinkedList:

Komplementäre Stärken: Array dominiert beim Indexzugriff und bei Append (amortisiert O(1) bei dynamischen Arrays); eine doppelt verkettete Liste mit Tail-Referenz dominiert bei Prepend und beim Einfügen/Löschen an einer bekannten Knoten-Referenz (O(1)).

Warum kein O(1) am Ende?

Weil die LinkedList nur weiß, wo der erste Knoten ist (head). Um zum Ende zu kommen, muss sie von head aus jeden next-Pointer einmal verfolgen. Bei 1.000 Knoten: 1.000 Schritte.

Optimierung: man kann zusätzlich einen tail-Pointer mitführen, dann ist append auch O(1). Aber Standard-Implementierungen haben das oft nicht.

Warum kein O(1) Index-Zugriff?

Bei list[5] wüsste die LinkedList nicht direkt wo Knoten 5 ist, die Knoten sind im Speicher verstreut. Sie muss von head aus 5x dem next-Pointer folgen.

Im Array dagegen liegen alle Elemente direkt hintereinander im Speicher. arr[5] ist ein einzelner Speicher-Sprung.

So sieht's im Code aus

import java.util.LinkedList;

LinkedList<Integer> liste = new LinkedList<>();

// Am Anfang einfügen, O(1)
liste.addFirst(5);     // [5]
liste.addFirst(8);     // [8, 5]
liste.addFirst(3);     // [3, 8, 5]

// Am Ende einfügen, O(1) wenn tail-Pointer da
liste.addLast(9);      // [3, 8, 5, 9]

// Vom Anfang entfernen, O(1)
int first = liste.removeFirst();  // 3, Liste: [8, 5, 9]

// Suchen, O(n)
boolean hat = liste.contains(5);  // true

int size = liste.size();          // 3

from collections import deque

# Python hat keine eingebaute SinglyLinkedList.
# deque (double-ended queue) kommt am nächsten dran:
liste = deque()

# Am Anfang einfügen, O(1)
liste.appendleft(5)    # deque([5])
liste.appendleft(8)    # deque([8, 5])
liste.appendleft(3)    # deque([3, 8, 5])

# Am Ende einfügen, O(1)
liste.append(9)        # deque([3, 8, 5, 9])

# Vom Anfang entfernen, O(1)
first = liste.popleft()  # 3

# Suchen, O(n)
hat = 5 in liste

size = len(liste)

Eigene LinkedList implementieren

In der Klausur wird oft gefragt, die LinkedList selbst zu schreiben. Das ist nicht schwer:

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
        this.next = null;
    }
}

class MyLinkedList {
    Node head;

    void prepend(int value) {
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode;
    }

    void printAll() {
        Node current = head;
        while (current != null) {
            System.out.print(current.value + " → ");
            current = current.next;
        }
        System.out.println("null");
    }
}

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class MyLinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def print_all(self):
        current = self.head
        while current is not None:
            print(current.value, "→ ", end="")
            current = current.next
        print("null")

Wann LinkedList, wann Array?

LinkedList nehmen wenn:

• Du oft am Anfang einfügst oder entfernst
• Du oft an mittlerer Position einfügst und schon weißt wo (mit Pointer auf den Knoten)
• Du keine Index-Zugriffe brauchst

Array (ArrayList) nehmen wenn:

• Du per Index zugreifst (list[5])
• Du am Ende anhängst (was die häufigste Operation ist)
• Du wenig einfügst oder löschst, viel liest

In der Praxis: ArrayList wird viel häufiger genutzt. LinkedList ist die "akademisch wichtige" Datenstruktur, die in Klausuren gefragt wird, in echtem Code aber selten ist.

Doppelt verkettete Liste (DLL)

Variante: jeder Knoten hat zwei Pointer, next und prev. Dann kann man auch rückwärts durch die Liste laufen.

null ← [ 5 | ↔ ] ↔ [ 8 | ↔ ] ↔ [ 3 | ↔ ] ↔ [ 9 ] → null

Java's LinkedList ist intern doppelt verkettet. Vorteil: removeLast in O(1) (sonst müsste man von head zum Ende wandern, um den Vorgänger des letzten Knotens zu finden).

Klausur-Tricks

• head ist der einzige Einstieg, verlierst du head, ist die Liste logisch nicht mehr erreichbar. In Java und Python werden die Knoten später durch Garbage Collection freigegeben. In C/C++ kann das ein echter Memory Leak sein, wenn vorher nicht freigegeben wurde.
• null-Check beim Durchlaufen: while (current != null), sonst NullPointerException
• prepend ist O(1), wenn dir das nicht klar ist, klick im Visualizer durch
• append ist O(n) ohne tail-Pointer, O(1) mit
• Index-Zugriff ist niemals O(1) in einer LinkedList
• Typische Klausur-Falle: vergessen, head zu aktualisieren bei prepend oder deleteHead führt zu Memory-Leak in C/C++ oder NullPointerException beim nächsten Zugriff in Java

LinkedList live

Beobachte wie die Operationen funktionieren, die orangefarbene Wanderung zeigt, durch wie viele Knoten der Algorithmus wirklich gehen muss.

Probier folgendes:

• prepend: blitzschnell, egal wie lang die Liste, O(1)
• append: orange Wanderung durch alle Knoten bis Ende, O(n)
• insertAt(2): orange Wanderung bis Position 2, dann einfügen
• find auf Wert: wandert vorwärts bis Treffer (oder bis Ende)
• prepend vs append im Vergleich: derselbe Effekt, aber massiver Aufwand-Unterschied bei langen Listen

Faustregel zum Mitnehmen: LinkedList ist umgekehrt zu Array. Array ist stark bei Indexzugriff und meist stark beim Anhängen (amortisiert O(1) bei dynamischen Arrays). Eine einfach verkettete Liste ohne tail ist schlecht beim Anhängen (O(n)); mit tail-Pointer ist Anhängen ebenfalls O(1). Indexzugriff bleibt aber immer O(n).

Hinweis zur Visualisierung: Diese Animation zeigt eine einfach verkettete Liste ohne tail-Pointer, daher die orange Wanderung beim append. Java LinkedList ist doppelt verkettet mit head und tail, dort ist append O(1).

In der Praxis ist Array meist die richtige Wahl. Aber wenn deine Hauptoperation prepend ist, kann LinkedList plötzlich um Größenordnungen schneller sein.

---

Code-Stepper: prepend, append, insertAt(2) als Pointer-Trace

Hier siehst du was bei Listen-Operationen wirklich passiert: Pointer-Umhängen statt Speicher-Verschiebung. Wir starten mit Liste 5 → 9 und führen drei Operationen aus. Beachte den Unterschied bei append (Wanderung durch alle Knoten bis curr.next == null) gegenüber prepend (nur head umhängen).