Datenstrukturen einfach erklärt: Arten, Beispiele und Auswahl

Für eine Rückgängig-Funktion passt ein Stack, für eine Warteschlange eine Queue und für die Kundensuche über eine Nummer eine Map. Dieser Einstieg erklärt die wichtigsten Datenstrukturen mit Beispielen und zeigt, wann welche Struktur hilfreich ist.

Genau darum geht es bei Datenstrukturen: Sie organisieren Informationen so, dass bestimmte Aufgaben gut funktionieren. Die gleichen Namen können in einer Reihe stehen, auf einem Stapel liegen oder über Verbindungen zusammenhängen. Jede Anordnung erleichtert andere Zugriffe.

Die Frage lautet deshalb zuerst: Was möchtest du mit den Daten tun? Einen Eintrag an einer bekannten Position lesen? Die letzte Aktion zurücknehmen? Den dringendsten Auftrag finden? Erst danach ergibt sich eine sinnvolle Struktur.

Arrays: Wenn die Position bekannt ist

Ein Array ähnelt einer Reihe nummerierter Schließfächer. Jedes Fach hat einen festen Platz. Kennst du seine Nummer, lässt sich die Position berechnen, ohne die vorherigen Fächer nacheinander anzusehen.

Bei vielen Programmiersprachen beginnt die Nummerierung bei null. In der Reihe Mia, Leo, Ben, Ada hat Ada den Index 3. Der Index bezeichnet die Position, nicht den Inhalt.

Dieser Unterschied ist entscheidend. „Lies das Element an Position 3“ ist einfach. „An welcher Position steht Ada?“ kann eine Suche durch die ganze Reihe erfordern, wenn keine weitere Ordnung bekannt ist.

Beim Einfügen mitten in eine zusammenhängende Reihe müssen nachfolgende Elemente Platz machen. Für vier Namen ist das überschaubar. Bei sehr vielen Einträgen summiert sich die Arbeit.

Ein gewöhnliches Array besitzt eine feste Größe. Ein dynamisches Array reserviert bei Bedarf mehr Platz. Hinten lässt sich häufig günstig anfügen; gelegentlich müssen viele Elemente in einen größeren Bereich übernommen werden. Deshalb spricht man etwa bei Javas ArrayList von amortisiert konstantem Aufwand für das Anhängen: Die günstige Aussage gilt über eine Folge von Operationen, nicht zwingend für jeden einzelnen Aufruf. Java: ArrayList.

Verkettete Listen: Verbindungen statt fester Nachbarschaft

Eine verkettete Liste funktioniert eher wie eine Schnitzeljagd. Jeder Knoten enthält Daten und einen Verweis auf den nächsten Knoten. Die Elemente müssen im Speicher nicht unmittelbar nebeneinanderliegen.

Soll zwischen Mia und Leo ein neuer Name stehen, ändern sich die Verbindungen:

Vorher: Mia → Leo → Ben
Danach: Mia → Ada → Leo → Ben

Mia verweist anschließend auf Ada, Ada auf Leo. Die übrigen Daten müssen dafür nicht verschoben werden.

Das ist allerdings nur dann ein kleiner Eingriff, wenn die benötigte Stelle bereits bekannt ist. Um zum zehnten Element zu gelangen, musst du bei einer einfach verketteten Liste normalerweise den Verweisen folgen. Der direkte Sprung über einen Index fehlt.

Auch beim Entfernen brauchst du die passenden Verbindungen. Bei einer einfach verketteten Liste ist häufig der Vorgänger nötig, dessen Verweis umgelenkt wird. Eine doppelt verkettete Liste speichert zusätzlich Rückverweise. Das erleichtert bestimmte Schritte, kostet aber Speicher.

Die Liste tauscht also einen Vorteil gegen einen anderen: flexible Verknüpfungen gegen direkten Zugriff auf Positionen. Welche Variante praktisch schneller ist, hängt auch von der konkreten Implementierung und Nutzung ab.

Stacks: Die letzte Aktion kommt zuerst zurück

Ein Stack folgt der Regel „Last in, first out“, kurz LIFO. Stell dir einen Tellerstapel vor: Der zuletzt aufgelegte Teller wird zuerst heruntergenommen.

Eine Rückgängig-Funktion passt dazu. Du zeichnest einen Kreis, färbst ihn blau und verschiebst ihn. Beim Rückgängigmachen wird zuerst die Verschiebung zurückgenommen, dann die Farbe und zuletzt das Zeichnen.

