Eine Datenstruktur ist eine konkrete Art, Daten im Speicher eines Computers zu organisieren und miteinander zu verknüpfen, sodass bestimmte Operationen auf diesen Daten effizient ausgeführt werden können.
Daten allein reichen nicht aus – sie müssen auch sinnvoll angeordnet sein, damit ein Programm schnell auf sie zugreifen kann. Eine Datenstruktur legt genau diese Anordnung fest: Welche einzelnen Werte gehören zusammen, wie sind sie im Speicher angeordnet, und welche Operationen – etwa Hinzufügen, Entfernen oder Durchsuchen – sind darauf vorgesehen. Je nachdem, welche Operation am häufigsten gebraucht wird, eignet sich eine andere Datenstruktur besser.
Einfache Datenstrukturen wie das Array reihen Werte desselben Typs lückenlos hintereinander im Speicher auf, sodass jedes Element über seine Position direkt angesprochen werden kann. Andere Datenstrukturen wie die verkettete Liste speichern zusätzlich zu jedem Wert einen Verweis auf das nächste Element, wodurch sich Elemente leicht einfügen oder entfernen lassen, ohne die übrigen Werte im Speicher zu verschieben. Komplexere Datenstrukturen wie Bäume oder Hashtabellen bauen auf solchen Grundbausteinen auf und sind gezielt darauf ausgelegt, bestimmte Operationen wie das Suchen eines Werts besonders schnell zu machen. Welche Datenstruktur die richtige Wahl ist, hängt davon ab, welche Operationen ein Programm am häufigsten ausführt und wie groß die Datenmenge ist.
Eine Einkaufsliste lässt sich als Array speichern, wenn die Anzahl der Einträge von vornherein feststeht und selten geändert wird. Muss die Liste dagegen häufig um neue Einträge ergänzt oder einzelne Positionen gestrichen werden, ist eine verkettete Liste praktischer, da sich Einträge dort einfügen und entfernen lassen, ohne alle übrigen Positionen im Speicher zu verschieben.
Datenstrukturen werden eingesetzt, um Datenbanken intern zu organisieren, Suchvorgänge und Sortieralgorithmen zu beschleunigen, Programme speichereffizient zu gestalten und komplexe Objekte wie Dateisysteme oder Netzwerkgraphen abzubilden.
Es gibt keine Datenstruktur, die für jede Aufgabe gleich gut geeignet ist; eine Struktur, die das schnelle Einfügen begünstigt, ist oft beim Suchen langsamer, und umgekehrt. Die Wahl der Datenstruktur ist deshalb immer ein Kompromiss, der von der jeweiligen Anwendung abhängt. Häufig wird außerdem übersehen, dass eine Datenstruktur nur die Organisation der Daten beschreibt – wie ein Problem mit diesen Daten gelöst wird, regelt stattdessen ein Algorithmus.
Nicht zu verwechseln mit Datentyp: Ein Datentyp legt fest, welche Art von Wert eine einzelne Variable annehmen darf, während eine Datenstruktur beschreibt, wie mehrere solcher Werte zu einer größeren, durchsuchbaren oder veränderbaren Einheit zusammengesetzt werden. Ebenfalls abzugrenzen ist Algorithmus: Ein Algorithmus ist das Verfahren, das auf einer Datenstruktur arbeitet, etwa um sie zu durchsuchen oder zu sortieren – die Datenstruktur selbst liefert nur die Organisation, nicht das Lösungsverfahren.