Nizovi vs povezani popisi
Nizovi su najčešće korištena podatkovna struktura za pohranu zbirke elemenata. Većina programskih jezika nudi metode za jednostavno deklariranje nizova i pristup elementima u nizovima. Povezana lista, točnije jednostruko povezana lista, također je podatkovna struktura koja se može koristiti za pohranu zbirke elemenata. Sastoji se od niza čvorova i svaki čvor ima referencu na sljedeći čvor u nizu.
Prikazano na slici 1 je dio koda koji se obično koristi za deklariranje i dodjeljivanje vrijednosti nizu. Slika 2 prikazuje kako bi niz izgledao u memoriji.
Gornji kod definira niz koji može pohraniti 5 cijelih brojeva i njima se pristupa pomoću indeksa od 0 do 4. Jedno važno svojstvo niza je da je cijeli niz dodijeljen kao jedan blok memorije i svaki element dobiva svoj vlastiti prostor u nizu. Nakon što je niz definiran, njegova veličina je fiksna. Dakle, ako niste sigurni u veličinu polja u vrijeme kompajliranja, morali biste definirati dovoljno veliko polje da biste bili sigurni. No, većinu vremena zapravo ćemo koristiti manji broj elemenata nego što smo dodijelili. Dakle, znatna količina memorije je zapravo izgubljena. S druge strane, ako "dovoljno velik niz" zapravo nije dovoljno velik, program bi se srušio.
Povezani popis dodjeljuje memoriju svojim elementima zasebno u vlastitom bloku memorije, a cjelokupna struktura se dobiva povezivanjem tih elemenata kao karika u lancu. Svaki element na povezanom popisu ima dva polja kao što je prikazano na slici 3. Podatkovno polje sadrži stvarne pohranjene podatke, a sljedeće polje sadrži referencu na sljedeći element u lancu. Prvi element povezane liste pohranjuje se kao glava povezane liste.
| podaci | sljedeća |
Slika 3: Element povezanog popisa
Slika 4 prikazuje povezani popis s tri elementa. Svaki element pohranjuje svoje podatke i svi elementi osim posljednjeg pohranjuju referencu na sljedeći element. Posljednji element ima nultu vrijednost u sljedećem polju. Bilo kojem elementu na popisu može se pristupiti tako da počnete od glave i pratite sljedeći pokazivač dok ne naiđete na traženi element.
Iako su nizovi i povezani popisi slični u smislu da se oboje koriste za pohranu zbirke elemenata, stvaraju razlike zbog strategija koje koriste za dodjelu memorije svojim elementima. Nizovi dodjeljuju memoriju svim svojim elementima kao jednom bloku, a veličina niza mora se odrediti tijekom izvođenja. To bi nizove učinilo neučinkovitima u situacijama u kojima ne znate veličinu niza u vrijeme kompajliranja. Budući da povezani popis zasebno dodjeljuje memoriju svojim elementima, bio bi vrlo učinkovit u situacijama u kojima ne znate veličinu popisa u vrijeme kompajliranja. Deklaracija i pristup elementima u povezanom popisu ne bi bili jednostavni u usporedbi s načinom na koji izravno pristupate elementima u nizu pomoću njegovih indeksa.
