Jeder Programmierer steht vor dem Problem, wie er zusammengehörige Daten abspeichern soll. Im einfachsten Fall kann er ein Array verwenden, doch hier kann der Verwaltungsaufwand schnell zu hoch werden, um noch effektiv damit arbeiten zu können. Aus diesem Grund wurden eine Reihe verschiedener Datenstrukturen entwickelt, die verschiedene Vor- und Nachteile haben. Im Folgenden soll erläutert werden, was Datenstrukturen genau sind und wofür man sie benötigt. Außerdem sollen die wichtigsten elementaren Datenstrukturen genannt werden.
Was sind Datenstrukturen?
Die Entscheidung zur Organisation von Daten sind bei der Entwicklung eines Programms ein sehr wesentlicher Schritt. Und eine Datenstruktur tut genau das: sie organisiert die Daten und stellt Algorithmen zur Datenverwaltung zur Verfügung. Weil die Daten in einer bestimmten Art und Weise miteinander verknüpft werden, um einem möglichst einfachen Zugang zu ermöglichen, spricht man von einer Struktur. Dabei spielt die Art der zu speichernden Informationen erst einmal keine Rolle.
Dabei gibt es Datenstrukturen, die in einem Programm verwendet werden, um Daten während der Programmlaufzeit im Speicher zu organisieren (z.B. Arrays) und solche, die bei der Speicherung auf externen Datenträgern unterstützen (z.B. auf Festplatten, in Datenbanken). Einige Datenstrukturen wie z.B. Bäume können in beiden Fällen eingesetzt werden.
Datenstrukturen sind nicht passiv. Wie bereits erwähnt, stellen sie Algorithmen zur Verfügung, mit deren Hilfe die Daten verwaltet werden können. Grundlegende Funktionen einer Datenstruktur sind z.B. das Hinzufügen und das Löschen von Informationen. Dabei müssen Sie natürlich beachten, dass gleiche Funktionen bei verschiedenen Datenstrukturen unterschiedlich effizient und komplex zu programmieren sind. Bestimmte Strukturen benötigen mehr Speicherplatz für die gleichen Daten als andere, bringen dafür aber wiederum Vorteile in anderen Bereichen mit sich.
Bevor Sie sich für eine Datenstruktur entscheiden, müssen Sie deren Vor- und Nachteile kennen und diese in dem jeweiligen konkreten Fall gegeneinander abwägen. Ziel ist es natürlich, durch die geeignete und richtige Wahl einer Struktur Zeit und Speicherplatz zu sparen und möglichst effektiv mit den Daten arbeiten zu können.
Warum sollte man sich mit Datenstrukturen auskennen?
Die meisten Datenstrukturen müssen Sie im Allgemeinen nicht mehr selbst programmieren. Als Informatiker sollten Sie jedoch deren Konzepte kennen. Dies kann helfen, Ihr Verständnis von der Informatik und von Software zu erhöhen. So werden in Datenbanken bspw. Bäume als Strukturen eingesetzt. Außerdem stellt die Programmierung von Datenstrukturen immer wieder eine gute Übung dar, um die eigenen Fähigkeiten in der Programmierung zu verbessern.
Welche Datenstrukturen gibt es und wie hängen sie zusammen?
Es gibt elementare Datenstrukturen wie z.B. Arrays und verkettete Listen. Diese bilden die Grundlage für die komplexeren Strukturen wie Bäume, Stacks usw. Ein Stack kann sowohl durch Arrays als auch durch verkettete Listen realisiert werden. Für die Realisierung von Listen können wiederum Arrays verwendet werden. Die Entscheidung, mit Hilfe welcher elementaren Struktur eine komplexe Datenstruktur realisiert wird, kann auch Auswirkungen auf die Effizienz haben: Wenn Sie einen Baum durch ein Array realisieren, ist das besonders effizient für die Laufzeit, wird sich aber negativ auf den Platzbedarf aus.
In der folgenden Liste sehen Sie einige Datenstrukturen, die Sie als Programmierer unbedingt kennen sollten:
- Arrays
- Stacks
- Queues
- Verkettete Listen
- Binäre Bäume
- Rot-Schwarz-Bäume
- 2-3-4-Bäume
- Hash-Tabellen
- Graphen