Länkad lista
Wikipedia
En länkad lista är en dynamisk datastruktur, det vill säga att den kan enkelt öka och minska i storlek efter behov, till skillnad från en array, som har en fix storlek. I en länkad lista kan även element läggas till och tas bort i mitten.
En länkad lista innehåller noll eller flera noder. 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.
[redigera] Fördelar
- Kan växa och minska i storlek efter behov
- Element kan läggas till och tas bort var som helst i listan.
[redigera] 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å.
- Tämligen anvancerad att implementera.
[redigera] 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 så ä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älltet i varje nod i sin tur pekar på en länkad lista och så vidare (en länkad lista av länkade listor med andra ord), så får man ett träd.
