En array er en sammenhengende blokk med minne som inneholder elementer av samme type, indeksert fra 0. Fordi elementene ligger ved siden av hverandre, beregnes adressen til element i direkte som base + i * elementSize, noe som gir O(1) tilfeldig tilgang.
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
| Operasjon | Tid |
|---|---|
| Tilgang ved indeks | O(1) |
| Søk (usortert) | O(n) |
| Tilføy (dynamisk) | O(1) amortisert |
| Sett inn/slett i front/midten | O(n) |
Arrayer er grunnlaget under de fleste andre strukturer — strenger, hash-tabeller, heaper og dynamiske lister bygger alle på dem.
Deres cache-lokalitet gjør ofte at en "tregere" Big-O array slår en "raskere" pointer-basert struktur i virkelige benchmarks.