Die einfachsten Arten, Daten zu sortieren — Reihen, Stapel und Schlangen.
Grundlagen 14 min Einsteiger 3. Mai 2026
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
Array
AnalogieDefinition
Stell dir einen Eierkarton mit 12 nummerierten Fächern (0 bis 11) vor. Du greifst direkt zu Fach 7, ohne Fächer 0 bis 6 zu prüfen — das ist O(1)-Zugriff. Um ein Ei bei Fach 3 einzufügen, wenn alle Fächer belegt sind, musst du Eier 3 bis 11 um eine Position nach rechts schieben — das ist O(n). Brauchst du ein 13. Ei, brauchst du einen größeren Karton und musst alles umziehen — analog zur Array-Vergrößerung.
Beispiel
Im echten Karton könnte man ein Ei zwischen Fächer quetschen — im Speicher müssen Elemente zusammenhängend ohne Lücken liegen. Außerdem modelliert der Karton die dynamische Größenanpassung (geometrisches Wachstum) nicht.
Analogie:
Stell dir einen Eierkarton mit 12 nummerierten Fächern (0 bis 11) vor. Du greifst direkt zu Fach 7, ohne Fächer 0 bis 6 zu prüfen — das ist O(1)-Zugriff. Um ein Ei bei Fach 3 einzufügen, wenn alle Fächer belegt sind, musst du Eier 3 bis 11 um eine Position nach rechts schieben — das ist O(n). Brauchst du ein 13. Ei, brauchst du einen größeren Karton und musst alles umziehen — analog zur Array-Vergrößerung.
Beispiel
Im echten Karton könnte man ein Ei zwischen Fächer quetschen — im Speicher müssen Elemente zusammenhängend ohne Lücken liegen. Außerdem modelliert der Karton die dynamische Größenanpassung (geometrisches Wachstum) nicht.
Definition:
Ein Array speichert Elemente in einem zusammenhängenden Speicherblock, wobei jedes Element gleich groß ist. Der Computer berechnet die Adresse von Element i als Basisadresse + i × Elementgröße, was Index-Zugriff zu O(1) macht. Das Einfügen in der Mitte erfordert das Verschieben aller nachfolgenden Elemente → O(n). Dynamische Arrays (Pythons list, Javas ArrayList) wachsen durch Überallokation und Kapazitätsverdopplung, was Anhängen amortisiert O(1) macht.
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.
Deep Dive: Dynamische Arrays
Wenn ein dynamisches Array voll ist, allokiert es einen neuen Block mit doppelter Kapazität und kopiert alle Elemente. Diese Vergrößerung kostet O(n), passiert aber selten genug, dass die amortisierte Kosten pro Anhängen bei O(1) liegen. Pythons list nutzt genau diese Strategie.
# Kapazitätsverdopplung (vereinfacht)
Kapazität: 4 → voll → neue Kapazität: 8
→ voll → neue Kapazität: 16
# 1000 Anhänge-Operationen:
# ~10 Vergrößerungen, Rest schreibt direkt
# → amortisiert O(1) pro append()
Linked Lists — Verstreute Knoten mit Zeigern
Linked List
AnalogieDefinition
Stell dir eine Schnitzeljagd vor. Jeder Hinweiszettel verrät dir, wo der nächste versteckt ist. Um Zettel 5 zu finden, musst du bei Zettel 1 starten und jedem Hinweis der Reihe nach folgen — O(n). Um einen neuen Zettel zwischen Zettel 2 und 3 einzufügen, schreibst du einfach die Wegbeschreibung auf Zettel 2 um — kein anderer Zettel muss sich bewegen (O(1), wenn du Zettel 2 bereits in der Hand hältst).
Beispiel
Bei einer echten Schnitzeljagd variiert die Laufzeit zwischen Stationen; im Speicher dauert das Folgen eines Zeigers annähernd gleich lang. Die Analogie zeigt auch nicht den zusätzlichen Speicherbedarf für den Zeiger in jedem Knoten (Overhead).
Analogie:
Stell dir eine Schnitzeljagd vor. Jeder Hinweiszettel verrät dir, wo der nächste versteckt ist. Um Zettel 5 zu finden, musst du bei Zettel 1 starten und jedem Hinweis der Reihe nach folgen — O(n). Um einen neuen Zettel zwischen Zettel 2 und 3 einzufügen, schreibst du einfach die Wegbeschreibung auf Zettel 2 um — kein anderer Zettel muss sich bewegen (O(1), wenn du Zettel 2 bereits in der Hand hältst).
Beispiel
Bei einer echten Schnitzeljagd variiert die Laufzeit zwischen Stationen; im Speicher dauert das Folgen eines Zeigers annähernd gleich lang. Die Analogie zeigt auch nicht den zusätzlichen Speicherbedarf für den Zeiger in jedem Knoten (Overhead).
Definition:
Eine Linked List speichert Elemente in Knoten, die über den Speicher verstreut sind. Jeder Knoten enthält einen Wert und einen Zeiger (Pointer) auf den nächsten Knoten. Es gibt keine Indexarithmetik — um Element k zu erreichen, folgt man k−1 Zeigern vom Kopf der Liste → O(k). Der Vorteil: Einfügen oder Löschen an einer bekannten Position erfordert nur das Umschreiben von Zeigern → O(1).
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ärts Navigieren 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)
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.
Historischer Kontext
Linked Lists entstanden in den 1950er Jahren aus früher KI-Forschung. Newell, Shaw und Simon entwickelten IPL (Information Processing Language, 1955), die Linked Lists als Kernstruktur nutzte. John McCarthy machte Linked Lists mit LISP (1958) zur Grundlage funktionaler Programmierung.
Stacks und Queues — Zugriffsprinzipien
Stack (LIFO) Last In, First Out — der zuletzt hinzugefügte Eintrag wird zuerst entfernt. Beispiel: Rückgängig-Funktion im Texteditor.
Queue (FIFO) First In, First Out — der zuerst hinzugefügte Eintrag wird zuerst bedient. Beispiel: Warteschlange beim Webserver.
Stack & Queue
AnalogieDefinition
Ein Tellerstapel: Du legst saubere Teller oben drauf und nimmst immer den obersten zuerst — der unterste bleibt vergraben (LIFO). Eine Supermarkt-Schlange: Der erste in der Reihe wird zuerst bedient; Neuzugänge stellen sich hinten an (FIFO). Diese zwei Prinzipien bestimmen, wie du auf die Daten zugreifen darfst.
Beispiel
Bei einem echten Tellerstapel könnte man in die Mitte greifen — ein echter Stack verbietet das. An einer Kasse können Leute die Schlange verlassen — eine strikte Queue hat keine solche Flexibilität.
Analogie:
Ein Tellerstapel: Du legst saubere Teller oben drauf und nimmst immer den obersten zuerst — der unterste bleibt vergraben (LIFO). Eine Supermarkt-Schlange: Der erste in der Reihe wird zuerst bedient; Neuzugänge stellen sich hinten an (FIFO). Diese zwei Prinzipien bestimmen, wie du auf die Daten zugreifen darfst.
Beispiel
Bei einem echten Tellerstapel könnte man in die Mitte greifen — ein echter Stack verbietet das. An einer Kasse können Leute die Schlange verlassen — eine strikte Queue hat keine solche Flexibilität.
Definition:
Stacks und Queues sind abstrakte Datentypen, die die Zugriffsreihenfolge definieren, nicht die Speicheranordnung. Ein Stack folgt LIFO (Last In, First Out): push legt oben drauf, pop entfernt von oben. Eine Queue folgt FIFO (First In, First Out): enqueue fügt hinten an, dequeue entfernt vorne. Beide erreichen O(1) für ihre Kernoperationen, unabhängig von der zugrunde liegenden Speicherung.
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.
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.
Deep Dive: Call Stack und Stack Overflow
Jeder Funktionsaufruf erzeugt einen Stack Frame mit lokalen Variablen und Rücksprungadresse. Python hat ein Standard-Rekursionslimit von ~1.000 Frames. Wird dieses überschritten, beendet Python das Programm mit einem RecursionError — dem berühmten Stack Overflow.
Friedrich Bauer und Klaus Samelson formalisierten den Stack 1957 an der 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
Array
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.
Linked List
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.
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
Vorteil (klein/schnell/hoch)
Neutral
Nachteil (groß/langsam/niedrig)
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)
Kernaussage: Keine Struktur ist universell die beste. Arrays gewinnen beim Zugriff, Linked Lists beim Einfügen. Die richtige Wahl hängt davon ab, welche Operationen dein Programm am häufigsten ausführt.
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.
Quiz: Lineare Datenstrukturen
Frage 1 / 4
Noch offen
Was ist der zentrale Unterschied zwischen einem Array und einer Linked List?
1. Was ist der zentrale Unterschied zwischen einem Array und einer Linked List?
☐ A) Arrays sind immer schneller als Linked Lists
☐ B) Arrays speichern Elemente zusammenhängend im Speicher; Linked Lists speichern sie verstreut mit Zeigern
☐ C) Linked Lists können nur Zahlen speichern
☐ D) Arrays erlauben kein Einfügen von Elementen
2. Du hast eine Liste mit 1.000.000 Einträgen und musst häufig in der Mitte einfügen. Welche Struktur ist geeigneter?
☐ A) Array — es hat besseren Index-Zugriff
☐ B) Linked List — WENN du bereits eine Referenz auf die Einfügestelle hast, ist Einfügen O(1)
☐ C) Stack — er erlaubt push und pop
☐ D) Queue — sie verarbeitet der Reihe nach
3. Ein Webserver muss eingehende Anfragen fair bearbeiten — wer zuerst kommt, wird zuerst bedient. Welches Prinzip sollte er nutzen?
☐ A) Stack (LIFO) — die neueste Anfrage zuerst
☐ B) Array — direkter Index-Zugriff
☐ C) Queue (FIFO) — die älteste Anfrage zuerst
☐ D) Linked List — verstreute Speicherung
4. Pythons list heißt 'list', ist aber intern ein dynamisches Array. Warum ist diese Unterscheidung wichtig?
☐ A) Sie spielt keine Rolle — Namen beeinflussen die Performance nicht
☐ B) Weil Arrays O(1)-Index-Zugriff haben, während echte Linked Lists O(n)-Durchlauf brauchen — der Name suggeriert andere Performance-Eigenschaften
☐ C) Weil Linked Lists immer schneller sind
☐ D) Weil Python keine echten Linked Lists implementieren kann
Auflösung: 1) B · 2) B · 3) C · 4) B
Lernziele
Du hast ein Array mit 1.000.000 Elementen. Wie viele Elemente müssen verschoben werden, um ein neues Element bei Position 500.000 einzufügen? Und wenn du am Ende anhängst?
Du baust eine Playlist-App. Nutzer fügen häufig Songs am Anfang und Ende hinzu, greifen aber selten per Positionsnummer zu. Würdest du ein Array oder eine Linked List wählen? Warum?
Dein Texteditor speichert Aktionen für die Rückgängig-Funktion. Du tippst A, B, C und drückst zweimal Rückgängig. Welche Aktionen werden rückgängig gemacht und in welcher Reihenfolge? Welches Prinzip (LIFO oder FIFO) steckt dahinter — und warum wäre das andere Prinzip hier katastrophal?