Eine Datenstruktur in der Informatik ist eine Möglichkeit, Daten
in einem Computer zu speichern
, damit sie effizient genutzt werden können. Es ist eine Organisation
mathematischer und logischer Datenkonzepte. Oftmals ermöglicht eine sorgfältig ausgewählte
Datenstruktur die Verwendung des
effizientesten Algorithmus
. Die Wahl der Datenstruktur beginnt oft mit der
Wahl eines abstrakten Datentyps. Eine gut durchdachte Datenstruktur ermöglicht die
Durchführung
einer Vielzahl kritischer Operationen unter Verwendung von so wenig
Ressourcen wie Ausführungszeit und Speicherplatz wie möglich. Datenstrukturen
werden von einer
Programmiersprache als Datentypen und die
Referenzen implementiert
und Operationen, die sie anbieten.
Verschiedene Arten von Datenstrukturen sind für verschiedene Arten von
Anwendungen geeignet
und einige sind auf bestimmte Aufgaben hoch spezialisiert. Zum
Beispiel
B-Bäume sind besonders gut geeignet für die Implementierung von Datenbanken, während Netzwerke von Maschinen auf Routing - Tabellen Funktion verlassen.
Beim Entwurf vieler Arten von Computerprogrammen ist die Wahl der Datenstrukturen
eine primäre Entwurfsüberlegung. Die Erfahrung beim Aufbau
großer Systeme hat gezeigt, dass die Schwierigkeit der Implementierung sowie die
Qualität und Leistung des Endergebnisses stark von der Wahl
der besten Datenstruktur abhängen
. Nachdem die Datenstrukturen ausgewählt wurden,
zu verwendende Algorithmen werden oft relativ offensichtlich. Manchmal
funktionieren die Dinge
in die entgegengesetzte Richtung – Datenstrukturen werden gewählt, weil
bestimmte Schlüsselaufgaben Algorithmen haben, die mit bestimmten Datenstrukturen am besten funktionieren
. In jedem Fall ist die Wahl geeigneter Datenstrukturen
entscheidend.
Diese Erkenntnis hat zu vielen formalisierten Entwurfsmethoden und
Programmiersprachen geführt, in denen Datenstrukturen und nicht Algorithmen
der entscheidende Organisationsfaktor sind. Die meisten Sprachen verfügen über eine Art
Modulsystem, das die sichere Wiederverwendung
von Datenstrukturen in
verschiedenen Anwendungen ermöglicht, indem ihre überprüften Implementierungsdetails
hinter kontrollierten Schnittstellen versteckt
werden.
Insbesondere
objektorientierte Programmiersprachen wie C++ und
Java verwenden hierfür
Klassen .
Da Datenstrukturen so wichtig sind, sind viele von ihnen in Standardbibliotheken moderner Programmiersprachen und
APIs enthalten , wie beispielsweise die
Container von C++
, das
Java Collections Framework und das Microsoft
.NET Framework .
Die grundlegenden Bausteine der meisten Datenstrukturen sind Arrays,
Datensätze ,
diskriminierte Vereinigungen und
Referenzen .
Beispielsweise ist die Nullable-Referenz, eine Referenz, die Null sein kann,
eine Kombination aus Referenzen und diskriminierten Vereinigungen, und die einfachste
verknüpfte Datenstruktur, die Linked List, wird aus Datensätzen und
Nullable-Referenzen aufgebaut.
Datenstrukturen stellen Implementierungen oder
Schnittstellen dar :
Eine Datenstruktur kann als Schnittstelle zwischen zwei Funktionen oder
als Implementierung von Methoden zum Zugriff auf Speicher betrachtet werden, der
nach dem zugehörigen Datentyp
organisiert ist