Datenstrukturen erkennen und passend auswählen

Ein Datentyp fasst Werte und die Operationen dafür zu einer Einheit zusammen. Eine Operation ist eine Tätigkeit mit den Daten, zum Beispiel speichern, lesen oder löschen. Beispiele für Datentypen sind Ganzzahlen, Kommazahlen oder Zeichenketten.

Elementare Datentypen heißen auch einfache oder primitive Datentypen. Sie können nur einen Wert aus ihrem Wertebereich aufnehmen. Bei Zahlen sind die Grundoperationen die Grundrechenarten.

Eine Datenstruktur ist ein Objekt, das Daten speichert und organisiert. Die Daten werden in einer bestimmten Art und Weise angeordnet und verknüpft. So sind Zugriff und Verwaltung effizient möglich, das heißt ohne unnötigen Aufwand. Eine Datenstruktur ist nicht nur durch die enthaltenen Daten gekennzeichnet, sondern vor allem durch die Operationen, mit denen du auf die Daten zugreifst und sie verwaltest.

Zusammengesetzte Datentypen bestehen aus einfacheren Datentypen. Weil sie theoretisch beliebig komplex werden können, zählt man sie auch häufig schon zu den Datenstrukturen.

Ein Datensatz (auch Tupel) ist eine sehr einfache Datenstruktur. Er enthält meist in einer festen Anzahl und Folge Werte, die selbst wieder Werte enthalten können. Ein Datensatz für eine Prüfung hat zum Beispiel die Felder Fach, Schüler, Punkte, Lehrer und Termin.

Ein Array (auch Feld) speichert mehrere Variablen vom selben Basisdatentyp, zum Beispiel lauter Noten. Du erreichst jedes Element über einen Index, das ist seine Platznummer. Die notwendigen Operationen sind das indizierte Speichern und das indizierte Lesen. Beide greifen direkt auf jedes Element zu.

In einer verketteten Liste enthält jedes Listenelement einen Verweis auf das nächste Element. So entsteht eine Kette von Objekten. Die Liste kann beliebig viele Objekte speichern. Bei einer doppelt verketteten Liste gibt es auch einen Verweis auf das vorhergehende Element.

Im Stapelspeicher (englisch Stack) werden die gespeicherten Objekte nur in umgekehrter Reihenfolge wieder gelesen. Das heißt LIFO: Last In, First Out, also zuletzt hinein, zuerst heraus. Mit push legst du ein Objekt ab. Mit pop liest du das zuletzt gespeicherte Objekt und entfernst es vom Stapel. Die Operation top (oder peek) liest das oberste Element, ohne es zu löschen. Sie ist nicht zwingend vorgeschrieben.

In einer Warteschlange (englisch Queue) werden die Objekte in der Reihenfolge wieder gelesen, in der sie gespeichert wurden. Das heißt FIFO: First In, First Out. Mit enqueue speicherst du ein Objekt. Mit dequeue liest du das zuerst gespeicherte Objekt und entfernst es.

Ein Baum besteht aus Knoten und Kanten. Eine Kante verbindet zwei Knoten. Ein bestimmter Knoten ist die Wurzel. Sie ist der einzige Knoten ohne eingehende Kante. Jeder andere Knoten hat genau eine eingehende Kante. Knoten unter einem Elternteil heißen Kinder. Ein Knoten ohne Kinder heißt Blatt. Ein Baum eignet sich, um hierarchische Strukturen abzubilden. Ein Sonderfall ist der Binärbaum, in dem jeder Knoten höchstens zwei Kinder hat.

Auch ein Graph ist eine Datenstruktur. Bei ihm muss die Verknüpfung nicht nur in eine Richtung laufen. Seine Operationen sind das Einfügen, Löschen und Finden eines Objekts. Bäume sind spezielle Formen von Graphen.

Die Wahl der Datenstruktur zählt. Bei vielen Algorithmen hängen die benötigte Laufzeit und der Speicherplatz davon ab, ob eine geeignete Datenstruktur verwendet wird. Frage dich deshalb zuerst: Welche Operationen brauche ich?

