Lista

Definition 

En lista har inte någon annan definition än definitionen av en sekvens (elementen är ordnade och det kan finnas dubletter). Denna tämligen abstrakta definition innebär att listan kan ha väldigt många olika operationer som dessutom gärna har olika namn i olika bibliotek. För att inte förlora oss i detaljer minimerar vi här antalet operationer.

Låt oss först titta på fallet att lägga in något i listan. Det finns utrymme för fem olika operationer: lägga in något först, sist, på en bestämd position, omedelbart före ett annat element och omedelbart efter ett annat element. Här nöjer vi oss med att kunna lägga in något sist och på en bestämd position. Detta ger följande operationer:
Sedan behöver vi operationer för att iterera igenom listan. För detta behövs minst två operationer: Placera cursorn först i listan och läsa nästa element. Detta ger följande minimala definition av operationer:
Dessutom kanske vi vill ha en specifik operation för att kolla om det finns fler element i listan, vi tar med en sådan också:
Vi tar däremot inte med operationer för att iterera från sista elementet och framåt.

Vidare skulle listan kunna ha operationer för att till exempel ange hur många element den innehåller samt ett antal operationer för att ta bort element på olika positioner (först, sist, ...). Dessa tillför dock inga nya aspekter på implementationen så vi hoppar över dem. Här kommer en header-fil med ovanstående definition, list.h .

Implementation

Array

Här kommer en implementation där listan sparas i en array, ArrayList.c , och ett program för att testa den, TestList.c . Testprogrammet skriver in ett antal tal i nummerordning och itererar sedan igenom listan och skriver ut dem.

Vad gäller exekveringshastighet är alla operationer utom insertAt() O(1) enligt samma resonemang som för stacken . Detta gäller även om vi tar hänsyn till arraydubbling. InsertAt() är däremot O(n) eftersom antalet element som måste kopieras är proportionellt mot n, åtminstone om vi lägger in något i början av listan (worst case).

Angående minesutrymme gäller samma resonemang som för stacken .

Länkad lista

Här kommer en implementation med en länkad lista, LinkedList.c .

Även här är, enligt resonemanget för stacken , alla operationer utom insertAt() O(1). InsertAt() är O(n) eftersom vi i worst case (när något ska in i listans slut) måste leta oss fram genom ca n noder.

Även här gäller för minesutrymme samma resonemang som för stacken .

Jämförelse

Även här gäller, med undantag av insertAt() och iterering, samma resonemang som för en stack . Att resonemangen blir så lika är ingen slump. Det beror på att implementationerna av listan och stacken är tämligen identiska. Datat lagras på exakt samma sätt, enda skillnaden är att datat kan läsas och skrivas i olika ordning (och att operationerna har olika namn).

Det är heller ingen slump att resonemanget för insertAt() inte har någon motsvarighet i en stack, det beror på att en stack inte har någon operation för att stoppa in data "mitt i". Är det då någon skillnad mellan insertAt() för en arrayimplementation och en länkad listimplementaion? Ja, det är det. Även om båda är O(n) är det med den länkade listan en pekare som tilldelas ca n gånger medans det med en array är ett element i listan. Detta innebär att arrayen oftast blir långsammare eftersom elementen oftast är större än en pekare.

Vad gäller iterering är operationerna O(1) för båda implementationerna men arrayen blir något snabbare eftersom vi där i next ökar cursor med ett medans vi i listimplementationen måste göra en tilldelning (cursor = cursor->next). Dels klarar processorn säkert ökningen med ett snabbare än tilldelningen, dels innebär tilldelningen en minnesaccess.

Detta innebär att vi kan dra följande slutsats: Arrayimplemetationen är snabbare om vi oftast itererar igenom hela listan, den länkade listan är däremot snabbare om vi oftast lägger till (eller tar bort) element mitt i listan.

Exempel

Uppgift 3.4 på sid 63, Ringlek.c .

Några finurligheter

Cursor

Ett problem med cursorn i våra exempel är att den är lagrad i listan. Det kommer inte att funka om flera itereringar pågår samtidigt. En lösning på detta är att låta det program som använder listan hålla reda på cursorn. I så fall ska beforeFirst() returnera en cursor som sedan ska skickas med till (och returneras av) next() och hasNext().

Dubbel länkad lista 

Tänk om vi vill kunna iterera bakifrån och framåt också, det blir väldigt krångligt med implementationen mha länkad lista ovan. En lösning är att i stället för (som ovan) en enkel länkad lista använda en dubbel länkad lista. Då har varje nod inte bara en pekare till noden efter utan även till noden före. Detta gör iterering bakifrån väsentligt snabbare, men i gengäld blir flera andra operationer lite långsamare eftersom det blir fler pekare att hantera.

Cirkulär lista utan pekare på first

I den länkade listan ovan finns det både en pekare till den första och en till den sista noden. Genom att göra listan cirkulär, dvs låta den sista noden peka på den första kan vi skippa pekaren first. first är då helt enkelt last->next .