Nizovi vs povezani popisi
Nizovi su najčešće korištena struktura podataka za pohranu zbirke elemenata. Većina programskih jezika pruža metode za lako deklariranje nizova i pristup elementima u nizovima. Povezani popis, točnije pojedinačno povezani popis, također je struktura podataka 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.
Na slici 1 prikazan je dio koda koji se obično koristi za deklariranje i dodjeljivanje vrijednosti nizu. Slika 2 prikazuje kako bi niz izgledao u memoriji.
Iznad koda definira niz koji može pohraniti 5 cijelih brojeva i njima se pristupa pomoću indeksa 0 do 4. Jedno važno svojstvo niza je da je čitav niz dodijeljen kao jedan blok memorije i svaki element dobiva svoj prostor u polju. Jednom kada je niz definiran, njegova je veličina fiksna. Dakle, ako niste sigurni u veličinu niza u vrijeme sastavljanja, morali biste definirati dovoljno velik niz da bude na sigurnoj strani. Ali, 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 dodijeljuje memoriju svojim elementima odvojeno u vlastitom bloku memorije, a ukupna struktura dobiva se povezivanjem tih elemenata kao karika u lancu. Svaki element na povezanom popisu ima dva polja kao što je prikazano na slici 3. Polje podataka sadrži stvarne pohranjene podatke, a sljedeće polje sadrži referencu na sljedeći element u lancu. Prvi element povezanog popisa sprema se kao zaglavlje povezanog popisa.
Slika 3: Element povezanog popisa
Slika 4 prikazuje povezani popis s tri elementa. Svaki element pohranjuje svoje podatke, a svi elementi osim zadnjeg pohranjuju referencu na sljedeći element. Posljednji element sadrži null vrijednost u svom sljedećem polju. Bilo kojem elementu s popisa može se pristupiti tako da se krene od glave i slijedi sljedeći pokazivač dok ne ispunite traženi element.
Iako su nizovi i povezani popisi slični u smislu da se obojica koriste za pohranu zbirke elemenata, oni imaju razlike zbog strategija koje koriste za dodjelu memorije svojim elementima. Nizovi dodjeljuju memoriju svim svojim elementima kao jedan blok, a veličina polja mora se odrediti za vrijeme izvođenja. To bi učinilo nizove neučinkovitima u situacijama kada ne znate veličinu niza u vrijeme sastavljanja. Budući da povezani popis memoriju zasebno dodjeljuje svojim elementima, to bi bilo mnogo učinkovitije u situacijama u kojima ne znate veličinu popisa u vrijeme sastavljanja. Izjava i pristup elementima na povezanom popisu ne bi bili izravni u usporedbi s onim kako izravno pristupate elementima u nizu koristeći njegove indekse.
