Pojedinačno povezana lista vs Dvostruko povezana lista
Povezana lista je linearna struktura podataka koja se koristi za pohranjivanje zbirke podataka. Povezana lista dodeljuje memoriju svojim elementima odvojeno u svom bloku memorije, a ukupna struktura se dobija povezivanjem ovih elemenata kao karika u lancu. Pojedinačno povezana lista je sastavljena od niza čvorova i svaki čvor ima referencu na sljedeći čvor u nizu. Dvostruko povezana lista sadrži niz čvorova u kojima svaki čvor sadrži referencu na sljedeći čvor kao i na prethodni čvor.
Pojedinačno povezana lista
Svaki element u jednostruko povezanoj listi ima dva polja kao što je prikazano na slici 1. 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.
Slika 2 prikazuje jednostruko 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.
Dvostruko povezana lista
Svaki element u dvostruko povezanoj listi ima tri polja kao što je prikazano na slici 3. Slično kao jednostruko povezana lista, polje podataka sadrži stvarne pohranjene podatke, a sljedeće polje sadrži referencu na sljedeći element u lancu. Dodatno, prethodno polje sadrži referencu na prethodni element u lancu. Prvi element povezane liste je pohranjen kao glava povezane liste.
Slika 4 prikazuje dvostruko povezanu listu sa tri elementa. Svi međuelementi pohranjuju reference na prvi i prethodni element. Poslednji element na listi drži nultu vrednost u svom sledećem polju, a prvi element na listi drži nultu vrednost u svom prethodnom polju. Dvostruko povezana lista može se prijeći naprijed slijedeći sljedeće reference u svakom elementu i slično se može prijeći unazad koristeći prethodne reference u svakom elementu.
Koja je razlika između jednostruko povezane i dvostruko povezane liste?
Svaki element u jednostruko povezanoj listi sadrži referencu na sljedeći element u listi, dok svaki element u dvostruko povezanoj listi sadrži reference na sljedeći element kao i prethodni element u listi. Dvostruko povezane liste zahtijevaju više prostora za svaki element u listi, a elementarne operacije kao što su umetanje i brisanje su složenije jer se moraju nositi s dvije reference. Ali liste sa dvostrukim vezama omogućavaju lakšu manipulaciju jer omogućavaju kretanje kroz listu u smjeru naprijed i nazad.
