Popis pojedinačno povezanih ili Popis dvostruko povezanih
Povezani popis linearna je struktura podataka koja se koristi za pohranu zbirke podataka. Povezani popis dodijeljuje memoriju svojim elementima odvojeno u vlastitom bloku memorije, a ukupna struktura dobiva se povezivanjem tih elemenata kao karika u lancu. Pojedinačno povezani popis sastoji se od niza čvorova i svaki čvor ima referencu na sljedeći čvor u nizu. Dvostruko povezan popis sadrži niz čvorova u kojima svaki čvor sadrži referencu na sljedeći čvor kao i na prethodni čvor.
Popis pojedinačno povezanih
Svaki element na pojedinačno povezanom popisu 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 povezanog popisa sprema se kao zaglavlje povezanog popisa.
Na slici 2 prikazan je pojedinačno povezan 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.
Popis dvostruko povezanih
Svaki element na dvostruko povezanom popisu ima tri polja kao što je prikazano na slici 3. Slično kao pojedinačno povezani popis, podatkovno polje sadrži stvarne pohranjene podatke, a sljedeće polje upućuje na sljedeći element u lancu. Uz to, prethodno polje sadrži referencu na prethodni element u lancu. Prvi element povezanog popisa sprema se kao zaglavlje povezanog popisa.
Slika 4 prikazuje dvostruko povezan popis s tri elementa. Svi posrednički elementi pohranjuju reference na prvi i prethodni element. Posljednji element na popisu sadrži null vrijednost u sljedećem polju, a prvi element na popisu null vrijednost u svom prethodnom polju. Dvostruko povezani popis može se prelaziti prema naprijed slijedeći slijedeće reference u svakom elementu, a slično se može i unatrag pomoću prethodnih referenci u svakom elementu.
Koja je razlika između pojedinačno povezanog popisa i dvostruko povezanog popisa?
Svaki element na pojedinačno povezanom popisu sadrži referencu na sljedeći element na popisu, dok svaki element na 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 poput umetanja i brisanja složenije su jer se moraju nositi s dvije reference. Ali popisi s dvostrukim vezama omogućuju lakšu manipulaciju jer omogućuju kretanje po popisu u smjeru naprijed i natrag.