Soll die Reihenfolge erhalten bleiben, passt eine Warteschlange. Sie dient als Puffer: Objekte werden zwischengespeichert, bevor sie weiterverarbeitet werden. So werden langsame Geräte wie ein Drucker vom Programm entkoppelt. Graphische Oberflächen puffern Ereignisse der Maus und Tastatur in einer Message Queue nach dem FIFO-Prinzip, also in der Reihenfolge ihres Auftretens. Wird dagegen das zuletzt gespeicherte Objekt zuerst gebraucht, passt ein Stapelspeicher. Bei Kartenspielen, in denen Karten auf einen Stapel gelegt oder von einem Stapel gezogen werden, sind Stapelspeicher geeignet.

Soll der Zugriff über eine Platznummer laufen, passt ein Array. Soll er über einen Schlüssel laufen, passt eine Zuordnungstabelle. Sie heißt auch assoziatives Array. Eine mögliche Umsetzung ist die Hashtabelle. Bei ihr berechnet eine Funktion die Position eines Objekts. Dadurch musst du nicht viele Objekte durchsuchen. Es kann aber passieren, dass zwei verschiedene Schlüssel zum selben Feld führen. Das nennt man Kollision. Eine Hashtabelle pflegt keine Ordnung zwischen den Schlüsseln.

Bäume haben bei geordneten Elementen, besonders bei Suchbäumen, einen Vorteil: Du findest Elemente schnell. Die Suche dauert bei einem Baum logarithmisch, bei einem Feld linear. Bei sehr vielen Daten wächst der Aufwand im Baum also viel langsamer. Außerdem können Bäume alle Indexwerte in einer Ordnung wiedergeben. Dafür brauchen sie einen größeren Verwaltungsaufwand als Hashtabellen.

Auch die Größe spielt eine Rolle. Eine statische Datenstruktur hat eine feste Größe, die sich zur Laufzeit nicht ändert. Brauchst du mehr Platz, musst du eine neue Struktur erstellen und alle Daten hineinschreiben. Eine dynamische Datenstruktur kann ihre Größe ändern, während das Programm läuft. Bei einer verketteten Liste muss die maximale Anzahl der Elemente nicht festgelegt werden.

Begründe deine Wahl immer so: Aufgabe nennen, nötige Operationen nennen, dann sagen: „Ich wähle …, weil …“.

Ein abstrakter Datentyp, kurz ADT, ist ein Verbund von Daten zusammen mit der Definition aller zulässigen Operationen, die auf sie zugreifen. Auf die Daten kommst du nur über diese Operationen. Die Daten sind deshalb nach außen gekapselt, also von außen geschützt. Du kannst nicht ungewollt in die innere Struktur eingreifen.

Ein ADT beschreibt, was die Operationen tun. Das nennt man Semantik. Er beschreibt aber noch nicht, wie sie es tun. Das Wie ist die Implementierung, also die konkrete Umsetzung.

Beim Stapelspeicher und bei der Warteschlange sehen die Signaturen gleich aus. Eine Signatur sagt, was in eine Operation hineingeht und was herauskommt. Erst mit der Semantik zeigen sich Unterschiede: Der Stapel arbeitet nach LIFO, die Warteschlange nach FIFO.

Derselbe ADT kann unterschiedlich umgesetzt sein. Eine Warteschlange wird gewöhnlich als verkettete Liste implementiert. Sie kann intern aber auch ein Array verwenden. Dann ist die Anzahl der Elemente begrenzt. Häufig ist sie ein Ringpuffer: Je ein Zeiger zeigt auf Anfang und Ende der Warteschlange, und der Puffer hat eine feste Größe. Ein Stapelspeicher wird gewöhnlich als Liste implementiert, kann aber auch ein Vektor sein. Eine Hashtabelle wird in der Praxis als Array implementiert.

Der Übergang zwischen Datenstruktur und abstraktem Datentyp ist nicht klar definiert. Er hängt von der Betrachtungsweise ab: Liegt der Schwerpunkt nicht auf der konkreten Umsetzung der Operationen, sprichst du oft von einem ADT.