Der Stack beschreibt eine Zugriffsregel. Er schreibt nicht vor, wie die Elemente darunter gespeichert werden. In Python kann eine Liste diese Aufgabe übernehmen:

aktionen = []
aktionen.append("Kreis zeichnen")
aktionen.append("Blau färben")
aktionen.append("Nach rechts verschieben")

print(aktionen.pop())  # Nach rechts verschieben

append fügt am Ende hinzu, pop entnimmt dort. Die eigentliche Rückgängig-Funktion müsste zusätzlich wissen, wie sie die gespeicherte Aktion umkehrt. Ein Text allein tut das noch nicht. Python: Listen als Stacks.

Falls dir Variablen und Methodenaufrufe noch neu sind, führt dich der Artikel zu den Programmiergrundlagen mit Python durch diese Bausteine.

Queues: Wer zuerst kommt, wird zuerst bearbeitet

An einer Kasse wäre LIFO meist unpassend. Dort sollen zuerst eingetroffene Personen zuerst bedient werden. Eine Queue folgt „First in, first out“, kurz FIFO.

Neue Aufgaben kommen hinten dazu. Die nächste Aufgabe wird vorne entnommen. Aus Mia, Leo, Ben wird dadurch die Bearbeitungsreihenfolge Mia, Leo, Ben.

Für ein kleines Python-Beispiel eignet sich deque:

from collections import deque

auftraege = deque(["Mia", "Leo", "Ben"])
auftraege.append("Ada")
print(auftraege.popleft())  # Mia

Eine deque unterstützt effizientes Hinzufügen und Entfernen an beiden Enden. Wiederholt das erste Element einer gewöhnlichen Python-Liste zu entfernen wäre für eine große Warteschlange ungünstiger, weil die restlichen Elemente verschoben werden müssen. Python: deque.

Hashmaps: Einen Wert über seinen Schlüssel finden

Manchmal kennst du keine Position, sondern eine Kennung: Kundennummer 204 gehört zu einem bestimmten Datensatz. Eine Map bildet solche Schlüssel-Wert-Zuordnungen ab. Eine verbreitete Umsetzung ist die Hashtabelle, häufig Hashmap genannt.

Eine Hashfunktion verarbeitet den Schlüssel und hilft dabei, ein Tabellenfach zu bestimmen. Dort wird geprüft, welcher gespeicherte Schlüssel tatsächlich passt. Dieser Vergleich bleibt nötig, weil verschiedene Schlüssel im selben Fach landen können. Das nennt man eine Kollision.

Kollisionen lassen sich beispielsweise durch mehrere Einträge pro Fach behandeln. Andere Implementierungen verwenden andere Verfahren. Der wichtige Punkt: Ein fremder Eintrag darf nicht einfach überschrieben werden, nur weil er dasselbe Fach belegt.

Bei geeigneter Verteilung sind grundlegende Zugriffe im Durchschnitt sehr günstig. Das ist keine Garantie für exakt einen Arbeitsschritt. Die offizielle Dokumentation von Javas HashMap nennt eine passende Verteilung der Schlüssel ausdrücklich als Voraussetzung. Java: HashMap.

In Python könnte die Zuordnung so aussehen:

kunden = {204: "Mia", 318: "Leo"}
print(kunden[204])  # Mia

Dabei bedeutet „nicht automatisch sortiert“ etwas anderes als „ohne jede Reihenfolge“: Python-Dictionaries bewahren die Einfügereihenfolge. Nach Kundennummern sortiert sind sie dadurch nicht. Python: Dictionaries.

Sets: Ist ein Element schon dabei?

Bei einer Gästeliste soll eine doppelte Anmeldung nicht zu einem doppelten Gast führen. Dafür eignet sich ein Set, auf Deutsch eine Menge. Jedes unterschiedliche Element ist höchstens einmal enthalten.

feier = {17, 42, 42}
essen = {42, 99}
print(feier & essen)  # {42}

Die doppelte 42 erzeugt keinen zweiten Eintrag. Das & bildet hier die Schnittmenge: Gast 42 ist für beide Veranstaltungen angemeldet.

Ein Set beantwortet Fragen nach Zugehörigkeit und Eindeutigkeit. Es ist keine geeignete Darstellung, wenn du unbedingt festhalten musst, wer zuerst zugesagt hat. Auch Sets lassen sich mit Hashtabellen umsetzen. Python: Mengen.

Bäume: Wenn Informationen eine Hierarchie haben

