Oboje pohrane niz, ali imaju suprotne profile troškova. Niz je kontinuirana memorija s O(1) indeksiranjem; povezana lista je raspršenih čvorova spojenih pokazivačima, s O(1) umetanjem/brisanjem na krajevima ali bez indeksiranja.
Oboje pohrane niz, ali imaju suprotne profile troškova. Niz je kontinuirana memorija s O(1) indeksiranjem; povezana lista je raspršenih čvorova spojenih pokazivačima, s O(1) umetanjem/brisanjem na krajevima ali bez indeksiranja.
| Operacija | Niz (dinamički) | Povezana lista |
|---|
| Pristup po indeksu | O(1) | O(n) |
| Pretraga | O(n) | O(n) |
| Umetanje/brisanje na početku | O(n) | O(1) |
| Umetanje/brisanje na kraju | O(1) amortiziran | O(1) s pokazivačem na kraj |
| Umetanje/brisanje u sredini | O(n) | O(n) pretraga + O(1) spajanje |
| Memorijska režija | niska | visoka (pokazivač po čvoru) |
| Lokalnost cache-a | odličan | loša |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
U praksi nizovi pobjeđuju većinu vremena jer lokalnost cache-a premašuje Big-O razlike za tipične veličine.
Znajući oboje možete opravdati svoj izbor na razgovorima umjesto da slijepo zadanu vrijednost — i objasniti zašto "O(1) umetanje" rijetko pobjeđuje kontinuirani niz.