Oba shranjujeta zaporedja, vendar imajo nasprotne profilne stroške. Polje je neprekinjena pomnilniška območja s O(1) indeksiranjem; povezan seznam je razpršeni vozlišča, povezana s kazalci, s O(1) vstavljanjem/brisanjem na koncih, vendar brez indeksiranja.
| Operacija | Polje (dinamično) | Povezan seznam |
|---|
| Dostop po indeksu | O(1) | O(n) |
| Iskanje | O(n) | O(n) |
| Vstavljanje/brisanje na začetku | O(n) | O(1) |
| Vstavljanje/brisanje na koncu | O(1) amortiziran | O(1) s kazalcem na konec |
| Vstavljanje/brisanje v sredini | O(n) | O(n) iskanje + O(1) spojenje |
| Pomnilniška zalihost | nizka | visoka (kazalec na vozlišče) |
| Lokalnost predpomnilnika | odličnanavbez | slaba |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
V praksi polja zmagajo večino časa, ker lokalnost predpomnilnika presega razlike Big-O za tipične velikosti.
Znanje obojega vam omogoči, da v intervjujih utemeljite svojo izbiro namesto da slepо privzamete privzeto možnost — in razložite zakaj "O(1) vstavljanje" redko premaga neprekinjeno polje.
Knjižnica IT vprašanj za razgovore s podrobnimi odgovori — od začetnika do izkušenega.
Doniraj