Informatik-Lexikon

Eine Datenstruktur ist aus einfachen Datentypen zusammengesetzt. Als einfachste Datenstruktur wird der Array angesehen, der aus endlich vielen Elementen des gleichen Datentyps besteht. Andere Datenstrukturen sind einfach oder doppelt verkettete dynamische Listen, dynamische Binärbäume etc.

Bei einer Datenstruktur wird genau angegeben, wie sie zu implementieren ist. Eine dynamische Liste beispielsweise besteht aus Knoten mit je einer Wert-Eigenschaft und einem Nachfolger auf den nächsten Knoten. Bei einer doppelt verketteten dynamische Liste hat darüber hinaus jeder Knoten auch noch einen Zeiger auf das Vorgängerelement.

Datenstrukturen dürfen nicht mit Abstrakten Datentypen (ADTs) verwechselt werden. Bei einem Stack (einem ADT) werden zum Beispiel überhaupt keine Angaben gemacht, aus welchen Datentypen oder Datenstrukturen er zusammengesetzt ist oder wie er genau implementiert wird. Er wird lediglich über die Operationen definiert, die mit ihm möglich sein sollen.