Singly Linked List vs Double Linked List
Linked list er en lineær datastruktur som brukes til å lagre en samling av data. En koblet liste tildeler minne til elementene separat i sin egen minneblokk, og den overordnede strukturen oppnås ved å koble disse elementene som ledd i en kjede. En enkeltlenket 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.
Singly Linked List
Hvert element i en enkeltlenket 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 lagres som hodet på den koblede listen.
Figur 2 viser en enkeltlenket liste med tre elementer. Hvert element lagrer dataene sine, og alle elementene unntatt det siste lagrer en referanse til det neste elementet. Siste element har en nullverdi i neste felt. Ethvert element i listen kan nås ved å starte på toppen og følge neste peker til du oppfyller det nødvendige elementet.
Double Linked List
Hvert element i en dobbeltlenket liste har tre felt som vist i figur 3. I likhet med enkeltlenket 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 lagres som hodet på den koblede listen.
Figur 4 viser en dobbelt koblet liste med tre elementer. Alle de mellomliggende elementene lagrer referanser til de første og forrige elementene. Det siste elementet i listen har en nullverdi i det neste feltet og det første elementet i listen har en nullverdi i det forrige feltet. Dobbeltlenket liste kan krysses fremover ved å følge de neste referansene i hvert element, og kan på samme måte krysses bakover ved å bruke de tidligere referansene i hvert element.
Hva er forskjellen mellom Liste med enkeltkoblede og dobbeltkoblede liste?
Hvert element i den enkeltlenkede listen inneholder en referanse til det neste elementet i listen, mens hvert element i den dobbeltlenkede listen inneholder referanser til det neste elementet 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 doble lenkelister gjør det enklere å manipulere siden det gjør det mulig å krysse listen forover og bakover.
