Et array er en sammenhængende blok hukommelse, der indeholder elementer af samme type, indekseret fra 0. Fordi elementer ligger ved siden af hinanden, beregnes adressen på element i direkte som base + i * elementSize, hvilket giver O(1) tilfældig adgang.
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 | Tid |
|---|---|
| Adgang efter indeks | O(1) |
| Søgning (usorteret) | O(n) |
| Tilføj (dynamisk) | O(1) amortiseret |
| Indsæt/slet i front/midte | O(n) |
Arrays er fundamentet under de fleste andre strukturer — strenge, hash-tabeller, heaps og dynamiske lister bygger alle på dem.
Deres cache-lokalitet gør ofte, at et "langsommere" Big-O array slår en "hurtigere" pointer-baseret struktur i rigtige benchmarks.