Een array is een aaneengesloten geheugenblok dat elementen van hetzelfde type bevat, geïndexeerd vanaf 0. Omdat elementen naast elkaar liggen, wordt het adres van element i rechtstreeks berekend als base + i * elementSize, wat O(1) willekeurige toegang geeft.
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
| Bewerking | Tijd |
|---|---|
| Toegang op index | O(1) |
| Zoeken (ongesorteerd) | O(n) |
| Toevoegen (dynamisch) | O(1) geamortiseerd |
| Invoegen/verwijderen aan voorkant/midden | O(n) |
Arrays zijn de basis onder de meeste andere structuren — strings, hash tables, heaps en dynamische lijsten zijn er allemaal op gebaseerd.
Hun cache-lokaliteit maakt vaak dat een "langzamere" Big-O array een "snellere" pointer-gebaseerde structuur in echte benchmarks verslaat.