En array är ett sammanhängande minnesblock som innehåller element av samma typ, indexerade från 0. Eftersom elementen sitter bredvid varandra beräknas adressen för element i direkt som base + i * elementSize, vilket ger O(1) slumpmässig åtkomst.
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 |
|---|---|
| Åtkomst efter index | O(1) |
| Sökning (osorterad) | O(n) |
| Lägg till (dynamisk) | O(1) amorterad |
| Infoga/ta bort i början/mitten | O(n) |
Arrays är grunden under de flesta andra strukturer — strängar, hashtabeller, heaps och dynamiska listor bygger alla på dem.
Deras cache-lokalitet gör ofta att en "långsammare" Big-O array slår en "snabbare" pekarbaserad struktur i verkliga benchmarks.