Informatik > Lexikon

Datenstrukturen

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 Liste beispielsweise besteht aus Knoten mit je einer Wert-Eigenschaft und einem Zeiger auf den nächsten Knoten, den sogenannten Nachfolger. Bei einer doppelt verketteten Liste hat darüber hinaus jeder Knoten auch noch einen Zeiger auf den Vorgänger. Bei einem Baum hat jeder Knoten zwei oder mehr Nachfolger.

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 definiert, die mit ihm möglich sein sollen.

Interne Links: