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)

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 (Insertion am Anfang bei LinkedList vs bei Array; Indexzugriff bei Array vs bei LinkedList), die Unterschiede zwischen (nur ), ( + ) und (doppelt-verkettete Implementierung), wie bei // aussehen, warum Append am Ende ohne kostet (mit Tail wieder ), und warum man in Klausuren mit eigener -Implementierung statt Bibliotheks- üben sollte.

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)

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.

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 (ArrayList)

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)

amortisiert O(1) (Resize gelegentlich O(n))

O(n) ohne tail / O(1) mit tail

Index-Zugriff (get(5))

O(1)

O(n), durch alle wandern

Suchen nach Wert

O(n)

Löschen an Index

O(n)

O(n), Suche bis dort hin

Löschen eines bekannten Knotens

O(n) bei ArrayList

O(1) bei DLL (mit Referenz auf den Knoten)

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.

Erklärung

LinkedList (Verkettete Liste)

Verkettete Liste.

Erklärung

LinkedList (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

LinkedList live

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

Wenn du fertig bist: jetzt üben.

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

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

Quiz