Singly Linked List vs Double Linked List
Linked liste er en lineær datastruktur, der bruges til at gemme en samling af data. En sammenkædet liste allokerer hukommelse til sine elementer separat i sin egen hukommelsesblok, og den overordnede struktur opnås ved at forbinde disse elementer som led i en kæde. En enkelt forbundet liste består af en sekvens af noder, og hver node har en reference til den næste node i sekvensen. En dobbelt linket liste indeholder en sekvens af noder, hvor hver node indeholder en reference til den næste node såvel som til den forrige node.
Singly Linked List
Hvert element i en enkelt linket liste har to felter som vist i figur 1. Datafeltet indeholder de faktiske data, der er gemt, og det næste felt indeholder referencen til det næste element i kæden. Det første element i den linkede liste gemmes som hovedet på den linkede liste.
Figur 2 viser en enkelt linket liste med tre elementer. Hvert element gemmer sine data, og alle elementer undtagen det sidste gemmer en reference til det næste element. Sidste element har en nulværdi i dets næste felt. Ethvert element på listen kan tilgås ved at starte ved hovedet og følge den næste markør, indtil du opfylder det påkrævede element.
dobbelt linket liste
Hvert element i en dobbeltlinket liste har tre felter som vist i figur 3. I lighed med en enkeltforbundet liste indeholder datafeltet de faktiske data, der er lagret, og det næste felt indeholder referencen til det næste element i kæden. Derudover indeholder det forrige felt referencen til det forrige element i kæden. Det første element i den linkede liste gemmes som hovedet på den linkede liste.
Figur 4 viser en dobbeltforbundet liste med tre elementer. Alle de mellemliggende elementer gemmer referencer til det første og forrige element. Sidste element på listen har en nulværdi i dets næste felt, og det første element på listen har en nulværdi i dets forrige felt. Dobbeltkoblet liste kan gennemløbes fremad ved at følge de næste referencer i hvert element og kan på samme måde gennemløbes baglæns ved at bruge de tidligere referencer i hvert element.
Hvad er forskellen mellem enkelt-linkede liste og dobbelt-linkede liste?
Hvert element i den enkelt-linkede liste indeholder en reference til det næste element i listen, mens hvert element i den dobbelt-linkede liste indeholder referencer til det næste element såvel som det forrige element i listen. Dobbeltlinkede lister kræver mere plads til hvert element i listen, og elementære operationer såsom indsættelse og sletning er mere komplekse, da de skal håndtere to referencer. Men dobbeltlinklister tillader lettere manipulation, da det gør det muligt at krydse listen frem og tilbage.
