Datenstrukturen erkennen und passend auswählen

Ein einzelner elementarer Datentyp speichert gewöhnlich einen Wert, zum Beispiel eine ganze Zahl, eine Zeichenkette oder einen Wahrheitswert. Eine Datenstruktur fasst mehrere Werte zusammen oder stellt Beziehungen zwischen ihnen her.

Die Verkaufszahlen 500, 800, 600, 1200, 950 lassen sich beispielsweise gemeinsam in einem Array speichern. Dadurch kann ein Programm einzelne Werte über ihre Position abrufen oder alle Werte nacheinander verarbeiten.

Typische Operationen auf Datenstrukturen sind:

• Einfügen: einen Wert ergänzen
• Löschen: einen Wert entfernen
• Suchen: einen bestimmten Wert finden
• Zugreifen: einen bekannten Wert lesen oder verändern
• Sortieren: Werte in eine Reihenfolge bringen

Datenstrukturen lassen sich nach verschiedenen Fragen einteilen. Diese Einteilungen widersprechen sich nicht, sondern betrachten unterschiedliche Eigenschaften.

Linear oder nichtlinear?

Bei einer linearen Datenstruktur stehen die Elemente in einer Folge. Dazu gehören Arrays, verkettete Listen, Stacks und Queues.

Bei einer nichtlinearen Datenstruktur verzweigen sich Beziehungen oder bilden ein Netz. Bäume bilden Hierarchien, Graphen allgemeinere Beziehungsnetze.

Statisch oder dynamisch?

Eine statische Struktur besitzt in ihrem jeweiligen Modell eine festgelegte Kapazität. Ein klassisches Feld ist ein typisches Beispiel.

Eine dynamische Struktur kann während der Laufzeit wachsen oder schrumpfen. Verkettete Listen ergänzen dazu neue Knoten und Referenzen.

Die genaue Bedeutung hängt von der Programmiersprache und der Implementierung ab. Klassische Felder haben eine feste Größe. JavaScript-Arrays können dagegen nachträglich wachsen. Deshalb darfst du die Aussage „Arrays sind immer unveränderlich groß“ nicht auf jede Sprache übertragen.

Verhalten oder Implementierung?

Ein abstrakter Datentyp beschreibt, welche Werte und Operationen erlaubt sind und wie sie sich verhalten. Er legt nicht zwingend fest, wie die Daten intern gespeichert werden.

Eine Queue ist beispielsweise durch das FIFO-Verhalten bestimmt. Sie kann intern mit einem Feld oder mit einer verketteten Liste umgesetzt werden.

Array oder Feld

Ein Array ordnet Elemente über nummerierte Positionen, die Indizes. In vielen Sprachen beginnt der erste Index bei 0. Bei einem Array mit den Werten 4, 7, 9 liegt die 7 dann am Index 1.

Der bekannte Index ermöglicht direkten Zugriff. Bei einem klassischen Feld kostet dieser Zugriff unabhängig von der Elementzahl typischerweise O(1). Das bedeutet: Die Zahl der notwendigen Schritte wächst dabei nicht mit der Anzahl n der gespeicherten Elemente.

Soll jedoch am Anfang eines belegten Feldes ein Wert eingefügt werden, müssen viele vorhandene Werte verschoben werden. Im ungünstigen Fall wächst der Aufwand proportional zu n und wird als O(n) beschrieben.

Verkettete Liste

Eine verkettete Liste besteht aus Knoten. Jeder Knoten enthält Daten und mindestens eine Referenz auf den nächsten Knoten:

Video 1 → Video 2 → Video 3

Soll hinter Video 1 ein neues Element eingefügt werden, erhält der neue Knoten zuerst die Referenz auf Video 2. Danach verweist Video 1 auf den neuen Knoten. So bleibt der restliche Listenabschnitt erreichbar.

Einfügen und Löschen erfordern kein Verschieben aller folgenden Elemente. Die betreffende Stelle muss aber zunächst bekannt sein. Ohne direkten Verweis muss die Liste vom Anfang aus durchlaufen werden; eine Positionssuche kann deshalb O(n) benötigen.

Datensatz oder Record

Ein Datensatz fasst zusammengehörige Werte mit unterschiedlichen Bedeutungen zusammen. Ein Schülerdatensatz könnte beispielsweise die Felder Name, Geburtsjahr und Klassenstufe enthalten.

Das unterscheidet ihn von einem klassischen Array gleichartiger Werte: Ein Array eignet sich etwa für zehn Messwerte, ein Datensatz für verschiedene Angaben zu einem Gegenstand oder einer Person.

