Welche Operation ist auf einer LinkedList schneller als auf einem Array?

Richtige Antwort: Am Anfang einfügen (prepend). prepend ist auf LinkedList O(1) — nur head umbiegen. Auf Array ist es O(n), weil alle Elemente nach rechts rutschen müssen. Index-Zugriff und append sind dagegen Array-Stärken.

Welche Komplexität hat Index-Zugriff (list[5]) auf einer LinkedList mit n Knoten?

Richtige Antwort: O(n). LinkedList hat KEINEN O(1)-Index-Zugriff, weil Knoten verteilt im Speicher liegen. Du musst von head aus durch alle Knoten wandern — bei Index 5 also 5 Schritte. Worst Case O(n).

Was ist der head einer LinkedList?

Richtige Antwort: Der erste Knoten (Einstiegspunkt). head ist die Referenz auf den ersten Knoten. Verlierst du head, ist die ganze Liste unerreichbar (Memory-Leak in Java/C, Garbage Collection in Python).

Was passiert im folgenden Code, wenn die Liste 5 Knoten hat?

Richtige Antwort: Druckt 5. Klassisches LinkedList-Idiom: durch alle Knoten wandern. Bei 5 Knoten zählt count bis 5, dann ist current.next null (am Ende), die Schleife endet. Druckt 5 — die Anzahl der Knoten.

Was unterscheidet eine doppelt verkettete Liste von einer einfach verketteten?

Richtige Antwort: Jeder Knoten hat zwei Pointer: next und prev. Doppelt verkettet (Doubly Linked List) bedeutet jeder Knoten kennt sowohl den Nachfolger (next) als auch den Vorgänger (prev). Vorteil: Rückwärts-Iteration und O(1) removeLast. Nachteil: mehr Speicher pro Knoten.

Du musst eine Million Mal am Anfang einer Liste einfügen. Welche Datenstruktur ist viel schneller?

Richtige Antwort: LinkedList. ArrayList: jede prepend-Operation ist O(n), bei wachsender Liste also O(n)-Operationen, insgesamt O(n²) für n prepends. LinkedList: jedes prepend ist O(1), insgesamt O(n) für n prepends. Bei 1 Million also 10⁶ vs 10¹² Operationen — Faktor eine Million.

Warum ist Java's LinkedList für append in O(1)?

Richtige Antwort: Sie ist intern doppelt verkettet und führt einen tail-Pointer. Java's LinkedList ist eine doppelt verkettete Liste mit head UND tail. Bei addLast() wird direkt am tail eingefügt — O(1). Eine einfach verkettete Liste ohne tail-Pointer wäre O(n) für append.

Welche Aussage über Speicher-Layout stimmt?

Richtige Antwort: LinkedList-Knoten liegen verteilt im Speicher, Array-Elemente liegen zusammenhängend. Array reserviert einen zusammenhängenden Speicherblock — daher O(1) Index-Zugriff (Adresse des n-ten Elements ist berechenbar). LinkedList-Knoten werden bei jedem Hinzufügen einzeln allokiert und liegen verteilt. Pointer halten sie zusammen.

UniProMax/Algorithmen/linked-list

Algorithmen·17 Min Lesezeit·Fortgeschritten

Verkettete Liste

Knoten mit Pointern statt zusammenhängendem Speicher. Prepend in O(1), Index-Zugriff in O(n) — die umgekehrte Stärke zum Array. Klausur-Klassiker.

Voraussetzungen:Arrays und Listen·Big-O Notation

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

LinkedList (Verkettete Liste)

Eine verkettete Liste ist eine Datenstruktur aus Knoten, von denen jeder seinen Wert plus einen Pointer auf den nächsten Knoten kennt. Dadurch kannst du am Anfang in O(1) einfügen und löschen, zahlst aber mit O(n) für den wahlfreien Zugriff per Index.

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: pro Knoten ein zusätzlicher Pointer

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.

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.

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

Den Wert (z.B. "Anna" oder "5")
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.

Im Bild	Im Code	Bedeutung
Schnitzeljagd-Zettel	Knoten / Node	ein Element in der Liste
Wert auf dem Zettel	value / data	der eigentliche Inhalt
Adresse zum nächsten	next	Pointer / Reference zum nächsten Knoten
Erster Zettel	head	Einstiegspunkt der Liste
Letzter Zettel	tail (optional)	letzter Knoten, sein next ist null

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

