Konkrete Datenstrukturen
Aus ProgrammingWiki
Archivierte Version vom 2020-08-14T22:00:51+00:00. Aktuelle Version
Inhaltsverzeichnis |
Konkrete Datenstrukturen sind Implementierungen eines ADT. Zur Implementierung ein und desselben ADT kann es unterschiedliche konkrete Datentypen geben. Gleiche Operationen können für verschiedene konkrete Datenstrukturen sehr unterschiedliche Laufzeiten haben.
Array
Linked List
Dynamisches Array
Stack
Queue
Fazit
Abschließend stellen wir die Aufwände der einzelnen Operationen übersichtlich zusammen. Derartige Angaben bilden die wichtigste Grundlage für die Interpretation und Entscheidung für oder gegen einen bestimmten Datentyp in entsprechenden Softwareprojekten.
| Access | Search | Insert | Delete | |
|---|---|---|---|---|
| Array | \mathcal{O}(1) | \mathcal{O}(\log_2 n), wenn sortiert, sonst \mathcal{O}(n) | \mathcal{O}(1) | \mathcal{O}(n) |
| Singly linked list | \mathcal{O}(n) | \mathcal{O}(n) | \mathcal{O}(1), an vorgegebener Position | \mathcal{O}(n) |
| Doubly linked list | \mathcal{O}(n) | \mathcal{O}(n) | \mathcal{O}(1), an vorgegebener Position | \mathcal{O}(1) |
| Dynamisches Array | \mathcal{O}(1) | \mathcal{O}(\log_2 n), wenn sortiert, sonst \mathcal{O}(n) | \mathcal{O}(1), amortisiert, sonst \mathcal{O}(n) | \mathcal{O}(1), amortisiert, sonst \mathcal{O}(n) |
| Stack | \mathcal{O}(n) | \mathcal{O}(n) | \mathcal{O}(1) | \mathcal{O}(1) |
| Queue | \mathcal{O}(n) | \mathcal{O}(n) | \mathcal{O}(1) | \mathcal{O}(1) |