Forskjellen mellom Singly Linked List og Doubly Linked List

Singly Linked List vs Doubly Linked List

Lenkeliste er en lineær datastruktur som brukes til å lagre en samling av data. En koblet liste tildeler hukommelsen til elementene separat i sin egen blokk av minne, og den overordnede strukturen oppnås ved å koble disse elementene som lenker i en kjede. En enslig koblet 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 enkeltkoblet liste har to felt som vist i figur 1. Datafeltet holder de faktiske dataene 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 enkeltkoblet liste med tre elementer. Hvert element lagrer dataene sine og alle elementene unntatt den siste lagrer en referanse til neste element. Sist element har null verdi i neste felt. Ethvert element i listen kan nås ved å starte ved hodet og følge den neste pekeren til du møter det nødvendige elementet.

Dobbeltkoblet liste

Hvert element i en dobbeltkoblet liste har tre felt som vist på figur 3. I likhet med en enkeltkoblet liste holder datafeltet de faktiske lagrede dataene, 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 de første og forrige elementene. Siste element i listen har null verdi i sitt neste felt og det første elementet i listen har null verdi i det forrige feltet. Dobbeltkoblet liste kan krysse fremover ved å følge de neste referansene i hvert element og på samme måte kan du krysse bakover med de forrige referansene i hvert element.

Hva er forskjellen mellom Singly Linked List og Doubly Linked List?

Hvert element i den enkeltkoblede listen inneholder en referanse til det neste elementet i listen, mens hvert element i den dobbeltkoblede listen inneholder referanser til det neste elementet, i tillegg til 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 fordi de må håndtere to referanser. Men doble koblingslister tillater lettere manipulering, siden det tillater å krysse listen i frem og tilbake retninger.