Dynamische Datenstrukturen
Dynamische Datenstrukturen
- Beispiele für dynamische Datenstrukturen:
- Liste
- Baum
- Graph
- …
- Eigenschaften
- Erweiterbar
- Schnelles Einfügen
- Löschen möglich
dynamic Array
In a nutshell
Erweiterung des klassischen Arrays für effizientes Löschen / Einfügen am Ende.
- Unterscheidung zwischen capacity und legth
- capacity: Größe im Speicher
- length: Anzahl der tatsächlich verwendeten Elemente
- Einfügen und Löschen am Ende sind ≈ O(1).
- ABER: Einfügen und Löschen an einer beliebigen Stelle immer noch teuer.