Datenstruktur

Eine Datenstruktur ist eine bestimmte Art Daten zur Organisation in einem Informatiksystem anzuordnen.

Bei vielen Algorithmen kann die asymptotische Laufzeit durch Verwendung bestimmter Datenstrukturen verbessert werden, z.B. bei Dijkstra's Algorithmus durch die Verwendung eines Fibonacci-Heaps. Allerdings ist diese Datenstruktur so kompliziert, dass die Laufzeit in der Theorie zwar besser wäre, praktisch gesehen der Implementierungsaufwand sowie die in das Debugging zu investierende Arbeitszeit die - relativ geringe - tatsächliche Beschleunigung des Algorithmus kaum lohnt.

In der Wikipedia werden die folgenden Datenstrukturen beschrieben:

• Arrays (auch Felder, Elemente gleichen Datentyps))
• • eindimensional (Vektoren)
  • zweidimensional (Tabellen)
  • mehrdimensional
• Bäume
• • Binärbaum
  • • Rot-Schwarz-Baum
  • Balancierter Baum
  • • AVL-Baum
    • B-Baum
    • • 2-3-4-Baum
    • B*-Baum
  • Octree
• Graph (bzw. die zugrundeliegende Datenstruktur Adjazenzliste oder Adjazenzmatrix), siehe auch Repräsentation von Graphen im Computer
• Hashtabelle (auch assoziatives Array)
• Heaps (en: Haufen, Halde)
• • Binärer Heap (eindimensionales Array)
  • Fibonacci-Heap
  • Min-Max-Heap
  • Deap
• Listen, meist verkettet
• Stack
• Verbunde, (Records, Units, Elemente unterschiedlichen Datentyps)
• Warteschlange (auch Schlange, Queue)
• • Priority Queue (normalerweise mit Hilfe von Heaps implementiert)

Genau genommen enthält obige Liste auch einige abstrakte Datentypen, die sich mit Hilfe verschiedener Datenstrukturen implementieren lassen.

Literatur

• Wirth, Niklaus (2000), Algorithmen und Datenstrukturen in Pascal, Teubner. ISBN_3519222507: der deutsche Klassiker