Quelltext der Seite Datenstruktur

[[Datei:Python 3. The standard type hierarchy.png|mini]]

In der [[Informatik]] und [[Softwaretechnik]] ist eine '''Datenstruktur''' ein Objekt, welches zur Speicherung und Organisation von [[Daten]] dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung [[Effizienz (Informatik)|effizient]] zu ermöglichen.

Datenstrukturen sind nicht nur durch die enthaltenen Daten charakterisiert, sondern vor allem durch die [[Operation (Informatik)|Operationen]] auf diesen Daten, die Zugriff und Verwaltung ermöglichen und realisieren.

== Erklärung ==
Die Festlegung (''Definition'') von Datenstrukturen erfolgt im Allgemeinen durch eine exakte Beschreibung (''[[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 Implementierung der Datenstruktur.

Wird der Schwerpunkt der Betrachtung nicht auf die konkrete Implementierung der Operationen verschoben, so wird anstelle des Begriffs Datenstruktur auch häufig von einem [[Abstrakter Datentyp|abstrakten Datentyp]] gesprochen. Der Übergang von der Datenstruktur zu einem abstrakten Datentyp ist dabei nicht klar definiert, sondern hängt einzig von der Betrachtungsweise ab. Mit Blick auf den oft veränderlichen Speicherbedarf vieler Datenstrukturen wird dann auch von ''dynamischen Datentypen'' gesprochen, denen technisch eine [[dynamische Speicherverwaltung]] zugrunde liegt.

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-Baum|B-Bäume]] als Spezialisierung der Datenstruktur Baum besonders gut für Implementierungen von [[Datenbank]]en geeignet.

Bei vielen [[Algorithmus|Algorithmen]] hängt der Ressourcenbedarf, also sowohl die benötigte [[Asymptotische Laufzeit|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 [[Programmierparadigma|Programmierparadigmen]] wie die [[funktionale Programmierung]] können durchaus andere Datenstrukturen erfordern.

=== Datensatz ===
{{Hauptartikel|Datensatz}}
Datensätze (auch [[Tupel (Informatik)|'Tupel']]) sind die einfachsten Datenstrukturen. Sie verkörpern üblicherweise in einer fest definierten Anzahl und Folge Werte, die andere Werte enthalten. Datensätze identifizieren sich meist durch eines oder mehrere der in ihnen enthaltenen Elemente, oft [[Datenfeld]] genannt.

=== Array ===
{{Hauptartikel|Array (Datentyp)}}
Das Array (auch ''Feld'') ist die einfachste verwendete Datenstruktur. Es werden hierbei mehrere Variablen vom selben Basis[[datentyp]] 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 addiert 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 (Mathematik)|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 Beispiel für die Verwendung von Arrays ist die Speicherung von Noten in einem Notenheft. Angenommen, wir haben ein Notenbuch mit Platz für 10 Noten. Wir können Arrays verwenden, um diese Noten effizient zu speichern. Jede Note wird anhand ihres Index im Array gespeichert.<ref>T. H. Cormen, C. E. Leiserson, R. L. Rivest & C. Stein: ''Introduction to Algorithms.'' MIT Press 2009. </ref>

==== Zuordnungstabelle ====
{{Hauptartikel|Zuordnungstabelle}}
Einen Sonderfall bildet die Zuordnungstabelle (auch assoziatives Array oder Schlüssel-Wert-Paar), bei dem nicht über einen numerischen Index, sondern über einen [[Nummerung|Schlüssel]] auf die gespeicherten Daten zugegriffen wird. Eine mögliche Art, ein assoziatives Array zu implementieren, ist die [[Hashtabelle]].

==== Menge ====
{{Hauptartikel|Menge (Datenstruktur)}}
Einen weiteren Sonderfall bildet die Menge. Sie ist ungeordnet. Es kann nicht mittels Index oder Schlüssel auf konkrete Werte zugegriffen werden. Die Menge entspricht einer Zuordnungstabelle mit Schlüsseln, die nur einmalig vorkommen können, aber ohne Werte.

=== Verbund ===
{{Hauptartikel|Verbund (Datentyp)}}
Ein Verbund (oder {{enS|Record}}) ist ein [[Datentyp]], der aus einem oder mehreren Datentypen zusammengesetzt wurde.

=== (Verkettete) Liste ===
{{Hauptartikel|Liste (Datenstruktur)}}
Die (verkettete) Liste ist eine Datenstruktur zur dynamischen Speicherung von beliebig vielen Objekten. Dabei beinhaltet jedes Listenelement einer verketteten Liste als Besonderheit einen [[Zeiger (Informatik)|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 verwendet 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 lineare Strukturen. Werden Vorgänger und Nachfolger bidirektional verkettet, so spricht man von einer doppelt-verketteten Liste.

=== Warteschlange ===
{{Hauptartikel|Warteschlange (Datenstruktur)}}
In einer Warteschlange ({{enS|queue}}) kann eine beliebige Anzahl von Objekten gespeichert werden, jedoch können die gespeicherten Objekte nur in der gleichen 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 ihr 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 verkettete Liste implementiert, kann intern aber auch ein Array verwenden; in diesem Fall ist die Anzahl der Elemente begrenzt.

==== Stapelspeicher ====
{{Hauptartikel|Stapelspeicher}}
In einem Stapelspeicher ({{enS|stack}}) kann eine beliebige Anzahl von Objekten gespeichert werden, jedoch können die gespeicherten Objekte nur in umgekehrter Reihenfolge wieder gelesen werden. Dies entspricht dem [[Last In – First Out|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<ref>D. Baldwin & G. Scragg: ''Algorithms and Data Structures: The Science of Computing.'' CRC Press 2017.</ref>

* ''push'', um ein Objekt im Stapelspeicher abzulegen und
* ''pop'', um das zuletzt gespeicherte Objekt wieder zu lesen und vom Stapel zu entfernen.
* (''top'' oder ''peek'', 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.

Ein  Beispiel für die Verwendung von Stapeln ist die Verlaufsfunktion des Browsers. Wenn wir im Internet surfen und verschiedene Websites besuchen, werden die besuchten Seiten normalerweise in der Verlaufsliste gespeichert.

==== Deque ====
{{Hauptartikel|Deque}}
Bei der Deque (Double-ended queue) handelt es sich um eine Datenstruktur ähnlich der Warteschlange oder des Stapelspeichers. Es kombiniert die Eigenschaften beider Datenstrukturen. Der Unterschied besteht darin, dass die Daten an beiden Enden gelesen, eingefügt oder entfernt werden können.

==== Vorrangwarteschlange ====
{{Hauptartikel|Vorrangwarteschlange}}
Eine Spezialisierung der Warteschlange ist die Vorrangwarteschlange, die auch ''Prioritätswarteschlange'' bzw. engl. {{lang|en|''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 [[Heap (Datenstruktur)|Heaps]] implementiert.

=== Graph ===
{{Hauptartikel|Graph (Graphentheorie)|Graphentheorie}}
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 bekannteste Repräsentation von Graphen im Computer sind die [[Adjazenzmatrix]], die [[Inzidenzmatrix]] und [[Adjazenzliste]]. Planare Graphen lassen sich mittels [[Half-Edge-Datenstruktur]] abbilden.

=== Baum ===
{{Hauptartikel|Baum (Datenstruktur)}}
{{Hauptartikel|Baum (Graphentheorie)}}

Bäume sind spezielle Formen von Graphen in der [[Graphentheorie]]. Als Datenstruktur werden meist nur [[Out-Tree]]s verwendet. Dabei können ausgehend von der [[Wurzel (Graphentheorie)|Wurzel]] mehrere gleichartige Objekte miteinander verkettet werden, sodass 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 beträgt bei [[Binärbaum|Binärbäumen]] die Anzahl der Kinder höchstens zwei und in [[Balancierter Baum#Höhenbalance|höhen-balancierten Bäumen]] gilt zusätzlich, dass sich die [[Höhe (Graphentheorie)|Höhen]] des linken und rechten Teilbaums an jedem [[Knoten (Graphentheorie)|Knoten]] nicht zu sehr unterscheiden.

Bei geordneten Bäumen, insbesondere [[Suchbaum|Suchbäumen]], sind die Elemente in der Baumstruktur [[Ordnungsrelation|geordnet]] abgelegt, sodass man schnell Elemente im Baum finden kann. Man unterscheidet hier weiter in [[Binärer Suchbaum|binäre Suchbäume]] mit [[AVL-Baum|AVL-Bäumen]] (darunter [[Fibonacci-Baum|Fibonacci-Bäume]]) als balancierte Version und [[B-Baum|B-Bäumen]] sowie einer Variante, den [[B*-Baum|B*-Bäumen]]. Spezialisierungen von B-Bäumen sind wiederum [[2-3-4-Baum|2-3-4-Bäume]], welche oft als [[Rot-Schwarz-Baum|Rot-Schwarz-Bäume]] implementiert werden.

Nicht sortiert, aber „verschachtelt“ sind geometrische Baumstrukturen wie der [[R-Baum]] und seine Varianten. Hier werden nur diejenigen Teilbäume durchsucht, die sich mit dem angefragten Bereich überlappen.

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 ===
{{Hauptartikel|Heap (Datenstruktur)}}
Der Heap (auch Halde oder 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ärer Heap|Binäre Heap]], der [[Binomial-Heap]] und der [[Fibonacci-Heap]]. Heaps werden meistens über Bäume aufgebaut.

==== Treap ====
{{Hauptartikel|Treap}}
Der Treap vereinigt Eigenschaften von Bäumen („Trees“) und Heaps in sich.

=== Hashtabelle ===
{{Hauptartikel|Hashtabelle}}
Die Hashtabelle bzw. Streuwerttabelle ist eine spezielle [[Indexstruktur]], bei der die Speicherposition direkt berechnet werden kann. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen, die im Gegensatz zu Hashtabellen alle Indexwerte in einer Ordnung wiedergeben können, aber einen größeren Verwaltungsaufwand benötigen, um den Index bereitzustellen. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch vom ''Hashverfahren''. Bei sehr großen Datenmengen kann eine [[verteilte Hashtabelle]] zum Einsatz kommen.

== Speicher- und Rechenaufwand von Datenstrukturen ==
{|class="wikitable sortable"
!Operation!![[Array (Datentyp)|Array]]!!Dynamisches<br />Array !!Verlinkte<br />[[Liste (Datenstruktur)|Liste]]!!Balancierter<br />[[Balancierter Baum|Baum]] !![[Hashtabelle]]
|-
|Einfügung/Löschung<br /> am Anfang
|style="background:#eeeeee"|''N/A''
|style="background:#ffdddd"|[[Landau-Symbole|Θ]](''n'') <!-- Verlinkung des Landau-Symbols 'Θ' -->
|style="background:#ddffdd"|Θ(1)
|rowspan="3" style="background:#ffffdd"|Θ(''log n'')
|rowspan="3" style="background:#ffffdd"|Θ(''1'') bis Θ(''n'')<ref>{{Internetquelle |autor=Dan Schmidt |url=http://dfan.org/real/tpj_hash.html |titel=Building a Better Hash |abruf=2025-04-02}}</ref>
|-
|Einfügung/Löschung<br /> am Ende
|style="background:#eeeeee"|''N/A''
|style="background:#ddffdd"|Θ(1)
|style="background:#ddffdd"|Θ(1)<ref>Unter der Annahme, dass die verlinkte Liste sich einen Pointer der Datenendposition merkt, sonst muss erst das Ende der Liste mit dem Zeitaufwand Θ(''n'') ermittelt werden.</ref>
|-
|Einfügung/Löschung<br /> mittig
|style="background:#eeeeee"|''N/A''
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ddffdd"|suche +<br />Θ(1)<ref>Gerald Kruse. {{Toter Link |datum=2025-04 |url=http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm |text=CS 240 Lecture Notes |fix-attempted=1}}: {{Webarchiv |url=http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm |text=Linked Lists Plus: Complexity Trade-offs |archive-today=20120805083210}}. Juniata College. Spring 2008.</ref>
|-
|Suche
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffffdd"|Θ(''log n'')
|style="background:#ffffdd"|Θ(''1'') bis Θ(''n'')
|-
|Zusätzlicher Speicherplatz<br />gegenüber Array
|style="background:#ddffdd"|0
|style="background:#ffffdd"|0, Θ(''n'')<ref>Unter der Annahme, dass ein Puffer für Erweiterungen vorgehalten wird.</ref>
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffdddd"|Θ(''n'')
|-
|Zugriff auf ein beliebiges/zufälliges Element
|style="background:#ddffdd"|Θ(1)
|style="background:#ddffdd"|Θ(1)
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ffdddd"|Θ(''n'')
|}

== Siehe auch ==
{{Commonscat|Data structures|Datenstruktur}}
* [[Kontrollstruktur]]

== 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, Cambridge 1999, ISBN 0-521-66350-4
* Thomas Ottmann, Peter Widmayer: ''Algorithmen und Datenstrukturen''. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-1029-0.
* Hanan Samet: ''Foundations of Multidimensional and Metric Data Structures.'' Elsevier, Amsterdam 2006, ISBN 0-12-369446-9
* [[Niklaus Wirth]]: ''Algorithmen und Datenstrukturen in Pascal''. 5. Auflage. Teubner, Stuttgart 2000, ISBN 3-519-22250-7
* {{Literatur |Autor=Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders |Titel=Algorithmen und Datenstrukturen |Hrsg=Springer |Verlag=Springer |Ort=Berlin Heidelberg |Datum=2014 |ISBN=978-3-642-05471-6 }}

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur| ]]
[[Kategorie:Elektronischer Datenaustausch|!Datenstruktur]]