Singly Linked List kontra Dubbellänkad List
Länkad lista är en linjär datastruktur som används för att lagra en samling data. En länkad lista allokerar minne till sina 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 enkellänkad lista består av en sekvens av noder och varje nod har en referens till nästa nod i sekvensen. En dubbellänkad lista innehåller en sekvens av noder där varje nod innehåller en referens till nästa nod såväl som till föregående nod.
Singly Linked List
Varje element i en enkellänkad lista har två fält som visas i figur 1. Datafältet innehåller den faktiska data som är lagrad 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 huvudet på den länkade listan.
Figur 2 visar en enskilt länkad lista med tre element. Varje element lagrar sina data och alla element utom det 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 det obligatoriska elementet.
Double Linked List
Varje element i en dubbellänkad lista har tre fält som visas i figur 3. I likhet med en enskild länkad lista innehåller datafältet den faktiska data som är lagrad och nästa fält innehåller referensen till nästa element i kedjan. Dessutom innehåller det föregående fältet referensen till det föregående elementet i kedjan. Det första elementet i den länkade listan lagras som huvudet på den länkade listan.
Figur 4 visar en dubbelt länkad 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 sitt föregående fält. Dubbellänkad lista kan förflyttas framåt genom att följa nästa referenser i varje element och på liknande sätt kan korsas bakåt med de tidigare referenserna i varje element.
Vad är skillnaden mellan listan med enkellänkade och dubbellänkade?
Varje element i den enkellänkade listan innehåller en referens till nästa element i listan, medan varje element i den dubbellänkade listan innehåller referenser till nästa element såväl som föregående element i listan. Dubbellänkade listor kräver mer utrymme för varje element i listan och elementära operationer som infogning och borttagning är mer komplexa eftersom de måste hantera två referenser. Men listor med dubbla länkar möjliggör enklare manipulering eftersom det gör det möjligt att gå igenom listan i riktningar framåt och bakåt.
