Jednostruko povezani popis u odnosu na dvostruko povezani popis
Povezani popis je linearna struktura podataka koja se koristi za pohranu zbirke podataka. Povezani popis dodjeljuje memoriju svojim elementima zasebno u vlastitom bloku memorije, a cjelokupna struktura se dobiva povezivanjem tih elemenata kao karika u lancu. Jednostruko povezana lista sastoji se 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 povezani popis
Svaki element u pojedinačno povezanom popisu ima dva polja kao što je prikazano na slici 1. 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.
Slika 2 prikazuje pojedinačno povezanu listu 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 krenete od glave i pratite sljedeći pokazivač dok ne naiđete na traženi element.
Dvostruko povezani popis
Svaki element u dvostruko povezanoj listi ima tri polja kao što je prikazano na slici 3. Slično pojedinačno povezanom popisu, podatkovno polje sadrži stvarne pohranjene podatke, a sljedeće polje sadrži referencu na sljedeći element u lancu. Osim toga, prethodno polje sadrži referencu na prethodni element u lancu. Prvi element povezane liste pohranjuje se kao glava povezane liste.
Slika 4 prikazuje dvostruko povezanu listu s tri elementa. Svi međuelementi pohranjuju reference na prvi i prethodni element. Posljednji element na popisu ima nultu vrijednost u sljedećem polju, a prvi element na popisu ima nultu vrijednost u svom prethodnom polju. Dvostruko povezana lista može se kretati naprijed prateći sljedeće reference u svakom elementu i na sličan način može se kretati unatrag koristeći prethodne reference u svakom elementu.
Koja je razlika između jednostruko povezanog popisa i dvostruko povezanog popisa?
Svaki element u jednostruko povezanom popisu sadrži referencu na sljedeći element na popisu, dok svaki element u dvostruko povezanom popisu sadrži reference na sljedeći element kao i na prethodni element na popisu. Dvostruko povezani popisi zahtijevaju više prostora za svaki element na popisu, a elementarne operacije kao što su umetanje i brisanje su složenije jer moraju raditi s dvije reference. Ali popisi s dvostrukom vezom omogućuju lakšu manipulaciju budući da dopuštaju kretanje popisom u smjeru naprijed i natrag.
