Datenstruktur

Kernidee und Zweck

Eine Datenstruktur ist in Informatik und Softwaretechnik ein Objekt zur Speicherung und Organisation von Daten. Sie heißt Struktur, weil die Daten in einer bestimmten Weise angeordnet und verknüpft werden, damit Zugriff und Verwaltung effizient möglich sind. Datenstrukturen werden nicht nur durch die gespeicherten Daten beschrieben, sondern vor allem durch die Operationen, mit denen man auf diese Daten zugreift und sie verwaltet.

Datenstrukturen werden meist durch eine genaue Spezifikation festgelegt: Sie beschreibt die Datenhaltung und die nötigen Operationen. Diese Spezifikation legt das allgemeine Verhalten fest und abstrahiert von der konkreten Implementierung. Wenn der Blick stärker auf das Verhalten als auf die konkrete Umsetzung gerichtet ist, spricht man oft von einem abstrakten Datentyp. Der Übergang zwischen Datenstruktur und abstraktem Datentyp ist nicht klar definiert, sondern hängt von der Betrachtungsweise ab. Weil viele Datenstrukturen einen veränderlichen Speicherbedarf haben, werden sie auch als dynamische Datentypen bezeichnet; technisch liegt ihnen dann dynamische Speicherverwaltung zugrunde.

Von vielen Datenstrukturen gibt es Spezialisierungen für bestimmte Aufgaben. Ein Beispiel sind B-Bäume, die als Spezialisierung der Baum-Datenstruktur besonders gut für Implementierungen von Datenbanken geeignet sind. Bei vielen Algorithmen hängt der Ressourcenbedarf, also Laufzeit und Speicherplatzbedarf, wesentlich davon ab, ob geeignete Datenstrukturen verwendet werden.

Lineare und einfache Strukturen

Die grundlegenden Datenstrukturen wurden vor allem für die klassische imperative Programmierung entwickelt und optimiert. Andere Programmierparadigmen, zum Beispiel die funktionale Programmierung, können andere Datenstrukturen erfordern.

Ein Datensatz, auch Tupel genannt, gehört zu den einfachsten Datenstrukturen. Er enthält üblicherweise eine fest definierte Anzahl und Folge von Werten, die andere Werte enthalten können. Datensätze werden meist durch eines oder mehrere ihrer Elemente identifiziert; solche Elemente heißen oft Datenfelder. Ein Verbund, englisch Record, ist ein Datentyp, der aus einem oder mehreren Datentypen zusammengesetzt wurde.

Ein Array, auch Feld genannt, speichert mehrere Variablen desselben Basisdatentyps. Der Zugriff erfolgt über einen Index. Technisch entspricht der Index dem Wert, der zur Startadresse des Arrays im Speicher addiert wird, um die Adresse des gesuchten Objekts zu erhalten. Die grundlegenden Operationen sind indiziertes Speichern und indiziertes Lesen; beide können direkt auf jedes Element zugreifen. Ein eindimensionales Array heißt häufig Vektor, ein zweidimensionales Array Tabelle oder Matrix. Arrays sind aber nicht auf zwei Dimensionen beschränkt. Wegen ihrer Einfachheit und Bedeutung bieten die meisten Programmiersprachen Arrays als zusammengesetzten Datentyp im Grundsprachumfang an. Als Beispiel nennt der Artikel ein Notenheft mit Platz für 10 Noten, bei dem jede Note über ihren Index gespeichert wird.

Eine Zuordnungstabelle, auch assoziatives Array oder Schlüssel-Wert-Paar, ist ein Sonderfall: Der Zugriff erfolgt nicht über einen numerischen Index, sondern über einen Schlüssel. Eine mögliche Implementierung ist die Hashtabelle. Eine Menge ist ebenfalls ein Sonderfall. Sie ist ungeordnet, und man kann nicht per Index oder Schlüssel auf konkrete Werte zugreifen. Sie entspricht einer Zuordnungstabelle mit Schlüsseln, die nur einmalig vorkommen können, aber ohne Werte.

Eine verkettete Liste speichert dynamisch beliebig viele Objekte. Jedes Listenelement enthält einen Verweis auf das nächste Element, sodass eine Verkettung entsteht. Listen sind lineare Strukturen. Wenn Vorgänger und Nachfolger in beide Richtungen verbunden sind, spricht man von einer doppelt verketteten Liste. Die Operationen einer Liste sind im Artikel als relativ unspezifiziert beschrieben; in komplexeren Datenstrukturen wird aus Effizienzgründen oft direkt auf ihre Elemente zugegriffen.

Warteschlangen, Stapel und Prioritäten

Eine Warteschlange, englisch queue, speichert beliebig viele Objekte, gibt sie aber nur in derselben Reihenfolge wieder aus, in der sie gespeichert wurden. Dieses Prinzip heißt FIFO, also First In, First Out. Zu einer Queue gehören mindestens die Operationen enqueue, um ein Objekt zu speichern, und dequeue, um das zuerst gespeicherte Objekt zu lesen und aus der Warteschlange zu entfernen. Für die Spezifikation ist unerheblich, welche Art von Objekten gespeichert wird. Eine Warteschlange wird gewöhnlich als verkettete Liste implementiert, kann intern aber auch ein Array verwenden; dann ist die Anzahl der Elemente begrenzt.

