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.

Back to index