Skillnad mellan Singly Linked List och Doubly Linked List

Singly Linked List vs Doubly Linked List

Länkade lista är en linjär datastruktur som används för att lagra en samling data. En länkad lista allokerar minne till dess element separat i sitt eget minnesblock och den övergripande strukturen erhålls genom att länka dessa element som länkar i en kedja. En ensam länkad lista består av en sekvens av noder och varje nod har en referens till nästa nod i sekvensen. En dubbelt länkad lista innehåller en sekvens av noder där varje nod innehåller en referens till nästa nod samt till föregående nod.

Enbart länkad lista

Varje element i en ensam länkad lista har två fält som visas i Figur 1. Datafältet innehåller aktuella data lagrade och nästa fält innehåller referensen till nästa element i kedjan. Det första elementet i den länkade listan sparas som huvudet på den länkade listan.

Figur 2 visar en ensam länkad lista med tre element. Varje element lagrar sin data och alla element utom den sista lagrar en referens till nästa element. Det sista elementet har ett nollvärde i nästa fält. Alla element i listan kan nås genom att börja i huvudet och följa nästa pekare tills du uppfyller det önskade elementet.

Dubbelt länkad lista

Varje element i en dubbelförbunden lista har tre fält som visas i Figur 3. Liknande till enbart länkad lista innehåller datafältet de faktiska data som lagras och nästa fält innehåller referensen till nästa element i kedjan. Dessutom innehåller föregående fält hänvisningen till föregående element i kedjan. Det första elementet i den länkade listan sparas som huvudet på den länkade listan.

Figur 4 visar en dubbelkopplad lista med tre element. Alla mellanliggande element lagrar referenser till de första och föregående elementen. Det sista elementet i listan har ett nollvärde i nästa fält och det första elementet i listan har ett nollvärde i föregående fält. Dubbelt länkad lista kan spåras framåt genom att följa de följande referenserna i varje element och på samma sätt kan spåras bakåt med hjälp av tidigare referenser i varje element.

Vad är skillnaden mellan Singly Linked List och Doubly Linked List?

Varje element i den ensamlänkade listan innehåller en hänvisning till nästa element i listan, medan varje element i den dubbelförbundna listan innehåller hänvisningar till nästa element samt föregående element i listan. Dubbelt länkade listor kräver mer utrymme för varje element i listan och elementära operationer som införande och radering är mer komplexa eftersom de måste hantera två referenser. Men dubbla länklistor gör det lättare att manipulera eftersom det går att korsa listan i framåtriktad och bakåtriktad riktning.