Stack und Queue sind lineare abstrakte Datentypen. Beide können mit einem Feld oder einer verketteten Liste implementiert werden. Sie unterscheiden sich darin, welches Element als Nächstes entfernt wird.

Stack: zuletzt hinein, zuerst heraus

Ein Stack arbeitet nach LIFO: last in, first out. push legt ein Element oben ab, pop entfernt das oberste Element und peek liest es, ohne es zu entfernen.

Beispiel Rückgängig-Funktion:

1. Du tippst A.
2. Du tippst B.
3. Du tippst C.
4. Die Aktionen liegen in dieser Reihenfolge auf dem Stack.
5. Beim Rückgängigmachen wird zuerst die letzte Aktion, also C, entfernt.

Stacks eignen sich außerdem für Browserverläufe und Klammerprüfungen. Bei einer Klammerprüfung wird jeder Öffner abgelegt. Ein Schließer muss zum obersten Öffner passen. Ist der Stack vorher leer oder bleiben am Ende Öffner übrig, ist die Klammerfolge fehlerhaft.

Queue: zuerst hinein, zuerst heraus

Eine Queue arbeitet nach FIFO: first in, first out. enqueue fügt am Ende ein Element ein, dequeue entfernt das Element am Kopf.

Beispiel Druckerwarteschlange:

1. Auftrag A wird eingereiht.
2. Danach folgen B und C.
3. Der Drucker verarbeitet zuerst A, anschließend B und zuletzt C.

Queuen eignen sich für Druckaufträge, Ereignisse und gepufferte Nachrichten. Bei einer begrenzten Implementierung müssen Sonderfälle behandelt werden: dequeue bei einer leeren Queue führt zum Underflow, Einfügen in eine volle Struktur zum Overflow.

Baum: eine Hierarchie

Ein Baum beginnt an einer Wurzel und verzweigt sich über Knoten. Knoten ohne Kinder heißen Blätter. Ein Dateisystem mit Ordnern und Unterordnern lässt sich als Baum darstellen.

In einem Binärbaum besitzt jeder Knoten höchstens zwei Kinder. Ein binärer Suchbaum ordnet seine Schlüssel so, dass die Suche gezielt einem passenden Teilbaum folgen kann.

Graph: ein Beziehungsnetz

Ein Graph besteht aus Knoten und Kanten. Auf einer Straßenkarte können Städte die Knoten und Straßen die Kanten bilden. Anders als bei einem Baum dürfen allgemeinere Graphen mehrere Wege, Querverbindungen und Zyklen enthalten.

Die Breitensuche untersucht Verbindungen schrittweise Ebene für Ebene. Die Tiefensuche folgt zunächst einem Weg weiter in die Tiefe.

Hashtabelle: Zugriff über Schlüssel

Eine Hashtabelle speichert Schlüssel-Wert-Paare. Eine Hashfunktion berechnet aus einem Schlüssel eine Position oder Zuordnung. In einer Kontaktliste kann der Name als Schlüssel dienen und zur gespeicherten Telefonnummer führen.

Hashtabellen eignen sich besonders für den schnellen Zugriff über bekannte Schlüssel. Soll die Datenstruktur ihre Schlüssel dagegen geordnet ausgeben, kann eine geeignete Baumstruktur vorteilhafter sein.

Gehe bei der Auswahl in vier Schritten vor:

1. Bestimme die Daten: Sind es gleichartige Werte, verschiedenartige Eigenschaften, eine Reihenfolge, eine Hierarchie oder ein Netz?
2. Bestimme die häufigsten Operationen: Muss das Programm vor allem zugreifen, suchen, einfügen oder löschen?
3. Beachte Bedingungen: Ist die Größe bekannt? Wird ein Schlüssel verwendet? Muss die Reihenfolge erhalten bleiben?
4. Vergleiche die Kosten: Eine Stärke bei einer Operation kann eine Schwäche bei einer anderen bedeuten.

Übung: Begründe deine Wahl

Eine Lern-App soll Begriffe unter einem eindeutigen Stichwort speichern. Wird das Stichwort eingegeben, soll die Erklärung schnell gefunden werden. Welche Datenstruktur würdest du wählen?

Wenn du eine Datenstruktur auswählst, frage zuerst nach den häufig benötigten Operationen. Begründe danach, warum die Stärken der gewählten Struktur genau zu diesen Operationen passen.