Datenstruktur

In der Informatik ist eine Datenstruktur eine bestimmte Art, Daten zu verwalten und miteinander zu verknüpfen, um in geeigneter Weise auf diese zugreifen und diese manipulieren zu können. Datenstrukturen sind immer mit bestimmten Operationen verknüpft, um eben diesen Zugriff und diese Manipulation zu ermöglichen.

Erklärung

Die Definition von Datenstrukturen erfolgt im Allgemeinen durch die Angabe einer konkreten Spezifikation zur Datenhaltung und der dazu nötigen Operationen. Diese konkrete Spezifikation legt das allgemeine Verhalten der Operationen fest und abstrahiert damit von der konkreten Implementation der Datenstruktur.

Wird der Schwerpunkt der Betrachtung auf die konkrete Implementation der Operationen verschoben, so wird anstelle des Begriffs Datenstruktur auch häufig von einem Abstrakten Datentypen gesprochen. Der Übergang von der Datenstruktur zu einem Abstrakten Datentyp ist dabei nicht klar definiert, sondern hängt einzig von der Betrachtungsweise ab.

Von den meisten Datenstrukturen gibt es neben ihrer Grundform viele Spezialisierungen, die eigens für die Erfüllung einer bestimmten Aufgabe spezifiziert wurden. So sind beispielsweise B-Bäume als Spezialisierung der Datenstruktur Baum besonders gut für Implementationen von Datenbanken geeignet.

Bei vielen Algorithmen hängt der Ressourcenbedarf, also sowohl die benötigte Laufzeit als auch der Speicherplatzbedarf, von der Verwendung geeigneter Datenstrukturen ab.

Grundlegende Datenstrukturen

Die folgenden Datenstrukturen sind in der Regel für die klassische imperative Programmierung entwickelt und optimiert worden. Andere Programmierparadigmen wie die funktionale Programmierung können durchaus andere Datenstrukturen erfordern.

Array (Feld)

Das Array ist die einfachste verwendete Datenstruktur. Es werden hierbei mehrere Variablen vom selben Basisdatentyp gespeichert. Ein Zugriff auf die einzelnen Elemente wird über einen Index möglich. Technisch gesehen entspricht dieser dem Wert, der zu der Startadresse des Arrays im Speicher hinzuaddiert wird, um die Adresse des Objektes zu erhalten. Die einzigen notwendigen Operationen sind das indizierte Speichern und das indizierte Lesen, die auf jedes Element des Arrays direkt zugreifen können. Im eindimensionalen Fall wird das Array häufig als Vektor und im zweidimensionalen Fall als Tabelle oder Matrix bezeichnet. Arrays sind aber keinesfalls nur auf zwei Dimensionen beschränkt, sondern werden beliebig mehrdimensional verwendet. Wegen ihrer Einfachheit und grundlegenden Bedeutung bieten die allermeisten Programmiersprachen eine konkrete Umsetzung dieser Datenstruktur als zusammengesetzten Datentyp Array im Grundsprachumfang an.

Ein Sonderfall bildet das Assoziative Array, bei dem nicht über einen numerischen Index, sondern über einen Schlüssel auf die gespeicherten Daten zugegriffen wird. Eine weitere Spezialisierung des assoziativen Arrays ist die Hashtabelle.

Liste

Die Liste ist eine Datenstruktur zur dynamischen Speicherung von beliebig vielen Objekten. Dabei beinhaltet jedes Listenelement als Besonderheit einen Verweis auf das nächste Element, wodurch die Gesamtheit der Objekte zu einer Verkettung von Objekten wird. Die zu einer Liste gehörenden Operationen sind relativ unspezifiziert. Sie werden oft in komplizierteren Datenstrukturen verwenden und statt über Operationen wird dort aus Effizienzgründen meist direkt auf ihre Elemente zugegriffen. Die in Programmbibliotheken angebotenen Listen sind in ihrer zugrunde liegenden Datenstruktur meist viel komplexer und stellen nicht selten gar keine echten Listen dar, geben sich nach außen aber als solche aus. Listen sind stets linear.

Stapelspeicher

In einem so genannten Stapelspeicher (engl. Stack) kann eine beliebige Anzahl von Objekten gespeichert, jedoch können die gespeicherten Objekte nur in umgekehrter Reihenfolge wieder gelesen werden. Dies entspricht dem LIFO-Prinzip. Für die Definition und damit die Spezifikation des Stapelspeichers ist es unerheblich, welche Objekte in ihm gespeichert werden. Zu einem Stapelspeicher gehören zumindest die Operationen

push, um ein Objekt im Stapelspeicher abzulegen und
pop, um das zuletzt gespeicherte Objekt wieder zu lesen und vom Stapel zu entfernen.
(top, um das oberste Element zu lesen, ohne es zu löschen)

