Un array este un bloc contiguu de memorie care conține elemente de același tip, indexate de la 0. Deoarece elementele sunt plasate alături unele de altele, adresa elementului i este calculată direct ca base + i * elementSize, oferind O(1) acces aleatoriu.
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
| Operație | Timp |
|---|---|
| Acces după index | O(1) |
| Căutare (nesortate) | O(n) |
| Adăugare (dinamică) | O(1) amortizat |
| Inserare/ștergere la început/mijloc | O(n) |
Array-urile sunt fundamentul sub majoritatea celorlalte structuri — șiruri de caractere, tabele hash, heap-uri și liste dinamice se construiesc pe ele.
Localitatea cache-ului lor face adesea ca un array cu Big-O mai „lent