Wenn Arrays nicht reichen: Verkettete Listen als flexible Datenstruktur — Konzept, Implementierung und Anwendung in Python.
Eine verkettete Liste besteht aus Knoten — jeder Knoten speichert einen Datenwert und einen Zeiger auf den nächsten Knoten. Es gibt keinen zusammenhängenden Speicherblock.
Jeder Knoten ist ein Objekt mit zwei Feldern: dem Datenwert und dem Zeiger auf den Nachfolger.
[ data | next → ]
None am Ende)class Node mit den Attributen self.data und self.next.
Die Liste kennt nur den ersten Knoten (head). Der letzte Knoten hat next = None.
Einfach verkettet: jeder Knoten zeigt nur vorwärts. Doppelt verkettet: auch rückwärts.
[data|next→][←prev|data|next→]collections.deque ist intern eine doppelt verkettete Liste!
Wo ist die verkettete Liste schneller als ein Array — und wo langsamer?
Baue eine verkettete Liste Schritt für Schritt auf. Beobachte, wie sich die Zeiger-Verbindungen bei jeder Operation verändern.
Jetzt selbst ran: Vier Aufgaben mit Listen, Stack und Queue — ohne Klassen, nur mit dem, was du schon kennst.
Eine fertige verkettete Liste liegt als verschachteltes Dictionary vor. Schreibe Code, der alle Werte der Reihe nach ausgibt — genau wie der Visualizer oben.
Ein Stack ist perfekt für die Prüfung von Klammern. Ergänze die fehlenden Zeilen in der Funktion.
Simuliere eine Druckerwarteschlange. Dokumente werden hinten eingefügt und vorne gedruckt.
Wähle selbst: Implementiere entweder eine Browser-Verlauf-Simulation (Stack: zurück-Button) oder eine Ticketkasse (Queue: Kunden werden der Reihe nach bedient). Starte mit dem Grundgerüst.
Verkettete Listen sind die natürliche Grundlage für zwei wichtige abstrakte Datenstrukturen: Stack (LIFO) und Queue (FIFO).
Last In, First Out — wie ein Bücherstapel. Das zuletzt gelegte Buch wird zuerst genommen.
push(x) — Element oben drauflegen: O(1)pop() — Oberstes Element nehmen: O(1)peek() — Oberstes nur ansehen: O(1)First In, First Out — wie eine Warteschlange. Wer zuerst kommt, wird zuerst bedient.
enqueue(x) — Hinten anstellen: O(1)dequeue() — Vorne rausnehmen: O(1)peek() — Vorderstes ansehen: O(1)Pythons list kann beides — aber collections.deque ist effizienter für Queue.
s = []; s.append(x); s.pop()
Queue mit deque:from collections import deque
q = deque(); q.append(x); q.popleft()
list.pop(0) für Queue ist O(n) — deque.popleft() ist O(1)!
8 Fragen zu verketteten Listen, Stack und Queue — von Grundwissen bis kritischem Denken.
„In der Praxis sind Python-Listen fast immer schneller als selbst implementierte verkettete Listen — dank Cache-Optimierungen. Aber das Konzept dahinter ist die Grundlage für Bäume, Graphen und mehr."