Länkad lista i Python och när den faktiskt passar

När en kö får många ändringar i början kan en vanlig Python-lista bli besvärlig, och då kan en länkad lista verka lockande. En egen linked list i Python gör det enkelt att koppla in och koppla loss noder, men vinsten beror på om du redan känner till noden som ska ändras.

En nod pekar vidare, den hoppar inte till ett index

Tänk dig en kedja av kort där varje kort visar ett värde och adressen till nästa. I en enkellänkad lista börjar du vid huvudet, ofta kallat head, och följer sedan pekarna en i taget. Därför kan du inte slå upp ”element nummer 500” direkt som i en vanlig lista.

Det låter enkelt, men det påverkar vilka operationer som blir snabba. Jag tycker att den länkade listan är mest användbar som ett sätt att förstå referenser och datastrukturer, snarare än som en självklar ersättare för Pythons inbyggda typer.

En liten implementation räcker för att se hela kedjan

Här är en grundversion med tillägg sist, borttagning av första matchningen och iteration. Klassen håller även reda på svansen, så append slipper gå igenom hela kedjan varje gång.

class Node:
    __slots__ = ("value", "next")

    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, value):
        node = Node(value)

        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node

        self.size += 1

    def remove(self, value):
        previous = None
        current = self.head

        while current is not None:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next

                if current is self.tail:
                    self.tail = previous

                self.size -= 1
                return True

            previous = current
            current = current.next

        return False

    def __iter__(self):
        current = self.head

        while current is not None:
            yield current.value
            current = current.next

    def __len__(self):
        return self.size

items = LinkedList()
items.append("startsida")
items.append("portfolio")
items.append("kontakt")

items.remove("portfolio")
print(list(items))  # ['startsida', 'kontakt']

remove behöver hålla reda på både aktuell nod och föregående nod, eftersom den föregående nodens next måste kopplas om. Om listan blir tom ska både head och tail vara None; det här exemplet hanterar även borttagning från början och slutet.

En känd nod kan kopplas om på O(1)

Big O beskriver hur arbetet växer när antalet element ökar. Med listan ovan tar append O(1) tack vare svansreferensen, medan sökning och borttagning efter värde tar O(n), eftersom programmet kan behöva gå igenom varje nod.

Här finns en vanlig missuppfattning: ”infogning i en länkad lista är O(1)” gäller bara när platsen redan är känd. Om du först måste leta efter platsen blir hela operationen fortfarande O(n). För en editor där aktuell nod redan finns sparad kan det vara relevant; för en samling där du söker efter index är det sällan det.

Deque är oftast bättre för en vanlig kö

Om problemet är att ta bort det äldsta elementet ur en kö behöver du förmodligen inte bygga egna noder. Pythons dokumentation anger att collections.deque stöder tillägg och borttagning i båda ändar med ungefär O(1)-prestanda, medan list.pop(0) kräver att övriga referenser flyttas.

Som tumregel: välj deque för köer och arbete i båda ändar, en vanlig list för indexering och sekventiella data, och en egen länkad lista när du behöver kontroll över noderna eller övar på datastrukturer. Den skillnaden är tydligare än ett rent ”länkad lista mot lista”-påstående. Se beskrivningen av collections.deque i Python-dokumentationen.

Små noder kan ändå kosta mer minne

En nod innehåller mer än själva värdet: den behöver också en referens till nästa nod, och vanliga Python-objekt har attributhantering. Det innebär att en lång länkad lista ofta har betydande minneskostnad jämfört med en kompakt arrayliknande representation, även om exakta skillnader beror på Python-version och objekt.

I koden används __slots__ för att deklarera nodens två attribut och undvika den vanliga instansens attributordbok. Python-dokumentationen beskriver detta som en möjlig minnesbesparing, men det gör inte pekarstrukturen gratis och begränsar vilka attribut som kan läggas till dynamiskt. Läs om begränsningarna i Python-dokumentationens avsnitt om __slots__.

Felsök utifrån det som händer med kedjan

De flesta buggar visar sig när en referens glöms bort eller när en gräns, som början eller slutet, ändras. Tabellen hjälper dig att koppla ett symtom till den del av strukturen som behöver granskas.

En bra kontroll efter varje ändring är att gå igenom listan, räkna noderna och jämföra med len(items). Lägg gärna till tester för tom lista, borttagning av enda noden och upprepade värden, eftersom dessa fall avslöjar fel som ett enkelt exempel ofta missar.

Välj struktur efter hur data ska användas

En länkad lista gör det synligt hur referenser kan koppla ihop separata objekt, men den kräver mer kod och ger långsam åtkomst via position. För köer finns redan deque, och för data som ska indexeras snabbt är en vanlig lista i regel ett bättre förstaval.

Om du ändå bygger en egen implementation, börja med enkellänkad form och testa särskilt tom lista, en enda nod och borttagning av svansen. Då blir kedjan lättare att förstå, och buggarna svårare att gömma bakom till synes fungerande exempel.