Enojno povezan seznam v primerjavi z dvojno povezanim seznamom
Povezan seznam je linearna podatkovna struktura, ki se uporablja za shranjevanje zbirke podatkov. Povezan seznam dodeljuje pomnilnik svojim elementom ločeno v lastnem bloku pomnilnika, celotna struktura pa je pridobljena s povezovanjem teh elementov kot členov v verigi. Posamezno povezan seznam je sestavljen iz zaporedja vozlišč in vsako vozlišče ima referenco na naslednje vozlišče v zaporedju. Dvojno povezan seznam vsebuje zaporedje vozlišč, v katerih vsako vozlišče vsebuje referenco na naslednje vozlišče in tudi na prejšnje vozlišče.
Posamično povezan seznam
Vsak element na enojno povezanem seznamu ima dve polji, kot je prikazano na sliki 1. Podatkovno polje vsebuje dejanske shranjene podatke, naslednje polje pa sklic na naslednji element v verigi. Prvi element povezanega seznama je shranjen kot glava povezanega seznama.
Slika 2 prikazuje enojno povezan seznam s tremi elementi. Vsak element shrani svoje podatke in vsi elementi razen zadnjega shranijo referenco na naslednji element. Zadnji element ima v svojem naslednjem polju ničelno vrednost. Do katerega koli elementa na seznamu lahko dostopate tako, da začnete pri glavi in sledite naslednjemu kazalcu, dokler ne najdete zahtevanega elementa.
Dvojno povezan seznam
Vsak element na dvojno povezanem seznamu ima tri polja, kot je prikazano na sliki 3. Podobno kot pri enojno povezanem seznamu podatkovno polje vsebuje dejanske shranjene podatke, naslednje polje pa referenco 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 reference na prvi in prejšnji element. Zadnji element na seznamu ima ničelno vrednost v svojem naslednjem polju, prvi element na seznamu pa ima ničelno vrednost v prejšnjem polju. Po dvojno povezanem seznamu se lahko premikate naprej tako, da sledite naslednjim sklicem v vsakem elementu, podobno pa se lahko premikate nazaj z uporabo prejšnjih sklicev v vsakem elementu.
Kakšna je razlika med enojno in dvojno povezanim seznamom?
Vsak element na enojno povezanem seznamu vsebuje sklic na naslednji element na seznamu, medtem ko vsak element na dvojno povezanem seznamu vsebuje sklice na naslednji element in tudi prejšnji element na seznamu. Dvojno povezani seznami zahtevajo več prostora za vsak element na seznamu, osnovne operacije, kot sta vstavljanje in brisanje, pa so bolj zapletene, saj se morajo ukvarjati z dvema sklicema. Toda seznami z dvojno povezavo omogočajo lažjo manipulacijo, saj omogočajo premikanje po seznamu v smeri naprej in nazaj.