Die top-Operation ist nicht zwingend vorgeschrieben wird aber oft implementiert, um pop/push zu ersetzen, da es oft interessant ist das oberste Element zu "testen". Ein Stapelspeicher wird gewöhnlich als Liste implementiert, kann aber auch ein Vektor sein.

Warteschlange

In einer Warteschlange (engl. queue) kann eine beliebige Anzahl von Objekten gespeichert werden, jedoch können die gespeicherten Objekte nur in dergleichen Reihenfolge wieder gelesen werden, wie sie gespeichert wurden. Dies entspricht dem FIFO-Prinzip. Für die Definition und damit die Spezifikation der Queue ist es unerheblich, welche Objekte in ihm gespeichert werden. Zu einer Queue gehören zumindest die Operationen

enqueue, um ein Objekt in der Warteschlange zu speichern und
dequeue, um das zuerst gespeicherte Objekt wieder zu lesen und aus der Warteschlange zu entfernen.

Eine Warteschlange wird gewöhnlich als Liste implementiert, kann aber auch ein Vektor sein.

Vorrangwarteschlange

Eine Spezialisierung der Warteschlange ist die Vorrangwarteschlange, die auch Prioritätswarteschlange bzw. engl. Priority Queue genannt wird. Dabei wird vom FIFO-Prinzip abgewichen. Die Durchführung der enqueue Operation, die in diesem Fall auch insert Operation genannt wird, sortiert das Objekt gemäß einer gegebenen Priorität, die jedes Objekt mit sich führt, in die Vorrangwarteschlange ein. Die dequeue Operation liefert immer das Objekt mit der höchsten Priorität. Vorrangwarteschlangen werden meist mit Heaps implementiert.

Graph

Ein Graph ermöglicht es als Datenstruktur die Unidirektionalität der Verknüpfung zu überwinden. Die Operationen sind auch hier das Einfügen, Löschen und Finden eines Objekts. Die bekanntesten Repräsentation von Graphen im Computer sind die Adjazenzmatrix, die Inzidenzmatrix und Adjazenzliste.

Baum

Bäume sind spezielle Formen von Graphen in der Graphentheorie. Als Datenstruktur werden meist nur Out-Trees verwendet. Dabei können ausgehend von der Wurzel mehrere gleichartige Objekte miteinander verkettet werden, so dass die lineare Struktur der Liste aufgebrochen wird und eine Verzweigung stattfindet. Da Bäume zu den meist verwendeten Datenstrukturen in der Informatik gehören, gibt es viele Spezialisierungen.

So ist bei Binärbäumen die Anzahl der Kinder höchstens zwei und in balancierten Bäumen gilt zusätzlich, dass sich die Höhen des linken und rechten Teilbaums an jedem Knoten höchstens um eins unterscheiden.

Bei Suchbäumen sind die Elemente in der Baumstruktur geordnet abgelegt, so dass man schnell Elemente im Baum finden kann. Man unterscheidet hier weiter in binäre Suchbäume mit AVL-Bäumen als balancierte Version und B-Bäumen sowie einer Variante, den B*-Bäumen. Spezialisierungen von B-Bäumen sind wiederum 2-3-4-Bäume, welche oft als Rot-Schwarz-Bäume implementiert werden.

Bäume sind in ihrem Aufbau zwar mehrdimensional jedoch in der Verkettung der Objekte oft unidirektional. Die Verkettung der gespeicherten Objekte beginnt bei der Wurzel des Baums und von dort in Richtung der Knoten des Baums.

Heap (Haufen)

Der Heap (Haufen) vereint die Datenstruktur eines Baums mit den Operationen einer Vorrangwarteschlange. Häufig hat der Heap neben den minimal nötigen Operationen wie insert, remove und extractMin auch noch weitere Operationen wie merge oder changeKey. Je nach Reihenfolge der Priorität in der Vorrangwarteschlange wird ein Min-Heap oder ein Max-Heap verwendet. Weitere Spezialisierungen des Heap sind der Binäre Heap, der Binomial-Heap und der Fibonacci-Heap. Heaps werden meistens über Bäume aufgebaut.

Treap

Der Treap vereinigt Eigenschaften von Bäumen und Heaps in sich.

Hashtable (Hashtabelle)

Die Hashtabelle bzw. Streuwerttabelle ist eine spezielle Indexstruktur. Hashtabellen eignen sich also vor allem dazu Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen, die ebenfalls als Indexstruktur dienen können. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch vom Hashverfahren.

Literatur

Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed: Grundlagen von Datenstrukturen in C, International Thomson Publishing, Bonn 1994, ISBN 3-929821-00-1
Chris Okasaki: Purely Functional Data Structures, Cambridge University Press 1999, ISBN 0521663504
Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen, 4. Auflage, Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-1029-0
Wirth, Niklaus (2000), Algorithmen und Datenstrukturen in Pascal, Teubner. ISBN 3519222507