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 Listen, Binärbäume etc.
Bei einer Datenstruktur wird mehr oder weniger genau angegeben, wie sie zu implementieren ist, allerdings kann diese Angabe recht allgemein gehalten sein, unabhängig von einer konkreten Programmiersprache. Beispielsweise so:
Datenstruktur Liste, doppelt verknüpft
Die Liste besteht aus einer endlichen Anzahl von Knoten.
Jeder Knoten besteht aus einer Komponente, die die eigentliche Information speichert, einem Zeiger auf den vorhergehenden Knoten (falls dieser existiert) und einem Zeiger auf den nachfolgenden Knoten (falls dieser existiert). Außerdem existieren zwei Zeiger, die auf den ersten und den letzten Knoten der Liste zeigen.
Bei Datenstrukturen unterscheidet man noch zwischen statischen und dynamischen Datenstrukturen. Ein Beispiel für eine statische Datenstruktur ist der Array, bei dem die Zahl der Elemente bereits bei der Implementierung festgelegt wird. Diese Datenstruktur ist statisch, weil die Zahl der Elemente während der Laufzeit des Programms nicht mehr verändert werden kann.
Bei einer dynamischen Datenstruktur ist dies dagegen möglich. Eine dynamische Datenstruktur kann während der Laufzeit des Programms die Zahl der Elemente verändern und sich so an die jeweils aktuellen Bedürfnisse anpassen.
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 init(), push(), pop(), top() und empty() definiert, die mit ihm möglich sein sollen.
Implementiert werden kann ein solcher Stack dann mit der Datenstruktur Array, mit der Datenstruktur Liste oder mit irgendeiner anderen passenden Datenstruktur.