Ein Stapelspeicher, englisch stack, speichert ebenfalls beliebig viele Objekte, gibt sie aber in umgekehrter Reihenfolge wieder aus. Das ist das LIFO-Prinzip, also Last In, First Out. Mindestens nötig sind push, um ein Objekt abzulegen, und pop, um das zuletzt gespeicherte Objekt zu lesen und vom Stapel zu entfernen. Häufig gibt es zusätzlich top oder peek, um das oberste Element zu lesen, ohne es zu löschen. Diese Operation ist nicht zwingend, wird aber oft implementiert, weil man das oberste Element häufig testen möchte. Ein Stapelspeicher wird gewöhnlich als Liste implementiert, kann aber auch ein Vektor sein. Als Beispiel nennt der Artikel die Verlaufsfunktion eines Browsers, bei der besuchte Seiten in einer Verlaufsliste gespeichert werden.

Eine Deque, kurz für Double-ended queue, ähnelt Warteschlange und Stapelspeicher und kombiniert Eigenschaften beider. Der Unterschied ist, dass Daten an beiden Enden gelesen, eingefügt oder entfernt werden können.

Eine Vorrangwarteschlange, auch Prioritätswarteschlange oder Priority Queue, ist eine Spezialisierung der Warteschlange. Sie weicht vom FIFO-Prinzip ab. Die enqueue-Operation, hier auch insert genannt, sortiert jedes Objekt gemäß einer mitgeführten Priorität ein. Die dequeue-Operation liefert immer das Objekt mit der höchsten Priorität. Vorrangwarteschlangen werden meist mit Heaps implementiert.

Graphen, Bäume und Heaps

Ein Graph ist eine Datenstruktur, mit der die einseitige, lineare Verknüpfung überwunden werden kann. Typische Operationen sind Einfügen, Löschen und Finden eines Objekts. Bekannte Darstellungen von Graphen im Computer sind Adjazenzmatrix, Inzidenzmatrix und Adjazenzliste. Planare Graphen lassen sich mit einer Half-Edge-Datenstruktur abbilden.

Bäume sind spezielle Formen von Graphen. Als Datenstruktur werden meist Out-Trees verwendet. Von einer Wurzel aus können mehrere gleichartige Objekte miteinander verkettet werden, wodurch die lineare Struktur einer Liste aufgebrochen wird und Verzweigungen entstehen. Bäume gehören zu den meist verwendeten Datenstrukturen in der Informatik und haben viele Spezialisierungen. Bei Binärbäumen hat jeder Knoten höchstens zwei Kinder. Bei höhen-balancierten Bäumen unterscheiden sich die Höhen des linken und rechten Teilbaums an jedem Knoten nicht zu stark.

Bei geordneten Bäumen, besonders Suchbäumen, sind die Elemente so in der Baumstruktur abgelegt, dass man sie schnell finden kann. Dazu gehören binäre Suchbäume, AVL-Bäume als balancierte Version, darunter Fibonacci-Bäume, außerdem B-Bäume und B*-Bäume. Spezialisierungen von B-Bäumen sind 2-3-4-Bäume, die oft als Rot-Schwarz-Bäume implementiert werden. Nicht sortiert, aber verschachtelt sind geometrische Baumstrukturen wie der R-Baum und seine Varianten; dort werden nur Teilbäume durchsucht, die sich mit dem angefragten Bereich überlappen. Bäume sind im Aufbau mehrdimensional, in der Verkettung der Objekte aber oft unidirektional: Sie beginnt bei der Wurzel und führt zu den Knoten.

Ein Heap, auch Halde oder Haufen, verbindet die Datenstruktur eines Baums mit den Operationen einer Vorrangwarteschlange. Neben den minimal nötigen Operationen insert, remove und extractMin gibt es häufig weitere Operationen wie merge oder changeKey. Je nach Prioritätsreihenfolge verwendet man einen Min-Heap oder einen Max-Heap. Spezialisierungen sind der Binäre Heap, der Binomial-Heap und der Fibonacci-Heap. Heaps werden meistens über Bäume aufgebaut. Ein Treap vereinigt Eigenschaften von Trees, also Bäumen, und Heaps.

Hashtabellen und Aufwand

Eine Hashtabelle, auch Streuwerttabelle, ist eine spezielle Indexstruktur, bei der die Speicherposition direkt berechnet werden kann. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man vom Hashverfahren. Hashtabellen stehen in Konkurrenz zu Baumstrukturen: Bäume können alle Indexwerte in einer Ordnung wiedergeben, benötigen dafür aber einen größeren Verwaltungsaufwand, um den Index bereitzustellen. Bei sehr großen Datenmengen kann eine verteilte Hashtabelle verwendet werden.

Der Speicher- und Rechenaufwand verschiedener Datenstrukturen wird im Artikel mit Θ-Notation angegeben. Diese beschreibt das asymptotische Wachstum des Aufwands. Beim Zugriff auf ein beliebiges Element benötigen Array und dynamisches Array Θ(1), eine verlinkte Liste Θ(n), ein balancierter Baum Θ(n) und eine Hashtabelle Θ(n). Die Suche benötigt beim Array, dynamischen Array und der verlinkten Liste jeweils Θ(n), beim balancierten Baum Θ(log n) und bei der Hashtabelle Θ(1) bis Θ(n).

Einfügung und Löschung am Anfang sind beim Array nicht anwendbar, beim dynamischen Array Θ(n), bei der verlinkten Liste Θ(1), beim balancierten Baum Θ(log n) und bei der Hashtabelle Θ(1) bis Θ(n). Einfügung und Löschung am Ende sind beim Array nicht anwendbar, beim dynamischen Array Θ(1) und bei der verlinkten Liste Θ(1). Für Einfügung und Löschung in der Mitte nennt der Artikel beim Array nicht anwendbar, beim dynamischen Array Θ(n) und bei der verlinkten Liste Suche + Θ(1). Der zusätzliche Speicherplatz gegenüber einem Array beträgt beim Array 0, beim dynamischen Array 0 oder Θ(n), und bei verlinkter Liste, balanciertem Baum und Hashtabelle jeweils Θ(n).