Dynamische Datenstrukturen

Im Gegensatz zu statischen Datenstrukturen wie beispielsweise dem Array können sich dynamische Datenstrukturen zur Laufzeit des Programms an den wachsenden (oder sinkenden) Speicherbedarf anpassen. Möglich wird dies durch die Verwendung von Zeigern (Pointern, Referenzen).

Allgemein unterscheidet man drei Typen von dynamischen Datenstrukturen ¹⁾

Listen

Eine dynamische Liste besteht aus Elementen, die zwei oder drei Komponenten umfassen:

1. Der eigentliche Wert
2. Eine Referenz auf den Nachfolger
3. Eine Referenz auf den Vorgänger

Man unterscheidet hier zwischen einfach verketteten Listen (Komponenten 1 und 2) und doppelt verketteten Listen (Komponenten 1, 2 und 3). Für den Fall, dass die Listenelemente auf- oder absteigend sortiert sind, spricht man auch von sortierten Listen.

Eine dynamische Liste aus int-Zahlen vor und nach dem Einfügen eines Elementes
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.

Hier sehen wir eine einfach verkettete dynamische Liste aus int-Zahlen. Zunächst besteht die Liste aus den vier Zahlen 3, 5, 9 und 12. Dann wird die Zahl 7 in die Liste einsortiert. Hier haben wir es also mit dem Spezialfall der einfach verketteten sortierten Liste zu tun.

Dynamische Listen werden oft zur Implementierung von abstrakten Datentypen wie Stack oder Queue verwendet. Einen Stack oder eine Queue kann man natürlich auch mit einem statischen Datentypen (Array) implementieren, allerdings ist das dann auch mit allen Nachteilen der statischen Datentypen verbunden (siehe Einleitung oben).

Bäume

Bäume sind Datenstrukturen, bei denen jedes Element mindestens zwei Nachfolger und genau einen Vorgänger hat. Besondere Elemente sind die Wurzel, die keinen Vorgänger hat, und die Blätter, die keinen Nachfolger haben.

Ein häufig benutzter Spezialfall sind die binären Suchbäume. Das Wort "binär" bezieht sich auf die Tatsache, dass jedes Element des Baumes maximal zwei Nachfolger hat, und das Wort "Such" bezieht sich auf die Tatsache, dass binäre Suchbäume geordnet sind: Alle Elemente, die links unter einem Element stehen, sind kleiner als dieses Element, und alle Elemente, die rechts unter einem Element stehen, sind nicht kleiner (also größer oder gleich). Damit wird das Suchen eines bestimmten Elementes kinderleicht.

Graphen

Graphen sind Datenstrukturen, bei denen jedes Element mehrere Nachfolger und mehrere Vorgänger haben kann. Ein Anwendungsbeispiel ist das Traveling Salesman Problem, das in der Stufe Q2 oft behandelt wird. Vorgegeben ist eine endliche Anzahl von Städten mit ihren Koordinaten, und es gilt, eine möglichst kurze Rundreise durch alle Städte zu finden. Grundlage der meisten Algorithmen zur Lösung dieses Problems ist die Erzeugung einer Entfernungsmatrix, die auf verschiedene Weisen erstellt werden kann, zum Beispiel mit Hilfe eines zweidimensionalen Arrays. Aber auch ein Graph kann zur Modellierung einer solchen Tabelle herangezogen werden. Dann ist jede Stadt mit jeder anderen Stadt über eine Kante verbunden, und die Länge dieser Kante entspricht dann der Entfernung zwischen den beiden verbundenen Städten.