Dies ist eine Liste bekannter Datenstrukturen . Eine umfassendere Liste von Begriffen finden Sie unter „ Liste der Begriffe zu Algorithmen und Datenstrukturen“ . Einen Vergleich der Laufzeiten für eine Teilmenge dieser Liste finden Sie unter „Vergleich von Datenstrukturen“ .

Datentypen

Primitive Typen

Zusammengesetzte Datentypen oder nicht-primitive Datentypen

  • Ein Array ist eine Folge von Elementen desselben Typs, die zusammenhängend im Speicher abgelegt sind.
  • Datensatz (auch Struktur oder Struct genannt ), eine Sammlung von Feldern
  • Produkttyp (auch Tupel genannt), ein Datensatz, in dem die Felder nicht benannt sind
  • Zeichenkette , eine Folge von Zeichen, die Text darstellt
  • Union , ein Datum, das zu einer Menge von Typen gehören kann
  • Getaggte Union (auch Variante , diskriminierte Union oder Summentyp genannt ), eine Union mit einem Tag, der den Datentyp angibt.

Abstrakte Datentypen

Einige Eigenschaften abstrakter Datentypen:

Struktur Bestellt? Einzigartigkeit?
ListeJa NEIN
Assoziatives ArrayNEIN nur Schlüssel (Indizes)
SatzNEIN Ja
StapelJa NEIN
MultimapNEIN NEIN
Multiset (Beutel)NEIN NEIN
WarteschlangeJa NEIN

„Geordnet“ bedeutet, dass die Elemente des Datentyps eine explizite Reihenfolge aufweisen, wobei ein Element als „vor“ oder „nach“ einem anderen Element betrachtet werden kann. Diese Reihenfolge wird üblicherweise durch die Reihenfolge bestimmt, in der die Elemente der Struktur hinzugefügt werden. In bestimmten Kontexten, wie beispielsweise beim Sortieren einer Liste, können die Elemente jedoch neu angeordnet werden. Bei einer ungeordneten Struktur hingegen lassen sich keine Annahmen über die Reihenfolge der Elemente treffen (obwohl eine physikalische Implementierung dieser Datentypen häufig eine beliebige Reihenfolge anwendet). „Eindeutigkeit“ bedeutet, dass doppelte Elemente nicht zulässig sind. Je nach Implementierung des Datentyps kann der Versuch, ein doppeltes Element hinzuzufügen, entweder ignoriert, das vorhandene Element überschrieben oder ein Fehler ausgelöst werden. Die Erkennung von Duplikaten basiert auf einer integrierten (oder alternativ benutzerdefinierten) Regel zum Vergleich von Elementen.

Lineare Datenstrukturen

Eine Datenstruktur heißt linear, wenn ihre Elemente eine Sequenz bilden.

Arrays

Listen

Bäume

Bäume sind eine Teilmenge der gerichteten azyklischen Graphen .

Binärbäume

B-Bäume

Haufen

Bit-Slice-Bäume

In diesen Datenstrukturen vergleicht jeder Baumknoten einen Bitausschnitt von Schlüsselwerten.

Mehrwegebäume

Raumpartitionierungsbäume

Hierbei handelt es sich um Datenstrukturen, die zur Speicherplatzpartitionierung oder binären Speicherplatzpartitionierung verwendet werden .

Anwendungsspezifische Bäume

Hash-basierte Strukturen

Diagramme

Viele graphenbasierte Datenstrukturen werden in der Informatik und verwandten Bereichen verwendet:

Andere

Siehe auch