Nizovi vs povezane liste
Nizovi su najčešće korišćena struktura podataka za skladištenje kolekcije elemenata. Većina programskih jezika pruža metode za jednostavno deklarisanje nizova i pristup elementima u nizovima. Povezana lista, tačnije jednostruko povezana lista, je takođe struktura podataka koja se može koristiti za skladištenje kolekcije elemenata. Sastoji se od niza čvorova i svaki čvor ima referencu na sljedeći čvor u nizu.
Prikazan na slici 1, je dio koda koji se obično koristi za deklariranje i dodjelu vrijednosti nizu. Slika 2 prikazuje kako bi niz izgledao u memoriji.
Iznad 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 se cijeli niz dodjeljuje kao jedan blok memorije i svaki element dobiva svoj prostor u nizu. Jednom kada je niz definiran, njegova veličina je fiksna. Dakle, ako niste sigurni u veličinu niza u vrijeme kompajliranja, morali biste definirati dovoljno veliki niz da bude na sigurnoj strani. Ali, većinu vremena zapravo ćemo koristiti manji broj elemenata nego što smo dodijelili. Dakle, značajna količina memorije je zapravo izgubljena. S druge strane, ako "dovoljno veliki niz" nije dovoljno velik, program bi se srušio.
Povezana lista dodeljuje memoriju svojim elementima odvojeno u svom bloku memorije i ukupna struktura se dobija povezivanjem ovih elemenata kao karika u lancu. Svaki element u povezanoj listi 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 povezane liste je pohranjen kao glava povezane liste.
| podaci | sljedeća |
Slika 3: Element povezane liste
Slika 4 prikazuje povezanu listu sa tri elementa. Svaki element pohranjuje svoje podatke, a svi elementi osim posljednjeg pohranjuju referencu na sljedeći element. Zadnji element sadrži nultu vrijednost u svom sljedećem polju. Bilo kojem elementu na listi može se pristupiti tako što ćete početi od glave i pratiti sljedeći pokazivač dok ne ispunite traženi element.
Iako su nizovi i povezane liste slični u smislu da se oba koriste za pohranjivanje kolekcije elemenata, nastaju razlike zbog strategija koje koriste da dodijele memoriju njenim elementima. Nizovi dodeljuju memoriju svim svojim elementima kao jedan blok i veličina niza se mora odrediti tokom vremena izvođenja. Ovo bi učinilo nizove neefikasnim u situacijama kada ne znate veličinu niza u vrijeme kompajliranja. Budući da povezana lista izdvaja memoriju za svoje elemente odvojeno, bila bi vrlo efikasna u situacijama u kojima ne znate veličinu liste u vrijeme kompajliranja. Deklaracija i pristup elementima u povezanoj listi ne bi bili jednostavni u poređenju sa načinom na koji direktno pristupate elementima u nizu koristeći njegove indekse.
