Ein Array ist ein zusammenhängender Speicherblock, der Elemente desselben Typs enthält, indiziert von 0. Da Elemente nebeneinander liegen, wird die Adresse von Element i direkt als base + i * elementSize berechnet, was O(1) Direktzugriff ergibt.
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Operation | Zeit |
|---|---|
| Zugriff nach Index | O(1) |
| Suche (unsortiert) | O(n) |
| Anfügen (dynamisch) | O(1) amortisiert |
| Einfügen/Löschen am Anfang/in der Mitte | O(n) |
Arrays sind das Fundament unter den meisten anderen Strukturen — Strings, Hash-Tabellen, Heaps und dynamische Listen bauen alle darauf auf.
Ihre Cache-Lokalität führt oft dazu, dass ein "langsameres" Big-O Array eine "schnellere" Pointer-basierte Struktur in echten Benchmarks schlägt.