Az array (tömb) a memória egy szomszédos blokkja, amely ugyanolyan típusú elemeket tartalmaz, a 0-tól kezdve indexelve. Mivel az elemek egymás mellett helyezkednek el, az i elem címe közvetlenül base + i * elementSize-ként számítható ki, így O(1) időben lehet tetszőleges elemhez hozzáférni.
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
| Művelet | Idő |
|---|---|
| Hozzáférés index alapján | O(1) |
| Keresés (rendezetlen) | O(n) |
| Hozzáfűzés (dinamikus) | O(1) amortizált |
| Beszúrás/törlés az elején/közepén | O(n) |
A tömbök a legtöbb más adatstruktúra alapja — a stringek, hash táblázatok, kupacok és dinamikus listák mind ezekre épülnek.
A cache lokalitásuk miatt gyakran az egy "lassabb" Big-O tömbje jobban teljesít, mint egy "gyorsabb" mutatóalapú struktúra a valós teljesítménytesztekben.