Länkad lista

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2017-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Inom datavetenskap är en länkad lista en linjär följd av noder, även ibland kallat för celler, som länkas ihop med pekare. Noterbart är att till skillnad från en struktur som fält kan listans storlek, antalet noder, minska eller öka med enkel minneshantering. En länkad lista kan vara enkel- och dubbelriktad, där en enkelriktad endast kan traverseras från första till sista nod.

En nod består av två fält; ett informationsfält och ett adressfält. Informationsfältet är det data som ska sparas. Adressfältet innehåller adressen till nästa nod i listan eller ett speciellt värde, null, om det inte finns fler noder.

Prestanda

Fördelar

• Kan växa och minska i storlek efter behov
• Element kan läggas till och tas bort var som helst i listan.

Nackdelar

• För att hitta en nod n måste man tillämpa linjärsökning, det vill säga söka igenom var och en av n-1 noder innan nod n hittas. Anledningen är att det finns ingen relation mellan en nods position i listan och minnesadressen som den finns lagrad på.

Användningsområden

I de fall man har dynamiskt data där mängden inte är känd på förhand, data kanske måste läggas till och tas bort i mitten, och man inte har några krav på effektiv sökning är en länkad lista ett utmärkt val.

Stackar och köer implementeras med fördel över en länkad lista om man vill att de ska kunna växa och minska dynamiskt i storlek.

Gör man en länkad lista, där informationsfältet i varje nod i sin tur pekar på en länkad lista och så vidare (en länkad lista av länkade listor av länkade listor... med andra ord), får man ett träd.

Referenser

• Janlert, Lars-Erik, 1950- (2000 ;). Datatyper och algoritmer. Studentlitteratur. ISBN 9144013647. OCLC 186568746. http://worldcat.org/oclc/186568746. Läst 4 juni 2019 

Den här artikeln är helt eller delvis baserad på material från en annan språkversion av Wikipedia.