Datenstrukturen I (Linear)
Die einfachsten Arten, Daten zu ordnen — Reihen, Stapel und Schlangen.
Du hast gelernt, die Geschwindigkeit von Algorithmen mit Big-O zu messen. Jetzt stellt sich die Frage: Wo liegen die Daten eigentlich? Die Antwort — zusammenhängende Speicherblöcke, verstreute Zeigerketten oder zugriffsbeschränkte Stacks und Queues — entscheidet, welche Operationen schnell sind und welche langsam.
Diese vier linearen Strukturen sind das Fundament jedes datenintensiven Programms, von Tabellenkalkulationen bis zu neuronalen Netzen. Dieser Artikel macht ihre Abwägungen greifbar.
Arrays — Zusammenhängender Speicher mit Index-Zugriff
Definition
Array
Analogie
Beispiel
Definition
Beispiel: Python-Listen-Operationen
lst = [10, 20, 30, 40, 50]
lst[3] # → 40 O(1) Index-Zugriff
lst.insert(2, 25) # → [10, 20, 25, 30, 40, 50] O(n)
lst.append(60) # → [..., 60] amortisiert O(1)
30 in lst # → True O(n) lineare SucheKomplexitätstabelle: Array
Operation Komplexität
──────────────────────────────
Zugriff (Index) O(1)
Update (Index) O(1)
Anhängen amortisiert O(1)
Einfügen/Löschen O(n)
Suche O(n)Achtung
Irrtum: Pythons list ist eine Linked List
Pythons list ist intern ein dynamisches Array mit O(1)-Index-Zugriff — der Name ist irreführend. Eine echte Linked List hat keine Indexarithmetik und braucht O(n) Durchlauf, um Element k zu erreichen. Damit unterschiedlich große Elemente (wie Text und Zahlen) in dieselbe Liste passen, speichert Python intern nur gleich große Verweise (Pointer) auf die eigentlichen Daten.
Wenn ein dynamisches Array voll ist, allokiert es einen neuen, größeren Block (im Lehrbuchfall mit doppelter Kapazität) und kopiert alle Elemente. Diese Vergrößerung kostet O(n), passiert aber selten genug, dass die amortisierten Kosten pro Anhängen bei O(1) liegen. Pythons list nutzt dieselbe Idee, wächst aber jeweils nur um etwa ein Achtel.
# Kapazitätsverdopplung (vereinfacht)
Kapazität: 4 → voll → neue Kapazität: 8
→ voll → neue Kapazität: 16
# 1000 Anhänge-Operationen:
# ~8 Vergrößerungen, Rest schreibt direkt
# → amortisiert O(1) pro append()Linked Lists — Verstreute Knoten mit Zeigern
Definition
Linked List
Analogie
Beispiel
Definition
Beispiel: Einfügen bei Position 500.000
Ein Array mit 1.000.000 Elementen: Einfügen bei Position 500.000 erfordert das Verschieben von ~500.000 Elementen → O(n). Eine Linked List mit Zeiger auf Position 499.999: Zwei Zeiger umschreiben → O(1). Aber: Das Finden von Position 499.999 vom Kopf aus kostet O(n) Durchlauf. Der Gesamtaufwand ist also ebenfalls O(n), es sei denn, man hat bereits eine Referenz auf die Stelle.
Varianten: Einfach vs. Doppelt verkettet
Eine einfach verkettete Liste hat Zeiger nur in eine Richtung (vorwärts). Eine doppelt verkettete Liste hat zusätzlich Rückwärts-Zeiger, was das Löschen und Rückwärtsnavigieren effizienter macht. Pythons collections.deque nutzt eine doppelt verkettete Struktur für O(1)-Operationen an beiden Enden.
Komplexitätstabelle: Linked List
Operation Komplexität
──────────────────────────────────────────
Zugriff (Position k) O(n)
Suche O(n)
Einfügen/Löschen am Kopf O(1)
Einfügen an bekannter Pos. O(1)
Einfügen nach Suche O(n)Achtung
Irrtum: Linked Lists sind immer besser
Die O(1)-Einfügung gilt nur, wenn man bereits einen Zeiger auf die Einfügestelle hat. In den meisten realen Szenarien muss man erst suchen (O(n)), und Arrays haben bessere Cache-Lokalität — was sie für viele Arbeitslasten trotz teurer Mitteneinfügung schneller macht.
Linked Lists entstanden in den 1950er Jahren aus früher KI-Forschung. Newell, Shaw und Simon entwickelten IPL (Information Processing Language, um 1956), die Linked Lists als Kernstruktur nutzte. John McCarthy machte Linked Lists mit LISP (1958) zur Grundlage funktionaler Programmierung.
Stacks und Queues — Zugriffsprinzipien
Definition
Stack & Queue
Analogie
Beispiel
Definition
Beispiel: Der Call Stack
- 1. main() wird aufgerufen → Stack: [main]
- 2. processData() wird aufgerufen → Stack: [main, processData]
- 3. calculate() wird aufgerufen → Stack: [main, processData, calculate]
- 4. calculate() gibt zurück → Stack: [main, processData]
- 5. processData() gibt zurück → Stack: [main]
Funktionsaufrufe werden als Stack-Frames verwaltet: Jeder neue Aufruf wird oben draufgelegt (push), und wenn eine Funktion zurückkehrt, wird ihr Frame entfernt (pop). Das ist exakt LIFO. Bei zu tiefer Rekursion (z.B. fib(100000) ohne Optimierung) läuft der Stack über — ein Stack Overflow.
Beispiel: Webserver-Warteschlange
Ein Webserver empfängt 1.000 Anfragen pro Sekunde. Worker-Threads nehmen Anfragen in Eingangsreihenfolge aus der Queue und verarbeiten sie. FIFO stellt sicher, dass keine Anfrage verhungert — wer zuerst kommt, wird zuerst bedient.
Achtung
Irrtum: Ein Stack ist eine Art Array
Ein Stack ist ein Nutzungsprinzip (LIFO-Vertrag), das auf einem Array, einer Linked List oder jeder anderen Struktur implementiert werden kann. Das Prinzip definiert, welche Operationen erlaubt sind (nur push/pop), nicht wie die Daten physisch gespeichert werden.
Jeder Funktionsaufruf erzeugt einen Stack Frame mit lokalen Variablen und Rücksprungadresse. Python hat ein Standard-Rekursionslimit von ~1.000 Frames. Wird dieses überschritten, löst Python einen RecursionError aus, der das Programm abbricht, wenn ihn niemand abfängt — Pythons Schutz vor dem berühmten Stack Overflow.
import sys
print(sys.getrecursionlimit()) # → 1000
def endlos(n):
return endlos(n + 1)
endlos(0) # RecursionError: maximum recursion depth exceededFriedrich Bauer und Klaus Samelson formalisierten den Stack 1957 an der damaligen TH München (heute TU München) für die Auswertung arithmetischer Ausdrücke. Agner Krarup Erlang begründete die Warteschlangentheorie 1909 für die Analyse von Telefonnetzen — seine Arbeit bildet die Grundlage moderner Netzwerkdesigns.
Array vs. Linked List — Der Vergleich
Zusammenhängender Speicher. O(1) Index-Zugriff, O(n) Einfügen/Löschen. Gute Cache-Lokalität. Ideal wenn Lesen häufiger ist als Einfügen.
Verstreute Knoten mit Zeigern. O(n) Zugriff, O(1) Einfügen an bekannter Position. Kein Cache-Vorteil. Ideal wenn häufig an bekannten Stellen eingefügt/gelöscht wird.
Komplexitätsvergleich aller Strukturen
Interaktiv: Komplexitäts-Matrix
Klicke auf eine Datenstruktur, um ihre Stärken und Schwächen zu sehen. Achte auf das Farbmuster: Grün bedeutet O(1) — die Operation ist unabhängig von der Datenmenge blitzschnell. Rot bedeutet O(n) — die Laufzeit wächst linear mit der Anzahl der Elemente.
Operationen nach Datenstruktur
Zeile anklicken für Detailansicht
| Struktur | Zugriff (Index) | Suche | Einfügen | Löschen |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
Merke
Das Wichtigste auf einen Blick
- Arrays bieten günstiges Lesen (O(1) Index) gegen teures Einfügen in der Mitte (O(n)) — wähle sie, wenn du viel häufiger liest als einfügst.
- Linked Lists bieten günstiges lokales Bearbeiten (O(1) Zeiger umschreiben) gegen teures Durchlaufen (O(n)) — wähle sie, wenn Einfügen/Löschen an bekannten Positionen dominiert.
- Stacks (LIFO) und Queues (FIFO) sind Nutzungsverträge, keine Speichertypen — sie beschränken den Zugriff und ermöglichen so mächtige Muster wie Rückgängig, Rekursion und faire Planung.
Prüfen
Quiz: Lineare Datenstrukturen
Was ist der zentrale Unterschied zwischen einem Array und einer Linked List?
Wähle eine Antwort
1. Was ist der zentrale Unterschied zwischen einem Array und einer Linked List?
2. Du hast eine Liste mit 1.000.000 Einträgen und musst häufig in der Mitte einfügen. Welche Struktur ist geeigneter?
3. Ein Webserver muss eingehende Anfragen fair bearbeiten — wer zuerst kommt, wird zuerst bedient. Welches Prinzip sollte er nutzen?
4. Pythons list heißt 'list', ist aber intern ein dynamisches Array. Warum ist diese Unterscheidung wichtig?
Prüfen
Lernziele
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen