Enkeltkædet liste vs Dobbeltkædet liste
Tilknyttet liste er en lineær datastruktur, der bruges til at gemme en indsamling af data. En sammenkædet liste tildeler hukommelse til sine elementer separat i sin egen hukommelsesblok, og den samlede 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 henvisning til den næste node i sekvensen. En dobbeltkoblet liste indeholder en sekvens af noder, hvor hver node indeholder en henvisning til den næste knude såvel som til den foregående knude.
Enkelt forbundet liste
Hvert element i en enkelt sammenkædet liste har to felter som vist i figur 1. Datafeltet indeholder de faktisk lagrede data, og det næste felt indeholder henvisningen til det næste element i kæden. Det første element på den sammenkædede liste er gemt som hovedet på den sammenkædede liste.
Figur 2 viser en enkelt forbundet 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 nulværdi i det næste felt. Du kan få adgang til ethvert element på listen ved at starte ved hovedet og følge den næste markør, indtil du møder det krævede element.
Dobbelt sammenkædet liste
Hvert element i en dobbeltkoblet liste har tre felter som vist i figur 3. I lighed med enkeltkædet 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 foregående felt henvisningen til det forrige element i kæden. Det første element på den sammenkædede liste er gemt som hovedet på den sammenkædede liste.
Figur 4 viser en dobbeltkoblet liste med tre elementer. Alle mellemelementer gemmer henvisninger til det første og det forrige element. Sidste element på listen har en nulværdi i det næste felt, og det første element i listen har en nulværdi i det forrige felt. Dobbeltkoblet liste kan krydses fremad ved at følge de næste referencer i hvert element og kan ligeledes krydses bagud ved hjælp af de tidligere referencer i hvert element.
Hvad er forskellen mellem enkeltkædet liste og dobbeltkoblet liste?
Hvert element i den enkeltlinkede liste indeholder en henvisning til det næste element på listen, mens hvert element i den dobbeltkoblede liste indeholder henvisninger til det næste element såvel som det forrige element på listen. Dobbeltkoblede lister kræver mere plads til hvert element på listen, og elementære operationer såsom indsættelse og sletning er mere komplekse, da de skal håndtere to referencer. Men dobbeltlinklister muliggør lettere manipulation, da det gør det muligt at krydse listen i fremad og bagud retning.
