Seznam posamično povezanih in dvojno povezanih seznamov
Povezani seznam je linearna podatkovna struktura, ki se uporablja za shranjevanje zbirke podatkov. Povezani seznam razdeli pomnilnik svojim elementom ločeno v svojem bloku pomnilnika in celotno strukturo dobimo s povezovanjem teh elementov kot povezav v verigi. Enovezen seznam je sestavljen iz zaporedja vozlišč in vsako vozlišče se sklicuje na naslednje vozlišče v zaporedju. Dvojno povezan seznam vsebuje zaporedje vozlišč, v katerem vsako vozlišče vsebuje sklic na naslednje vozlišče in na prejšnje vozlišče.
Enotno povezan seznam
Vsak element na posamezno povezanem seznamu ima dve polji, kot je prikazano na sliki 1. Podatkovno polje vsebuje dejansko shranjene podatke, naslednje polje pa sklic na naslednji element v verigi. Prvi element povezanega seznama je shranjen kot glava povezanega seznama.
Slika 2 prikazuje posamično povezan seznam s tremi elementi. Vsak element shrani svoje podatke, vsi elementi, razen zadnjega, pa sklic na naslednji element. Zadnji element ima v naslednjem polju vrednost nič. Do katerega koli elementa na seznamu je mogoče dostopati tako, da začnete z glave in sledite naslednjemu kazalcu, dokler ne izpolnite zahtevanega elementa.
Dvojno povezan seznam
Vsak element na dvojno povezanem seznamu ima tri polja, kot je prikazano na sliki 3. Podobno kot posamezno povezan seznam vsebuje tudi dejansko shranjene podatke, naslednje polje pa sklic na naslednji element v verigi. Poleg tega prejšnje polje vsebuje sklic na prejšnji element v verigi. Prvi element povezanega seznama je shranjen kot glava povezanega seznama.
Slika 4 prikazuje dvojno povezan seznam s tremi elementi. Vsi vmesni elementi hranijo sklice na prvi in prejšnji element. Zadnji element na seznamu ima v naslednjem polju vrednost nič, prvi element na seznamu pa vrednost null v prejšnjem polju. Dvojno povezanega seznama je mogoče premakniti naprej, tako da sledite naslednjim referencam v vsakem elementu, podobno pa nazaj po prejšnjih referencah v vsakem elementu.
Kakšna je razlika med enojno povezanim seznamom in dvojno povezanim seznamom?
Vsak element na posamezno povezanem seznamu vsebuje sklic na naslednji element na seznamu, medtem ko vsak element na dvojno povezanem seznamu vsebuje sklice na naslednji element in prejšnji element na seznamu. Dvojno povezani seznami zahtevajo več prostora za vsak element na seznamu, elementarne operacije, kot sta vstavljanje in brisanje, pa so bolj zapletene, saj morajo obravnavati dve sklici. Toda seznami z dvojnimi povezavami omogočajo lažjo manipulacijo, saj omogočajo premikanje po seznamu v smeri naprej in nazaj.