Ein Ordner enthält Unterordner, die wiederum weitere Einträge enthalten. Für diese vereinfachte Hierarchie passt ein Baum: Oben steht die Wurzel, darunter liegen Kindknoten. Knoten ohne Kinder heißen Blätter.

In einem solchen verwurzelten Baum hat jeder Knoten außer der Wurzel genau einen direkten Elternknoten. Reale Dateisysteme können durch Verknüpfungen zusätzliche Beziehungen besitzen; die Ordnerhierarchie ist hier das Modell, das uns interessiert.

Eine besondere Baumart ist der binäre Suchbaum. Bei unterschiedlichen Zahlen liegen kleinere Werte im linken, größere im rechten Teilbaum. Steht oben 20 und wir suchen 25, gehen wir nach rechts. Treffen wir dort auf 30, geht es von dort nach links.

Die Form entscheidet über den Aufwand. Ein gut verteilter Baum schließt bei jedem Schritt viele Möglichkeiten aus. Eine fast einseitige Kette kann dagegen wieder lange Wege verursachen. Selbstbalancierende Varianten halten die Höhe begrenzt. Javas TreeMap verwendet einen Rot-Schwarz-Baum und dokumentiert logarithmischen Aufwand für grundlegende Operationen. Java: TreeMap.

Heaps: Immer die wichtigste Aufgabe griffbereit

Eine Queue sortiert nach Ankunft. Was aber, wenn ein dringender Serverausfall vor einem normalen Bericht bearbeitet werden soll? Dann brauchen wir eine Prioritätswarteschlange.

Ein binärer Heap ist eine Möglichkeit, sie umzusetzen. Im Min-Heap steht eine kleinste Prioritätszahl an der Spitze. Jeder Elternknoten besitzt einen Wert, der höchstens so groß ist wie der seiner Kinder. Der übrige Inhalt ist dadurch noch nicht vollständig sortiert.

Beim Einfügen wird die Ordnung durch Verschieben nach oben wiederhergestellt. Nach der Entnahme des kleinsten Elements kann ein ersetzendes Element nach unten wandern. Python stellt diese Operationen im Modul heapq bereit und speichert den Heap in einer Liste. Python: heapq.

Eine zusätzliche Regel brauchst du bei gleicher Priorität: Soll dann die ältere Aufgabe zuerst drankommen, muss die Einfügereihenfolge mit berücksichtigt werden.

Graphen: Wenn Beziehungen ein Netz bilden

Straßen, Flugverbindungen und Abhängigkeiten passen oft nicht in eine einfache Hierarchie. Ein Graph besteht aus Knoten und Kanten. Kanten können gerichtet sein und zusätzliche Werte tragen, sogenannte Gewichte. NetworkX: Graphen.

Ein Beispiel macht den Unterschied zwischen Struktur und Aufgabe deutlich:

Verbindung	Entfernung
A nach B	2 Kilometer
B nach C	2 Kilometer
A nach C	7 Kilometer

Der direkte Weg von A nach C nutzt nur eine Kante. Über B sind es zwei Kanten, aber insgesamt nur vier Kilometer. „Wenigste Verbindungen“ und „kürzeste Strecke“ sind also verschiedene Ziele. Für die schnellste Fahrt müsstest du Fahrzeiten als Gewichte betrachten.

Der Graph findet selbst noch keine Route. Er beschreibt die Beziehungen. Ein Algorithmus nutzt sie zur Suche. Gespeichert werden können sie beispielsweise als Nachbarlisten pro Knoten: Mehrere Datenstrukturideen arbeiten zusammen.

Eine kurze Entscheidungshilfe

Deine zentrale Frage	Passende Ausgangsidee
Was steht an Position 12?	Array oder dynamisches Array
Welche Aktion war zuletzt dran?	Stack
Welcher Auftrag wartet am längsten?	FIFO-Queue
Welcher Datensatz gehört zu dieser ID?	Map
Ist diese ID bereits enthalten?	Set
Was gehört unter welche Kategorie?	Baum
Welche Aufgabe hat höchste Priorität?	Prioritätswarteschlange
Wie hängen mehrere Orte zusammen?	Graph

Beginne bei deinem nächsten Projekt mit zwei oder drei häufigen Operationen. Musst du überwiegend suchen, einfügen, entnehmen oder Beziehungen verfolgen? Diese Fragen sind hilfreicher als die Suche nach einer universell besten Datenstruktur. Die passende Organisation ergibt sich aus der Arbeit, die sie erleichtern soll.