Datenstrukturen: Array, Liste, Stack und Queue
Kurzantwort
Eine Datenstruktur legt fest, wie mehrere Daten im Speicher organisiert und zugegriffen werden. Das Array bietet schnellen Zugriff über einen Index, die verkettete Liste erlaubt einfaches Einfügen und Löschen. Stack (LIFO) und Queue (FIFO) unterscheiden sich darin, in welcher Reihenfolge Elemente wieder entnommen werden. Die richtige Wahl hängt davon ab, welche Operationen häufig gebraucht werden.
Teil des Lernpfads Programmieren und Softwareentwicklung · Schritt 6 von 18
Eine einzelne Zahl in einer Variablen zu speichern ist einfach. Aber wie speichert man tausend Zahlen, eine Warteschlange oder die Rückgängig-Funktion eines Editors? Dafür gibt es Datenstrukturen – und welche man wählt, entscheidet oft über die Geschwindigkeit des ganzen Programms.
Was ist eine Datenstruktur?
Eine Datenstruktur bestimmt, wie mehrere Werte zusammen organisiert werden und wie man auf sie zugreift.
Das Array
Ein Array speichert Elemente fortlaufend und spricht sie über einen Index an – bei den meisten Sprachen beginnend bei 0.
index: 0 1 2 3
wert: "Ada" "Bob" "Cara" "Dan"Der Zugriff auf array[2] ist sofort möglich. Der Nachteil: Die Größe steht meist von Anfang an fest, und das Einfügen in der Mitte ist teuer, weil alle nachfolgenden Elemente verschoben werden müssen.
Die verkettete Liste
Bei einer verketteten Liste kennt jedes Element seinen Nachfolger. Die Elemente liegen nicht am Stück im Speicher.
["Ada"| →] → ["Bob"| →] → ["Cara"| →] → [null]Dadurch lässt sich vorne oder in der Mitte leicht einfügen und löschen – man biegt nur einen Verweis um. Der Preis: Es gibt keinen direkten Zugriff über einen Index; man muss von vorne durchhangeln.
Stack und Queue
Diese beiden unterscheiden sich allein in der Entnahme-Reihenfolge:
| Struktur | Prinzip | Bild | Einsatz |
|---|---|---|---|
| Stack | LIFO – last in, first out | Stapel Teller | Rückgängig-Funktion, Funktionsaufrufe |
| Queue | FIFO – first in, first out | Warteschlange | Druckaufträge, Nachrichtenpuffer |
Wie wähle ich richtig?
Selbstkontrolle
Selbstkontrolle
Ein Texteditor soll eine Rückgängig-Funktion bekommen: Der zuletzt gemachte Schritt wird als Erstes zurückgenommen. Welche Datenstruktur passt?
Häufige Fragen
Was ist der Unterschied zwischen Array und Liste in der Praxis?
Ein Array liegt am Stück im Speicher und bietet blitzschnellen Zugriff über den Index, ist aber unflexibel bei Größenänderungen. Eine verkettete Liste wächst und schrumpft mühelos und erlaubt günstiges Einfügen, kostet dafür bei jedem Zugriff über eine Position ein Durchhangeln. Viele Sprachen bieten zusätzlich dynamische Arrays, die intern ein Array nutzen, aber automatisch vergrößern.
Wo wird ein Stack im Betriebssystem genutzt?
Beim Aufruf von Funktionen. Jeder Aufruf legt seine lokalen Daten auf den sogenannten Aufruf-Stack, und beim Zurückkehren wird der oberste Eintrag wieder entfernt – genau das LIFO-Prinzip. Läuft eine Rekursion zu tief, läuft dieser Stack über, was zum bekannten Stack Overflow führt.
Was ist ein assoziatives Array oder eine Map?
Eine Struktur, die nicht über eine Zahl als Position zugreift, sondern über einen frei wählbaren Schlüssel, etwa einen Namen. Man spricht auch von Hashtabelle, Dictionary oder Map. Sie eignet sich, wenn du Werte schnell über einen eindeutigen Schlüssel finden willst, zum Beispiel eine Telefonnummer über den Namen.
Muss ich Datenstrukturen selbst programmieren können?
Für das Verständnis ja, für den Alltag meist nein. In der Prüfung sollst du erklären können, wie die Grundtypen funktionieren und welche wann passt. Im echten Projekt greifst du fast immer auf die geprüften Implementierungen der Standardbibliothek zurück, statt eine verkettete Liste selbst zu bauen.
Weiterlesen: Sortier- und Suchalgorithmen verstehen · Programmablaufplan (PAP) und Struktogramm · OOP-Grundlagen: Klasse, Objekt, Prinzipien
Das Wichtigste in Kürze
- Eine Datenstruktur legt Organisation und Zugriff mehrerer Werte fest.
- Array: schneller Zugriff per Index, aber starr und teuer beim Einfügen.
- Verkettete Liste: leicht einfügen und löschen, aber kein direkter Index-Zugriff.
- Stack = LIFO (Undo, Funktionsaufrufe), Queue = FIFO (Warteschlangen).
- Die Wahl richtet sich nach der häufigsten Operation.