Pole (array) je souvislý blok paměti obsahující prvky stejného typu, indexované od 0. Protože prvky sousedí vedle sebe, adresa prvku i se počítá přímo jako base + i * elementSize, což dává O(1) náhodný přístup.
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
| Operace | Čas |
|---|---|
| Přístup podle indexu | O(1) |
| Hledání (nesetřízené) | O(n) |
| Připojení (dynamické) | O(1) amortizovaně |
| Vložení/odstranění na začátku/uprostřed | O(n) |
Pola jsou základem pod většinou ostatních struktur — řetězce, hash tabulky, haldy a dynamické seznamy jsou na nich všechny postaveny.
Ich cache lokalita často způsobí, že "pomalejší" Big-O pole porazí "rychlejší" strukturu založenou na ukazatelích v reálných testech.