Enkeltkoblet liste vs Dobbeltkoblet liste
Koblet liste er en lineær datastruktur som brukes til å lagre en innsamling av data. En koblet liste tildeler minne til elementene separat i sin egen hukommelsesblokk, og den generelle strukturen oppnås ved å koble disse elementene som lenker i en kjede. En enkeltkoblet liste består av en sekvens av noder, og hver node har en referanse til neste node i sekvensen. En dobbeltkoblet liste inneholder en sekvens av noder der hver node inneholder en referanse til neste node så vel som til forrige node.
Enkelt koblet liste
Hvert element i en enkelt koblet liste har to felt som vist i figur 1. Datafeltet inneholder de faktiske dataene som er lagret, og det neste feltet inneholder referansen til neste element i kjeden. Det første elementet i den koblede listen er lagret som hodet til den koblede listen.
Figur 2 viser en enkelt koblet liste med tre elementer. Hvert element lagrer dataene og alle elementene unntatt den siste lagrer en referanse til neste element. Siste element har en nullverdi i sitt neste felt. Du kan få tilgang til ethvert element i listen ved å starte på hodet og følge neste peker til du oppfyller ønsket element.
Dobbeltkoblet liste
Hvert element i en dobbeltkoblet liste har tre felt som vist i figur 3. I likhet med enkeltkoblet liste inneholder datafeltet de faktiske dataene som er lagret, og det neste feltet inneholder referansen til neste element i kjeden. I tillegg inneholder det forrige feltet referansen til det forrige elementet i kjeden. Det første elementet i den koblede listen er lagret som hodet til den koblede listen.
Figur 4 viser en dobbeltkoblet liste med tre elementer. Alle mellomelementene lagrer referanser til det første og forrige elementet. Siste element i listen har en nullverdi i sitt neste felt, og det første elementet i listen har en nullverdi i det forrige feltet. Dobbeltkoblet liste kan krysses fremover ved å følge de neste referansene i hvert element, og kan på samme måte krysses bakover ved hjelp av de forrige referansene i hvert element.
Hva er forskjellen mellom enkeltkoblet liste og dobbeltkoblet liste?
Hvert element i den enkeltkoblede listen inneholder en referanse til neste element i listen, mens hvert element i den dobbeltkoblede listen inneholder referanser til neste element, så vel som det forrige elementet i listen. Dobbeltkoblede lister krever mer plass for hvert element i listen, og elementære operasjoner som innsetting og sletting er mer komplekse siden de må håndtere to referanser. Men dobbeltkoblingslister tillater enklere manipulering, siden det gjør det mulig å krysse listen i fremover og bakover.