Niz je susjedan blok memorije koji sadrži elemente istog tipa, indeksirane od 0. Budući da se elementi nalaze jedan pored drugog, adresa elementa i se izračunava izravno kao base + i * elementSize, dajući pristup nasumičnim elementima u vremenu O(1).
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
| Operacija | Vrijeme |
|---|---|
| Pristup po indeksu | O(1) |
| Pretraga (neuređena) | O(n) |
| Dodavanje (dinamički) | O(1) amortizovano |
| Umetanje/brisanje na početku/sredini | O(n) |
Nizovi su temelj većine ostalih struktura — stringovi, hash tablice, heaps i dinamičke liste sve se grade na njima.
Njihova cache lokalnost često čini da "sporiji" Big-O niz pobijedi "brži" strukturi temeljenu na pokazivačima u stvarnim mjerenjima.
Knjižnica IT pitanja za razgovore za posao s detaljnim odgovorima — od Juniora do Seniora.
Doniraj