Implementacije skupova pomocu nizova ce u opstem slucaju
pokazati nesto bolje performanse nego implementacije pomocu povezanih listi.
Razlika je, naravno, samo u konstantnom faktoru:
pretrazivanje i niza i povezane liste je u osnovi O(n) operacija.
Ipak, veliki broj faktora utice na neznatno bolje performanse nizova:
Adresa sledeceg elementa u nizu se moze izracunati iz trenutne adrese
i velicine elementa - oba podatka se cuvaju u registrima:
(sledeca)adresa := (trenutna)adresa + velicina
Obe adrese cak mogu da koriste isti registar.
Posto nije neophodan pristup memoriji,
ova se operacija odvija u jednom taktu modernih RISC procesora.
Koristeci nizove, informacije se cuvaju u uzastopnim lokacijama u memoriji:
ovo omogucava da se efikasno iskoriste kes sistemi modernih procesora.
Deo kes memorije koji je "dobavljen" pristupom trenutnom elementu niza
takodje sadrzi deo sledeceg elementa niza.
Stoga nema neiskoriscenosti kesa ili moguce sirine opsega CPU<->memorija.
Za razliku, kod implementacije pomocu povezanih listi:
Imamo dodatnu potrosnju memoriju za pointere
(i potrosnju prouzrokovanu upotrebom alokatora memorije
kao sto je malloc).
Ovo znaci da manje elemenata moze da se dobavi u kes
prilikom pristupa elementu skupa.
Ne postoji garancija da ce susedni elementi u listi
zauzimati susedne lokacije u memoriji. Ovo vodi do tracenja
sirine memorijskog opsega, jer elementi dobavljeni u kes
ne moraju biti upotrebljeni.