Niz je neprekinjena blok pomnilnika, ki drži elemente istega tipa, indeksirane od 0. Ker so elementi nameščeni drug ob drugem, je naslov elementa i izračunan neposredno kot base + i * elementSize, kar daje O(1) naključni dostop.
Postavitev pomnilnika
text
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
Primer
python
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
Zahtevnost
| Operacija | Čas |
|---|---|
| Dostop po indeksu | O(1) |
| Iskanje (neurejeno) | O(n) |
| Dodajanje (dinamično) | O(1) amortiziran |
| Vstavljanje/brisanje na začetku/sredi | O(n) |
Kompromisi
- Prednosti: hiter dostop, ugoden za cache (podatki so neprekinjeni), nizka režija pomnilnika.
- Slabosti: vstavljanje/brisanje v sredini je O(n); nizi s fiksno velikostjo zahtevajo kopiranje za rast.
Zakaj je to pomembno
Nizi so temelj za večino drugih struktur — nizi znakov,Hash tabele, kopici in dinamični seznami se vsi gradijo na njih.
Njihova lokalizacija v cache-u pogosto pusti, da "počasnejši" Big-O niz premaga "hitrejšo" strukturo na osnovi kazalcev v resničnih benchmark-ih.