Arrays
Ein Array ist die einfachste Datenstruktur: aufeinanderfolgende Speicherzellen mit fixem Zugriff per Index.
Komplexität
| Operation | Big-O | Warum |
|---|---|---|
| Zugriff per Index | O(1) | Direkte Speicheradresse |
| Suchen | O(n) | Linear durchgehen |
| Suche bei sortiert (Binary Search) | O(log n) | Halbieren |
| Einfügen am Ende (push) | O(1) amortisiert | Bei Vergrößerung: kopieren |
| Einfügen am Anfang | O(n) | Alles eine Stelle nach hinten |
| Löschen in Mitte | O(n) | Lücke füllen |
Statisch vs. Dynamisch
- Statisches Array: feste Größe, in C/Java/Rust üblich. Sehr schnell.
- Dynamisches Array: wächst automatisch. JS Array, Python list, C++ vector. Bei Vergrößerung: doppelte Größe allokieren, kopieren.
Beispiele
// JavaScript const arr = [1, 2, 3]; arr.push(4); // O(1) amortisiert arr[0]; // O(1) arr.indexOf(3); // O(n) arr.unshift(0); // O(n) — alle nach rechts arr.splice(1, 1); // O(n) — Lücke füllen
Wann Array?
- Reihenfolge wichtig
- Häufig per Index zugreifen
- Selten in Mitte einfügen/löschen
- Cache-Lokalität wichtig (CPU-Caches lieben Arrays)
Zurück zu Informatik