Datenstrukturen: Array, Liste, Stack, Queue, Baum, Hash
Bisher haben wir Algorithmen betrachtet – die Verarbeitung von Daten. Jetzt zur anderen Seite der Medaille: wie organisiert man die Daten überhaupt? Eine Datenstruktur ist eine Art, Daten im Speicher abzulegen, damit man effizient mit ihnen arbeiten kann.
Die Wahl der richtigen Datenstruktur ist oft wichtiger als der Algorithmus selbst. Eine geniale Suche nützt nichts, wenn die Daten in einer Struktur liegen, die schnelles Suchen nicht zulässt. Diese Lektion stellt die sechs grundlegenden Datenstrukturen vor, ihre Eigenschaften, typische Operationen und ihre O-Notation-Kosten.
1) Array – die einfachste Struktur
Ein Array (auch Feld) ist eine Sammlung von Elementen, die zusammenhängend im Speicher liegen. Jedes Element ist über einen Index (Position) ansprechbar – meist 0-basiert (erstes Element auf Index 0). Weil Elemente direkt nebeneinander liegen, kann das System die Adresse jedes Elements direkt berechnen: Startadresse + Index · Elementgröße.
Das Ergebnis: der Zugriff auf ein Element bei beliebigem Index dauert immer gleich lang – egal ob Position 0 oder Position 1 Million. Das ist O(1). Allerdings: Einfügen oder Löschen in der Mitte ist teuer, weil alle nachfolgenden Elemente verschoben werden müssen → O(n).
(Bei int-Werten, 4 Bytes pro Element, alle direkt hintereinander)
int[] in Java, list in Python (dynamisches Array), std::vector in C++.2) Verkettete Liste – flexible Verkettung
Eine verkettete Liste (engl. Linked List) speichert Elemente nicht zusammenhängend. Jedes Element (genannt Knoten) enthält den Wert plus einen Zeiger (Pointer) auf das nächste Element. Die Knoten liegen irgendwo im Speicher verstreut, sind aber durch Pointer verkettet.
NULL (oder null oder None, je nach Sprache) – Signal dafür, dass die Liste hier endet. Anders als beim Array: keine kontinuierliche Speicherzuordnung, daher kein O(1) Zugriff auf beliebige Position. Um zum 5. Element zu kommen, musst du dich von Knoten zu Knoten hangeln – das ist O(n). Vorteil: Einfügen und Löschen am Anfang (oder bei bekanntem Vorgänger-Knoten) ist O(1) – kein Verschieben nötig, nur Pointer umhängen.Es gibt Varianten: bei doppelt verketteten Listen hat jeder Knoten zusätzlich einen Pointer auf den vorherigen Knoten – das erlaubt Rückwärts-Iteration. Bei zyklischen Listen zeigt das letzte Element wieder auf das erste, statt auf NULL. In Sprachen: LinkedList in Java, std::list in C++. Python's list ist trotz des Namens ein dynamisches Array, keine verkettete Liste.
3) Array vs. verkettete Liste
Beide haben ihre Berechtigung. Wann nimmt man was?
- Array: wenn du oft per Index zugreifst, die Größe relativ stabil ist und die Daten gut in einen kontinuierlichen Speicherbereich passen. Vorteil: maximale Performance, Cache-Lokalität.
- Verkettete Liste: wenn du oft am Anfang oder mittendrin einfügst und löschst, ohne Index-Zugriffe zu brauchen. Vorteil: Größe wächst beliebig, kein Umkopieren bei Erweiterung.
In der Praxis dominieren Arrays. Modernes CPU-Caching macht Arrays selbst bei Operationen, die theoretisch O(n) sind, oft schneller als die theoretisch besseren Linked Lists.
4) Stack – LIFO (Last In, First Out)
Ein Stack (Stapel) ist eine Datenstruktur mit nur zwei Operationen: push (Element oben drauflegen) und pop (oberstes Element wegnehmen). Was zuletzt reinkam, kommt als erstes wieder raus – wie ein Stapel Teller. Du nimmst den obersten Teller, nicht den untersten. Daher LIFO: Last In, First Out.
5) Queue – FIFO (First In, First Out)
Eine Queue (Warteschlange) ist das Gegenstück zum Stack: First In, First Out. Was zuerst reinkommt, kommt auch zuerst wieder raus – wie an der Supermarktkasse. Operationen heißen meist enqueue (anstellen, hinten anfügen) und dequeue (bedienen, vorne entfernen).
6) Bäume – hierarchische Strukturen
Ein Baum ist eine hierarchische Datenstruktur. Ausgangspunkt ist ein Wurzelknoten (root). Jeder Knoten kann Kinder haben. Knoten ohne Kinder heißen Blätter. Die wichtigste Variante ist der Binärbaum – jeder Knoten hat höchstens zwei Kinder (links und rechts).
Wichtige Baum-Varianten:
- AVL-Bäume und Rot-Schwarz-Bäume: selbst-balancierende binäre Suchbäume. Garantieren immer O(log n).
- B-Bäume: Bäume mit höherer Verzweigung (oft viele Kinder pro Knoten). Werden in Datenbank-Indizes und Dateisystemen eingesetzt.
- Heap: spezieller Baum, in dem das Maximum (oder Minimum) immer an der Wurzel steht. Basis für Priority Queues und Heapsort.
- Trie: Präfix-Baum für Strings. Wird in Autovervollständigung und Wörterbüchern eingesetzt.
Bäume werden auch durch Rekursion sehr natürlich verarbeitet – jeder Teilbaum ist selbst wieder ein Baum. Die typischen Traversal-Verfahren (Inorder, Preorder, Postorder, Levelorder) sind klassische rekursive Algorithmen.
7) Hash-Map – Wörterbuch mit Direktzugriff
Die letzte und vielleicht mächtigste Grunddatenstruktur: die Hash-Map (auch Dictionary, Map, Assoziatives Array). Sie speichert Schlüssel-Wert-Paare und erlaubt O(1)-Zugriff auf den Wert bei gegebenem Schlüssel – im Durchschnitt.
Wie geht das? Über eine Hash-Funktion, die aus einem beliebigen Schlüssel eine Zahl errechnet (siehe K11 Lektion zu Hashing). Diese Zahl wird modulo Tabellengröße genommen und ergibt einen Bucket-Index. Der Wert wird in diesem Bucket abgelegt. Beim Suchen wendet man dieselbe Hash-Funktion an und findet den Wert sofort.
In der Praxis sind Hash-Maps für viele Aufgaben das schnellste Werkzeug:
- Konfigurationen: Key/Value-Paare wie "language" → "de", "theme" → "dark".
- Zählerstände: wie oft kommt jedes Wort in einem Text vor?
- Caches: Redis ist im Kern eine riesige Hash-Map.
- Datenbank-Indizes mit Hash-Index (siehe K36 DB-Indizes).
- Schnelle Duplikat-Erkennung in O(n).
In Sprachen: HashMap in Java, dict in Python, std::unordered_map in C++, Objekte in JavaScript.
8) Komplexitäts-Vergleich der Operationen
Hier die wichtigste Tabelle dieser Lektion: alle sechs Datenstrukturen mit ihren typischen Operationen und Kosten. Diese Tabelle solltest du gut kennen – sie wird in jeder Algorithmen-Klausur abgefragt:
| Datenstruktur | Zugriff [i] | Suchen | Einfügen | Löschen |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Sortiertes Array | O(1) | O(log n) | O(n) | O(n) |
| Verkettete Liste | 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) |
| Binärbaum (BST, balanciert) | — | O(log n) | O(log n) | O(log n) |
| Hash-Map | — | O(1)** | O(1)** | O(1)** |
9) Auswahl der richtigen Datenstruktur
Wie entscheidest du, welche Datenstruktur du brauchst? Mit diesen Faustregeln triffst du in 80% der Fälle die richtige Wahl:
10) Häufige Klausur-Aufgaben
Typische Fragen zu Datenstrukturen in IHK-Prüfungen:
- „Beschreiben Sie den Unterschied zwischen Array und verketteter Liste." Speicherlayout (zusammenhängend vs. verteilt), Zugriffszeit (O(1) vs. O(n)), Einfügen (O(n) vs. O(1) am Anfang). Klassiker.
- „Was ist der Unterschied zwischen Stack und Queue?" Stack: LIFO. Queue: FIFO. Stack push/pop am gleichen Ende, Queue: enqueue hinten, dequeue vorne.
- „Wann verwendet man Hash-Maps, wann Bäume?" Hash-Maps: O(1) Lookup, aber keine Sortierung. Bäume: O(log n) Lookup, aber bewahren Sortierung. Wenn du sortierte Iteration brauchst → Baum. Sonst → Hash-Map.
- „Geben Sie ein Beispiel für die Anwendung eines Stacks." Funktionsaufrufe (siehe Rekursion / Call-Stack), Undo-Funktion, Klammerprüfung, Browser-Zurück-Button.
- „Was ist eine Hash-Kollision und wie wird sie aufgelöst?" Zwei verschiedene Schlüssel ergeben denselben Bucket-Index. Lösungen: Chaining (verkettete Listen in jedem Bucket) oder Open Addressing (Linear Probing zu nächstem freien Bucket).
Zusammenfassung
Sechs grundlegende Datenstrukturen: Array (zusammenhängend, O(1) Zugriff, O(n) Einfügen), Verkettete Liste (Knoten mit Pointern, O(n) Zugriff, O(1) Einfügen am Anfang), Stack (LIFO, push/pop in O(1)), Queue (FIFO, enqueue/dequeue in O(1)), Baum (hierarchisch, in balancierten Varianten O(log n) für alle Operationen), Hash-Map (Schlüssel-Wert, O(1) im Durchschnitt). Die Wahl der richtigen Datenstruktur ist oft wichtiger als der Algorithmus – sie bestimmt, welche Operationen schnell sind. Faustregeln: viele Index-Zugriffe → Array. Schneller Lookup → Hash-Map. Sortierte Daten mit schneller Suche → Baum. LIFO → Stack. FIFO → Queue. Häufige Einfügung mittendrin → verkettete Liste. Bezüge zu anderen Lektionen: binäre Suche braucht sortierte Arrays. Sortier-Algorithmen operieren typisch auf Arrays. Rekursion nutzt intern einen Call-Stack. Bäume werden meist rekursiv traversiert. O-Notation hilft bei der Bewertung. In der Praxis: jede moderne Programmiersprache stellt diese Strukturen als Bibliotheks-Klassen bereit (in Java: ArrayList, LinkedList, Stack, Queue, TreeMap, HashMap). Praktische Anwendungen: B-Bäume in Datenbank-Indizes, Redis als Hash-Map-Datenbank, Hash-basierte Verschlüsselung, JSON als Baum-Struktur. Letzte Lektion L10 IHK-Aufgaben konsolidiert alle Kurs-Inhalte.