Liststrukturer

Liststrukturer är datastrukturer som lagrar en sekvens av element i en bestämd ordning. De bevarar varje elements position och gör det möjligt att iterera över dem samt infoga och ta bort element på olika ställen i listan. Valet av liststruktur påverkar prestanda för operationer, minnesanvändning och cachebeteende.

De vanligaste typerna är fältbaserade listor (dynamiska arrayer) och länkade listor. Dynamiska arrayer lagrar elementen i ett sammanhängande minnesblock. De erbjuder snabb access via index (O(1)) och god minnesutnyttjande när storleken är relativt konstant. Vid växling uppstår oftast omallokering och kopiering av elementen, vilket ger amortiserad kostnad men kan innebära kostnader vid expansion.

Länkade listor består av noder där varje nod innehåller data och en pekare till nästa nod (singel) eller till både nästa och föregående nod (dubbel). De möjliggör snabb infogning och borttagning när man har pekare till positionen och behöver inte flytta övriga element, men åtkomsten vid slumpmässig index är längre (O(n)) och det krävs extra minne för pekarna. Cirkulära varianter används i vissa kö- eller buffertapplikationer.

Komplexiteter och överväganden: åtkomst i fältbaserade listor är ofta O(1), medan infogning i mitten är O(n). För länkade listor är sökningen O(n) medan infogning och borttagning i början vanligtvis kan göras i O(1) om rätt pekare finns. Valet påverkas av behovet av snabb slumpmässig access, minneshantering och ofta av cacheläget.

Användningsområden inkluderar implementation av stackar och köer, samt scenarier där storleken varierar och frekventa insättningar eller borttagningar sker i början eller mitten av listan. I praktiken erbjuds ofta flera typer av liststrukturer i ett programspråk, vilka används beroende på krav på prestanda och minneshantering.