Array huwa blokk ta' memorja contiguwa li għandu elementi tal-istess tip, indiċjati mill-0. Minħabba li l-elementi jiffurmaw waħda ħdejn l-oħra, l-indirizz tal-element i huwa kkalkulat direttament bħala base + i * elementSize, li jagħti aċċess random O(1).
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
| Operazzjoni | Ħin |
|---|---|
| Aċċess b'indiċi | O(1) |
| Tfittxija (mhux sortjat) | O(n) |
| Append (dinamiku) | O(1) amortizzat |
| Insert/delete fil-frott/nofs | O(n) |
Arrays huma l-funzjoni taħt ħafna strutturi oħra — strings, hash tables, heaps, u dynamic lists kollha jbnu fuqhom.
Il-cache locality tagħhom spiss tagħmel li array "aktar bil-mod" Big-O juqbez struttura "aktar mgħaggel" bbażata fuq pointers f'benchmarks reali.