Forskellen mellem en enkelt linket liste og en dobbelt forbundet liste

Singelt forbundet liste vs dobbelt forbundet liste

Tilknyttet liste er en lineær datastruktur, der bruges til at gemme en samling af data. En tilknyttet liste tildeler hukommelse til dens elementer separat i sin egen hukommelsesblok, og den samlede struktur opnås ved at linke disse elementer som links i en kæde. En enkelt bundet liste består af en sekvens af knudepunkter, og hver knude har en henvisning til den næste knude i sekvensen. En dobbeltkædet liste indeholder en sekvens af noder, hvor hver knude indeholder en henvisning til den næste knude samt til den forrige knude.

Enkelt forbundet liste

Hvert element i en enkelt sammenkoblet liste har to felter som vist i figur 1. Datafeltet indeholder de faktiske data, der er gemt, og det næste felt indeholder henvisningen til det næste element i kæden. Det første element i den tilknyttede liste gemmes som hovedet på den tilknyttede liste.

Figur 2 viser en enkelt knyttet liste med tre elementer. Hvert element gemmer sine data og alle elementer undtagen det sidste gemmer en henvisning til det næste element. Sidste element har en nullværdi i det næste felt. Ethvert element på listen kan fås ved at starte ved hovedet og følge den næste markør, indtil du opfylder det krævede element.

Dobbeltkædet liste

Hvert element i en dobbeltkædet liste har tre felter som vist i figur 3. Ligesom en enkelt linket liste indeholder datafeltet de faktiske data, der er gemt, og det næste felt indeholder henvisningen til det næste element i kæden. Derudover indeholder det forrige felt henvisningen til det forrige element i kæden. Det første element i den tilknyttede liste gemmes som hovedet på den tilknyttede liste.

Figur 4 viser en dobbeltkædet liste med tre elementer. Alle mellemliggende elementer gemmer referencer til de første og forrige elementer. Sidste element på listen har en nullværdi i det næste felt, og det første element på listen indeholder en nullværdi i det forrige felt. Dobbeltkædet liste kan køres fremad ved at følge de næste referencer i hvert element og på lignende måde kan køres baglæns ved hjælp af de foregående referencer i hvert element.

Hvad er forskellen mellem Singled Linked List og Doubly Linked List?

Hvert element i den enkeltvist forbundne liste indeholder en henvisning til det næste element på listen, mens hvert element i den dobbeltkædede liste indeholder henvisninger til det næste element såvel som det forrige element på listen. Dobbeltkædede lister kræver mere plads for hvert element på listen, og elementære operationer som indsættelse og sletning er mere kompliceret, da de skal beskæftige sig med to referencer. Men dobbeltkædelister giver mulighed for lettere manipulation, da det gør det muligt at krydse listen i retninger frem og tilbage.