Warum sollte man Lineare Listen (arrays) als Datenstruktur verwenden?
Lineare Listen haben erstmal sehr viele Nachteile...
- Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)
- Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionieren
- Sortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat.
- Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.
Dagegen sind Bäume:
- Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss)
- Suche funktioniert aufbaubedingt IMMER in O(log(n))
- Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortieren
- Die Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).
Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?