Datenstrukturen

Datenstrukturen sind organisatorische Konzepte, mit denen Daten so gespeichert und zugänglich gemacht werden, dass bestimmte Operationen effizient möglich sind. Sie bilden die Grundlage vieler Algorithmen, weil sie den Zugriff, das Einfügen, Löschen und die Suche strukturieren. Typischerweise werden sie als abstrakte Datentypen beschrieben, deren Verhalten durch definierte Schnittstellen bestimmt ist, während konkrete Implementierungen das Speicherlayout festlegen. Die Wahl einer Datenstruktur beeinflusst Zeit- und Speicheraufwand von Abläufen, Cache-Verhalten und Skalierbarkeit.

Zu den grundlegenden linearen Strukturen gehören Arrays, verknüfte Listen, Stacks und Warteschlangen. Arrays ermöglichen direkten Zugriff per Index, haben aber feste Größe. Verknüfte Listen erlauben schnelles Einfügen und Löschen an beliebigen Stellen, leiden aber unter schlechterer Speicherlokalität. Stacks verwenden LIFO, Warteschlangen verwenden FIFO. In vielen Anwendungen werden diese Strukturen hinter Schnittstellen wie Push/Pop oder Enqueue/Dequeue verwendet.

Nicht-lineare Strukturen umfassen Bäume, Graphen und assoziative Container. Bäume ordnen Daten hierarchisch; balancierte Bäume ermöglichen logaritmische Suchen und Einfügungen. Graphen modellieren Beziehungen zwischen Elementen und helfen beim Finden von Pfaden. Hash-Tabellen liefern typischerweise einen nahezu konstanten Zugriff auf Schlüssel-Wert-Paare, abhängig von Kollisionen. Mengen (Sets) und Karten (Maps) speichern eindeutige Elemente bzw. Zuordnungen. Heaps dienen als Prioritätswarteschlangen; sie ermöglichen schnelle Zugriff auf das größte oder kleinste Element. Die Komplexität der Grundoperationen variiert je nach Struktur und Implementierung, typischerweise O(1) bis O(log n).

Bei der Wahl einer Datenstruktur spielen Zugriffsmuster, Speicherbedarf, Dynamik, Gleichzeitigkeit und Hardware eine Rolle. Viele Programmiersprachen liefern leistungsstarke Standardstrukturen, während spezialisierte Anwendungen maßgeschneiderte Lösungen benötigen. Grundwissen über Vor- und Nachteile unterstützt die effiziente Umsetzung von Algorithmen und Systemen.