Länkade listor - Till consboxens ära
Det finns en sak som man som programmerare måste lära sig att
älska. Den är en viktig del av den grundläggande teoretiska
datavetenskapen och är i princip omöjlig att undvika oavsett val
av programmeringsspråk. Den har förmodligen många namn, men det
som används av Uppsalas datavetare och således också av mig är
consbox. Faktum är att consboxen är så omtyckt att den blivit
symbol för den datavetenskapliga utbildningen vid Uppsala
universitet.
Vad är då en consbox och vad är det med den som är så bra? Jo,
consboxen symboliserar listan, en företeelse som alla
programmerare förr eller senare blir i desperat behov av att
behärska. Listans användningsområde är så vidsträckt att det är
svårt att ge något enstaka exempel, men ett litet axplock av
områden skulle kunna vara minneshantering, filsystem,
register/databaser, ja faktiskt alla sammanhang där man vill lagra
data på ett flexibelt sätt.
Varje element i en lista består av två delar: Data och en referens
till nästa element. Figuren med de två fyrkanterna och de två
pilarna visar just ett element i en lista (en consbox). Till
vänster finns en pil som pekar nedåt. Denna brukar kallas CAR och
tanken är att den pekar på det data som hör hemma på den platsen i
listan. Den andra pilen pekar åt höger på nästa element. Denna
brukar kallas CDR. Dessa pilar är egentligen adresser i datorns
minne, men det behöver man inte veta för att förstå principen
bakom en lista.
I många programmeringsspråk, främst funktionella sådana, är listan
ett naturligt inslag som man kan använda utan att behöva tänka
särskilt mycket. Ofta använder man i dessa sammanhang rekursiva
funktioner som jobbar på listans element. I lågnivåspråk, som
till exempel C, krävs det lite mer tanke innan man kan bygga upp
en lista och while-loopar är oftast att föredra framför
rekursion. För att hantera listor i C, (om man nu inte väljer att
använda någon av de färdiga implementationer som finns att få tag
i), så måste man veta hur man använder pekare. En pekare är
nämligen precis vad som används för att referera till data och
andra element i en lista. Bland källkoderna finns enkla exempel som visar
hur en lista kan användas.
Listan vs. Arrayen
Varför vill man då använda en lista i stället för till exempel en
array? Främsta argumentet för listan är flexibilitet. Listan kan
växa och krympa dynamiskt, (medan programmet körs). Man kan lätt
kasta om ordningen på data i en lista utan att behöva kopiera. Det
finns heller inget i listans natur som säger att det man lagrar
måste vara av samma typ, man kan utan problem ha en lista som
innehåller totalt skilda saker. Priset man får betala är
overhead. Listan tar mer plats i minnet än en enkel array (för
samma antal element). Det tar längre tid att hitta en given plats
i en lista jämfört med en array och det krävs lite mer jobb för
att underhålla en lista. När man vet exakt hur många element man
ska ha eller om hastighet vid access är avgörande är en array
förmodligen att föredra, men vet man inte hur många element man
kommer att vilja ha, eller vill man kunna sortera om data och
placera in nya element på valfri plats vill man troligtvis ha en
länkad lista.
Tillbaka till indexet |