Беларусь
Deutschland
United States
France
Қазақстан
Lietuva
Россия
ประเทศไทย
Украина
In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt welches zur Speicherung und Organisation von Dat
Datenstruktur
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 effizient zu ermöglichen.
Datenstrukturen sind nicht nur durch die enthaltenen Daten charakterisiert, sondern vor allem durch die 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 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-Bäume als Spezialisierung der Datenstruktur Baum besonders gut für Implementierungen 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.
Datensatz
Datensätze (auch '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
Das Array (auch Feld) 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 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 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.
Zuordnungstabelle
Einen Sonderfall bildet die Zuordnungstabelle (auch assoziatives Array oder Schlüssel-Wert-Paar), bei dem nicht über einen numerischen Index, sondern über einen Schlüssel auf die gespeicherten Daten zugegriffen wird. Eine mögliche Art, ein assoziatives Array zu implementieren, ist die Hashtabelle.
Menge
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
Ein Verbund (oder englisch Record) ist ein Datentyp, der aus einem oder mehreren Datentypen zusammengesetzt wurde.
(Verkettete) Liste
Die (verkettete) Liste ist eine Datenstruktur zur dynamischen Speicherung von beliebig vielen Objekten. Dabei beinhaltet jedes Listenelement einer verketteten Liste 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 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
In einer Warteschlange (englisch 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
In einem Stapelspeicher (englisch 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 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 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
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
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 bekannteste Repräsentation von Graphen im Computer sind die Adjazenzmatrix, die Inzidenzmatrix und Adjazenzliste. Planare Graphen lassen sich mittels Half-Edge-Datenstruktur abbilden.
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, 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ärbäumen die Anzahl der Kinder höchstens zwei und in höhen-balancierten Bäumen gilt zusätzlich, dass sich die Höhen des linken und rechten Teilbaums an jedem Knoten nicht zu sehr unterscheiden.
Bei geordneten Bäumen, insbesondere Suchbäumen, sind die Elemente in der Baumstruktur geordnet abgelegt, sodass man schnell Elemente im Baum finden kann. Man unterscheidet hier weiter in binäre Suchbäume mit AVL-Bäumen (darunter Fibonacci-Bäume) 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.
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
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äre Heap, der Binomial-Heap und der Fibonacci-Heap. Heaps werden meistens über Bäume aufgebaut.
Treap
Der Treap vereinigt Eigenschaften von Bäumen („Trees“) und Heaps in sich.
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
| Operation | Array | Dynamisches Array | Verlinkte Liste | Balancierter Baum | Hashtabelle |
|---|---|---|---|---|---|
| Einfügung/Löschung am Anfang | N/A | Θ(n) | Θ(1) | Θ(log n) | Θ(1) bis Θ(n) |
| Einfügung/Löschung am Ende | N/A | Θ(1) | Θ(1) | ||
| Einfügung/Löschung mittig | N/A | Θ(n) | suche + Θ(1) | ||
| Suche | Θ(n) | Θ(n) | Θ(n) | Θ(log n) | Θ(1) bis Θ(n) |
| Zusätzlicher Speicherplatz gegenüber Array | 0 | 0, Θ(n) | Θ(n) | Θ(n) | Θ(n) |
| Zugriff auf ein beliebiges/zufälliges Element | Θ(1) | Θ(1) | Θ(n) | Θ(n) | Θ(n) |
Siehe auch
- 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
- Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders: Algorithmen und Datenstrukturen. Hrsg.: Springer. Springer, Berlin Heidelberg 2014, ISBN 978-3-642-05471-6.
Einzelnachweise
- T. H. Cormen, C. E. Leiserson, R. L. Rivest & C. Stein: Introduction to Algorithms. MIT Press 2009.
- D. Baldwin & G. Scragg: Algorithms and Data Structures: The Science of Computing. CRC Press 2017.
- Dan Schmidt: Building a Better Hash. Abgerufen am 2. April 2025.
- 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.
- Gerald Kruse. CS 240 Lecture NotesCS 240 Lecture Notes (Seite dauerhaft nicht mehr abrufbar, festgestellt im April 2025. Suche in Webarchiven): Linked Lists Plus: Complexity Trade-offs ( vom 5. August 2012 im Webarchiv archive.today). Juniata College. Spring 2008.
- Unter der Annahme, dass ein Puffer für Erweiterungen vorgehalten wird.
Autor: www.NiNa.Az
Veröffentlichungsdatum:
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele, Mobiltelefon, Mobil, Telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, komputer
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 verknupft werden um den Zugriff auf sie und ihre Verwaltung effizient zu ermoglichen Datenstrukturen sind nicht nur durch die enthaltenen Daten charakterisiert sondern vor allem durch die Operationen auf diesen Daten die Zugriff und Verwaltung ermoglichen und realisieren ErklarungDie Festlegung Definition von Datenstrukturen erfolgt im Allgemeinen durch eine exakte Beschreibung Spezifikation zur Datenhaltung und der dazu notigen 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 haufig von einem abstrakten Datentyp gesprochen Der Ubergang von der Datenstruktur zu einem abstrakten Datentyp ist dabei nicht klar definiert sondern hangt einzig von der Betrachtungsweise ab Mit Blick auf den oft veranderlichen 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 fur die Erfullung einer bestimmten Aufgabe spezifiziert wurden So sind beispielsweise B Baume als Spezialisierung der Datenstruktur Baum besonders gut fur Implementierungen von Datenbanken geeignet Bei vielen Algorithmen hangt der Ressourcenbedarf also sowohl die benotigte Laufzeit als auch der Speicherplatzbedarf von der Verwendung geeigneter Datenstrukturen ab Grundlegende DatenstrukturenDie folgenden Datenstrukturen sind in der Regel fur die klassische imperative Programmierung entwickelt und optimiert worden Andere Programmierparadigmen wie die funktionale Programmierung konnen durchaus andere Datenstrukturen erfordern Datensatz Hauptartikel Datensatz Datensatze auch Tupel sind die einfachsten Datenstrukturen Sie verkorpern ublicherweise in einer fest definierten Anzahl und Folge Werte die andere Werte enthalten Datensatze 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 Basisdatentyp gespeichert Ein Zugriff auf die einzelnen Elemente wird uber einen Index moglich 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 konnen Im eindimensionalen Fall wird das Array haufig als Vektor und im zweidimensionalen Fall als Tabelle oder Matrix bezeichnet Arrays sind aber keinesfalls nur auf zwei Dimensionen beschrankt 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 fur die Verwendung von Arrays ist die Speicherung von Noten in einem Notenheft Angenommen wir haben ein Notenbuch mit Platz fur 10 Noten Wir konnen Arrays verwenden um diese Noten effizient zu speichern Jede Note wird anhand ihres Index im Array gespeichert Zuordnungstabelle Hauptartikel Zuordnungstabelle Einen Sonderfall bildet die Zuordnungstabelle auch assoziatives Array oder Schlussel Wert Paar bei dem nicht uber einen numerischen Index sondern uber einen Schlussel auf die gespeicherten Daten zugegriffen wird Eine mogliche 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 Schlussel auf konkrete Werte zugegriffen werden Die Menge entspricht einer Zuordnungstabelle mit Schlusseln die nur einmalig vorkommen konnen aber ohne Werte Verbund Hauptartikel Verbund Datentyp Ein Verbund oder englisch 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 Verweis auf das nachste Element wodurch die Gesamtheit der Objekte zu einer Verkettung von Objekten wird Die zu einer Liste gehorenden Operationen sind relativ unspezifiziert Sie werden oft in komplizierteren Datenstrukturen verwendet und statt uber Operationen wird dort aus Effizienzgrunden 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 aussen aber als solche aus Listen sind stets lineare Strukturen Werden Vorganger und Nachfolger bidirektional verkettet so spricht man von einer doppelt verketteten Liste Warteschlange Hauptartikel Warteschlange Datenstruktur In einer Warteschlange englisch queue kann eine beliebige Anzahl von Objekten gespeichert werden jedoch konnen die gespeicherten Objekte nur in der gleichen Reihenfolge wieder gelesen werden wie sie gespeichert wurden Dies entspricht dem FIFO Prinzip Fur die Definition und damit die Spezifikation der Queue ist es unerheblich welche Objekte in ihr gespeichert werden Zu einer Queue gehoren 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 gewohnlich 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 englisch stack kann eine beliebige Anzahl von Objekten gespeichert werden jedoch konnen die gespeicherten Objekte nur in umgekehrter Reihenfolge wieder gelesen werden Dies entspricht dem LIFO Prinzip Fur die Definition und damit die Spezifikation des Stapelspeichers ist es unerheblich welche Objekte in ihm gespeichert werden Zu einem Stapelspeicher gehoren 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 oder peek um das oberste Element zu lesen ohne es zu loschen 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 gewohnlich als Liste implementiert kann aber auch ein Vektor sein Ein Beispiel fur 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 ahnlich der Warteschlange oder des Stapelspeichers Es kombiniert die Eigenschaften beider Datenstrukturen Der Unterschied besteht darin dass die Daten an beiden Enden gelesen eingefugt oder entfernt werden konnen Vorrangwarteschlange Hauptartikel Vorrangwarteschlange Eine Spezialisierung der Warteschlange ist die Vorrangwarteschlange die auch Prioritatswarteschlange bzw engl Priority Queue genannt wird Dabei wird vom FIFO Prinzip abgewichen Die Durchfuhrung der enqueue Operation die in diesem Fall auch insert Operation genannt wird sortiert das Objekt gemass einer gegebenen Prioritat die jedes Objekt mit sich fuhrt in die Vorrangwarteschlange ein Die dequeue Operation liefert immer das Objekt mit der hochsten Prioritat Vorrangwarteschlangen werden meist mit Heaps implementiert Graph Hauptartikel Graph Graphentheorie und Graphentheorie Ein Graph ermoglicht es als Datenstruktur die Unidirektionalitat der Verknupfung zu uberwinden Die Operationen sind auch hier das Einfugen Loschen und Finden eines Objekts Die bekannteste Reprasentation 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 Baume sind spezielle Formen von Graphen in der Graphentheorie Als Datenstruktur werden meist nur Out Trees verwendet Dabei konnen ausgehend von der Wurzel mehrere gleichartige Objekte miteinander verkettet werden sodass die lineare Struktur der Liste aufgebrochen wird und eine Verzweigung stattfindet Da Baume zu den meist verwendeten Datenstrukturen in der Informatik gehoren gibt es viele Spezialisierungen So betragt bei Binarbaumen die Anzahl der Kinder hochstens zwei und in hohen balancierten Baumen gilt zusatzlich dass sich die Hohen des linken und rechten Teilbaums an jedem Knoten nicht zu sehr unterscheiden Bei geordneten Baumen insbesondere Suchbaumen sind die Elemente in der Baumstruktur geordnet abgelegt sodass man schnell Elemente im Baum finden kann Man unterscheidet hier weiter in binare Suchbaume mit AVL Baumen darunter Fibonacci Baume als balancierte Version und B Baumen sowie einer Variante den B Baumen Spezialisierungen von B Baumen sind wiederum 2 3 4 Baume welche oft als Rot Schwarz Baume implementiert werden Nicht sortiert aber verschachtelt sind geometrische Baumstrukturen wie der R Baum und seine Varianten Hier werden nur diejenigen Teilbaume durchsucht die sich mit dem angefragten Bereich uberlappen Baume 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 Haufig hat der Heap neben den minimal notigen Operationen wie insert remove und extractMin auch noch weitere Operationen wie merge oder changeKey Je nach Reihenfolge der Prioritat in der Vorrangwarteschlange wird ein Min Heap oder ein Max Heap verwendet Weitere Spezialisierungen des Heap sind der Binare Heap der Binomial Heap und der Fibonacci Heap Heaps werden meistens uber Baume aufgebaut Treap Hauptartikel Treap Der Treap vereinigt Eigenschaften von Baumen 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 konnen aber einen grosseren Verwaltungsaufwand benotigen um den Index bereitzustellen Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch vom Hashverfahren Bei sehr grossen Datenmengen kann eine verteilte Hashtabelle zum Einsatz kommen Speicher und Rechenaufwand von DatenstrukturenOperation Array Dynamisches Array Verlinkte Liste Balancierter Baum HashtabelleEinfugung Loschung am Anfang N A 8 n 8 1 8 log n 8 1 bis 8 n Einfugung Loschung am Ende N A 8 1 8 1 Einfugung Loschung mittig N A 8 n suche 8 1 Suche 8 n 8 n 8 n 8 log n 8 1 bis 8 n Zusatzlicher Speicherplatz gegenuber Array 0 0 8 n 8 n 8 n 8 n Zugriff auf ein beliebiges zufalliges Element 8 1 8 1 8 n 8 n 8 n Siehe auchCommons Datenstruktur Sammlung von Bildern Videos und Audiodateien KontrollstrukturLiteraturEllis 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 Martin Dietzfelbinger Kurt Mehlhorn Peter Sanders Algorithmen und Datenstrukturen Hrsg Springer Springer Berlin Heidelberg 2014 ISBN 978 3 642 05471 6 EinzelnachweiseT H Cormen C E Leiserson R L Rivest amp C Stein Introduction to Algorithms MIT Press 2009 D Baldwin amp G Scragg Algorithms and Data Structures The Science of Computing CRC Press 2017 Dan Schmidt Building a Better Hash Abgerufen am 2 April 2025 Unter der Annahme dass die verlinkte Liste sich einen Pointer der Datenendposition merkt sonst muss erst das Ende der Liste mit dem Zeitaufwand 8 n ermittelt werden Gerald Kruse CS 240 Lecture Notes 1 2 CS 240 Lecture Notes Seite dauerhaft nicht mehr abrufbar festgestellt im April 2025 Suche in Webarchiven Linked Lists Plus Complexity Trade offs Memento vom 5 August 2012 im Webarchiv archive today Juniata College Spring 2008 Unter der Annahme dass ein Puffer fur Erweiterungen vorgehalten wird