Taulukko (array) on yhtenäinen muistilohko, joka sisältää saman tyyppisiä alkioita ja on indeksoitu nollasta (0). Koska alkiot sijaitsevat vierekkäin, alkion i osoite lasketaan suoraan kaavalla base + i * elementSize, mikä antaa O(1) satunnaisarvon käyttöoikeuden.
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
| Operaatio | Aika |
|---|---|
| Pääsy indeksillä | O(1) |
| Haku (järjestämätön) | O(n) |
| Liitä (dynaaminen) | O(1) amortisoiduksi |
| Lisää/poista alussa/keskellä | O(n) |
Taulukot ovat perustan useimmille muille rakenteille — merkkijonot, hajautustaulukot, kekot ja dynaamiset luettelot kaikki rakentuvat niihin.
Niiden välimuistin paikallisesti tekevät usein "hitaamman" Big-O -taulukon voittaa "nopeamman" osoitinpohjaisen rakenteen todellisissa vertailuissa.