Operation	Array	LinkedList
Am Anfang einfügen (prepend)	O(n) — alle rutschen	O(1) — nur head umbiegen
Am Anfang entfernen (removeHead)	O(n) — alle rutschen	O(1) — head zeigt auf nächsten
Am Ende einfügen (append)	O(1)	O(n) — durch alle wandern
Index-Zugriff (get(5))	O(1)	O(n) — durch alle wandern
Suchen	O(n)	O(n)
Löschen an Position	O(n)	O(n)

Tausch der Stärken: Array ist gut am Ende und beim Index-Zugriff, LinkedList ist gut am Anfang.

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.

java// snippet

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

Java's LinkedList ist tatsächlich eine doppelt verkettete Liste mit head UND tail. Daher addLast() und removeFirst() in O(1).

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

java// snippet

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");
    }
}

Eigene LinkedList in 25 Zeilen. Klausur-Klassiker.

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.

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).

head ist der einzige Einstieg — verlierst du head, ist die ganze Liste weg (Speicher-Leak in Java/C, Garbage Collected in Python)
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

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).

Teil 1·Erklärung

Erklärung

LinkedList (Verkettete Liste)

Mehr aus Algorithmen

Algorithmen

Bubblesort

Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).

Algorithmen

Mergesort

Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.

Algorithmen

Quicksort

Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.

Was du danach lernen kannst

Folge-TopicBinärer SuchbaumAnschauen Folge-TopicGraphenAnschauen

LinkedList (Verkettete Liste)

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: pro Knoten ein zusätzlicher Pointer

Im Bild

Im Code

Bedeutung

Schnitzeljagd-Zettel

Knoten / Node

ein Element in der Liste

Wert auf dem Zettel

value / data

der eigentliche Inhalt

Adresse zum nächsten

next

Pointer / Reference zum nächsten Knoten

Erster Zettel

head

Einstiegspunkt der Liste

Letzter Zettel

tail (optional)

letzter Knoten, sein next ist null

Operation

Array

LinkedList

Am Anfang einfügen (prepend)

O(n) — alle rutschen

O(1) — nur head umbiegen

Am Anfang entfernen (removeHead)

O(n) — alle rutschen

O(1) — head zeigt auf nächsten

Am Ende einfügen (append)

O(1)

O(n) — durch alle wandern

Index-Zugriff (get(5))

O(1)

O(n) — durch alle wandern

Suchen

O(n)

Löschen an Position

O(n)

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

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"); } }

Verkettete Liste

LinkedList (Verkettete Liste)

Das Problem mit dem Array

Die Idee in einem Bild

Die Fachbegriffe

Was geht schneller, was langsamer?

Warum kein O(1) am Ende?

Warum kein O(1) Index-Zugriff?

So sieht's im Code aus

Eigene LinkedList implementieren

Wann LinkedList, wann Array?

Doppelt verkettete Liste (DLL)

Klausur-Tricks

Erklärung

LinkedList (Verkettete Liste)

Bubblesort

Mergesort

Quicksort

Verkettete Liste

LinkedList (Verkettete Liste)

Das Problem mit dem Array

Die Idee in einem Bild

Die Fachbegriffe

Was geht schneller, was langsamer?

Warum kein O(1) am Ende?

Warum kein O(1) Index-Zugriff?

So sieht's im Code aus

Eigene LinkedList implementieren

Wann LinkedList, wann Array?

Doppelt verkettete Liste (DLL)

Klausur-Tricks

Erklärung

LinkedList (Verkettete Liste)

Bubblesort

Mergesort

Quicksort

Das Problem mit dem Array

Die Idee in einem Bild

Die Fachbegriffe

Was geht schneller, was langsamer?

Warum kein O(1) am Ende?

Warum kein O(1) Index-Zugriff?

So sieht's im Code aus

Eigene LinkedList implementieren

Wann LinkedList, wann Array?

Doppelt verkettete Liste (DLL)

Klausur-Tricks

Interaktiv

LinkedList live

Quiz

Sortier-Vergleich

Lineare Suche

Binäre Suche