Enskilt länkad lista jämfört med dubbelt länkad lista
Länkad lista är en linjär datastruktur som används för att lagra en datainsamling. En länkad lista tilldelar minne till sina element separat i sitt eget minnesblock och den totala strukturen erhålls genom att länka dessa element som länkar i en kedja. En enstaka 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 hänvisning till nästa nod liksom till den tidigare noden.
Singly Linked List
Varje element i en enskilt länkad lista har två fält som visas i figur 1. Datafältet innehåller den faktiska lagrade data och nästa fält innehåller referensen till nästa element i kedjan. Det första elementet i den länkade listan lagras som huvud för den länkade listan.
Figur 2 visar en enstaka länkad lista med tre element. Varje element lagrar sina 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 vid huvudet och följa nästa pekare tills du uppfyller önskat element.
Dubbel länkad lista
Varje element i en dubbelt länkad lista har tre fält som visas i figur 3. På samma sätt som en länkad lista innehåller datafältet den faktiska lagrade data och nästa fält innehåller referensen till nästa element i kedjan. Dessutom innehåller föregående fält referens till föregående element i kedjan. Det första elementet i den länkade listan lagras som huvud för den länkade listan.
Figur 4 visar en dubbelt länkad lista med tre element. Alla mellanelement lagrar referenser till första och tidigare element. Det sista elementet i listan har ett nullvärde i nästa fält och det första elementet i listan innehåller ett nullvärde i sitt tidigare fält. Dubbel länkad lista kan spåras framåt genom att följa nästa referenser i varje element och på liknande sätt kan spåras bakåt med de tidigare referenserna i varje element.
Vad är skillnaden mellan singelinkad lista och dubbelt länkad lista?
Varje element i den enskilt länkade listan innehåller en hänvisning till nästa element i listan, medan varje element i den dubbelt länkade listan innehåller referenser till nästa element såväl som föregående element i listan. Dubbel länkade listor kräver mer utrymme för varje element i listan och elementära operationer som insättning och radering är mer komplexa eftersom de måste hantera två referenser. Men dubbelt länklistor möjliggör enklare manipulation eftersom det gör det möjligt att korsa listan i riktning framåt och bakåt.
