Länkade listor i Python: handledning med exempel

En länkad lista är en datastruktur som spelar en avgörande roll för hur data organiseras och hanteras. Den innehåller en serie noder som lagras på slumpmässiga platser i minnet, vilket möjliggör effektiv minneshantering. Varje nod i en länkad lista innehåller två huvudkomponenter: dataparten och en referens till nästa nod i sekvensen.

Om det här konceptet verkar komplext vid första anblick behöver du inte oroa dig!

Vi bryter ner det till grunderna för att förklara vad länkade listor är, varför vi använder dem och vilka unika fördelar de erbjuder.

Varför länkade listor?

Länkade listor skapades för att övervinna olika nackdelar kopplade till att lagra data i vanliga listor och arrayer, som beskrivs nedan:

Enkel insättning och borttagning

I listor kräver insättning eller borttagning av ett element på någon annan plats än slutet att alla efterföljande element flyttas till en ny position. Denna process har tidskomplexiteten O(n) och kan avsevärt försämra prestandan, särskilt när listan växer i storlek. Om du inte redan är bekant med hur listor fungerar eller hur de implementeras kan du läsa vår handledning om Python-listor.

Länkade listor fungerar däremot annorlunda. De lagrar element på olika, icke-sammanhängande minnesplatser och kopplar dem via pekare till efterföljande noder. Denna struktur gör att länkade listor kan lägga till eller ta bort element var som helst genom att helt enkelt ändra länkarna för att inkludera ett nytt element eller hoppa över det borttagna.

När du väl har en direkt referens till noden vid insättnings- eller borttagningspunkten är själva operationen O(1). Att hitta den positionen kräver dock fortfarande O(n) traversering, så O(1)-fördelen gäller bara när du redan håller en pekare till den relevanta noden (till exempel när du arbetar vid listans huvud).

Dynamisk storlek

Python-listor är dynamiska arrayer, vilket innebär att de ger flexibilitet att ändra storlek.

Denna process innefattar dock en rad komplexa operationer, inklusive att allokera om arrayen till ett nytt, större minnesblock. En sådan omallokering är ineffektiv eftersom element kopieras till ett nytt block, vilket potentiellt allokerar mer utrymme än vad som omedelbart behövs.

Till skillnad från detta kan länkade listor växa och krympa dynamiskt utan behov av omallokering eller storleksändring. Det gör dem till ett bättre val för uppgifter som kräver hög flexibilitet.

Minneseffektivitet

Listor allokerar minne för alla sina element i ett sammanhängande block. Om en lista behöver växa bortom sin initiala storlek måste den allokera ett nytt, större block av sammanhängande minne och sedan kopiera alla befintliga element till detta nya block. Denna process är tidskrävande och ineffektiv, särskilt för stora listor. Å andra sidan, om den initiala storleken på listan överskattas, slösas det outnyttjade minnet.

Länkade listor allokerar däremot minne för varje element separat. Denna struktur leder till bättre minnesutnyttjande eftersom minne för nya element kan allokeras i takt med att de läggs till.

När ska du använda länkade listor?

Även om länkade listor ger vissa fördelar jämfört med vanliga listor och arrayer, såsom dynamisk storlek och minnes­effektivitet, har de också begränsningar. Eftersom pekare för varje element måste lagras för att referera till nästa nod blir minnesanvändningen per element högre med länkade listor. Dessutom tillåter denna datastruktur inte direkt åtkomst till data. Att komma åt ett element kräver sekventiell genomgång från listans början, vilket ger tidskomplexiteten O(n) för sökning.

Valet mellan länkad lista och array beror på applikationens specifika behov. Länkade listor är mest användbara när:

• Du ofta behöver infoga och ta bort många element
• Datamängdens storlek är oförutsägbar eller sannolikt förändras ofta
• Direktåtkomst till element inte är ett krav
• Datasetet innehåller stora element eller strukturer

Typer av länkade listor

Det finns tre typer av länkade listor, som var och en erbjuder unika fördelar i olika scenarier. Dessa typer är:

Enkelriktade länkade listor

Enkelriktad länkad lista

En enkelriktad länkad lista är den enklaste typen av länkad lista, där varje nod innehåller data och en referens till nästa nod i sekvensen. De kan bara traverseras i en riktning – från huvudet (första noden) till svansen (sista noden).

Varje nod i en enkelriktad länkad lista består typiskt av två delar:

• Data: Den faktiska informationen som lagras i noden.
• Nästa pekare: En referens till nästa nod. Den sista nodens nästa pekare är vanligtvis satt till null.

Eftersom dessa datastrukturer bara kan traverseras i en riktning kräver åtkomst till ett specifikt element via värde eller index att man börjar vid huvudet och rör sig sekventiellt genom noderna tills den önskade noden hittas. Denna operation har tidskomplexiteten O(n), vilket gör den mindre effektiv för stora listor.

Att infoga och ta bort en nod i början av en enkelriktad länkad lista är mycket effektivt med tidskomplexiteten O(1). Däremot kräver insättning och borttagning i mitten eller i slutet att listan traverseras dit, vilket leder till tidskomplexiteten O(n).

Utformningen av enkelriktade länkade listor gör dem användbara när man utför operationer som sker i början av listan.

Dubbellänkade listor

Dubbellänkad lista

En nackdel med enkelriktade länkade listor är att vi bara kan traversera dem i en riktning och inte kan gå tillbaka till föregående nod vid behov. Denna begränsning inskränker vår förmåga att utföra operationer som kräver tvåvägsnavigering.

Dubbellänkade listor löser detta genom att varje nod får en extra pekare, vilket säkerställer att listan kan traverseras i båda riktningarna. Varje nod i en dubbellänkad lista innehåller tre element: data, en pekare till nästa nod och en pekare till föregående nod.

Cirkulära länkade listor

Cirkulär länkad lista

Cirkulära länkade listor är en specialiserad form av länkad lista där den sista noden pekar tillbaka på den första noden, vilket skapar en cirkulär struktur. Det betyder att, till skillnad från de enkel- och dubbellänkade listorna vi sett hittills, så tar den cirkulära länkade listan inte slut; den loopar runt.

Den cykliska naturen hos cirkulära länkade listor gör dem idealiska för scenarier som behöver loopas kontinuerligt, som brädspel som går från sista spelaren tillbaka till den första, eller i algoritmer som round-robin-schemaläggning.

Tidskomplexitet i korthet

Det är nyttigt att med en överblick se hur länkade listor står sig mot Python-listor:

Det viktigaste att ta med sig: länkade listor vinner på insättningar och borttagningar vid huvudet (O(1)), men förlorar på det mesta annat. Om du inte ofta lägger till eller tar bort element i början av din datastruktur är en vanlig Python-lista troligen ett bättre val.

Hur skapar man en länkad lista i Python

Nu när vi förstår vad länkade listor är, varför vi använder dem och deras varianter, går vi vidare till att implementera dessa datastrukturer i Python. Notebooken för denna handledning finns också i denna DataLab-arbetsbok; om du skapar en kopia kan du redigera och köra koden. Detta är ett utmärkt alternativ om du stöter på problem med att köra koden själv!

Initiera en nod

Som vi tidigare lärt oss är en nod ett element i den länkade listan som lagrar data och en referens till nästa nod i sekvensen. Så här kan du definiera en nod i Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return f"Node({self.data})"

Koden ovan initierar en nod genom att utföra två huvudåtgärder: Attributet ”data” för noden tilldelas ett värde som representerar den faktiska information som noden ska innehålla. Attributet ”next” representerar adressen till nästa nod. Detta är för närvarande satt till None, vilket betyder att den inte länkar till någon annan nod i listan. När vi fortsätter att lägga till nya noder i den länkade listan kommer detta attribut att uppdateras för att peka på efterföljande nod.

Skapa en klass för länkad lista

Därefter behöver vi skapa klassen för den länkade listan. Den kapslar in alla operationer för att hantera noderna, såsom insättning och borttagning. Vi börjar med att initiera den länkade listan:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

Genom att sätta self.head till None anger vi att den länkade listan initialt är tom och att det inte finns några noder i listan att peka på. Vi går nu vidare till att fylla listan genom att infoga nya noder.

Infoga en ny nod i början av en länkad lista

I klassen LinkedList ska vi lägga till en metod som skapar en ny nod och placerar den i början av listan:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Varje gång du anropar metoden ovan skapas en ny nod med din angivna data. Den nya nodens nästa pekare sätts till den aktuella listans huvud, vilket placerar noden framför de befintliga noderna. Slutligen görs den nyskapade noden till listans huvud.

Nu ska vi fylla denna länkade lista med en serie ord för att bättre förstå hur insättnings­operationen fungerar. För att åstadkomma detta skapar vi först en metod som är avsedd att traversera och skriva ut listans innehåll:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Metoden ovan skriver ut innehållet i vår länkade lista. Låt oss nu använda metoderna vi har definierat för att fylla vår lista med en serie ord: ”the quick brown fox”.

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Raderna ovan bör ge följande utskrift:

"the quick brown fox"

Infoga en ny nod i slutet av en länkad lista

Nu skapar vi en metod som heter insertAtEnd i klassen LinkedList för att skapa en ny nod i slutet av listan. Om listan är tom blir den nya noden listans huvud. Annars läggs den till efter den nuvarande sista noden i listan. Så här fungerar det i praktiken:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Metoden ovan börjar med att skapa en ny nod. Den kontrollerar sedan om listan är tom, och om så är fallet tilldelas den nya noden som listans huvud. Annars traverserar den listan för att hitta den sista noden och sätter denna nods pekare till den nya noden.

Nu behöver vi inkludera denna metod i vår LinkedList-klass och använda den för att lägga till ett ord i slutet av vår lista. För att göra detta, ändra din main-funktion så att den ser ut så här:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Observera att vi helt enkelt har anropat metoden insertAtEnd för att skriva ut ordet ”jumps” i slutet av listan. Koden ovan bör ge följande utskrift:

"the quick brown fox jumps"

Ta bort en nod från början av en länkad lista

Att ta bort den första noden i en länkad lista är enkelt eftersom det bara handlar om att peka listans huvud till den andra noden. På så sätt kommer den första noden inte längre att vara en del av listan. För att göra detta, inkludera följande metod i klassen LinkedList:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Ta bort en nod från slutet av en länkad lista

För att ta bort den sista noden i en länkad lista måste vi traversera listan för att hitta den näst sista noden och ändra dess nästa pekare till None. På så sätt kommer den sista noden inte längre att vara en del av listan. Kopiera och klistra in följande metod i din LinkedList-klass för att åstadkomma detta:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Metoden ovan kontrollerar först om den länkade listan är tom och returnerar i så fall ett meddelande till användaren. Annars, om listan innehåller en enda nod, tas den noden bort. För listor med flera noder lokaliserar metoden den näst sista noden och dess referens till nästa nod uppdateras till None.

Låt oss nu uppdatera main-funktionen för att ta bort element från början och slutet av den länkade listan:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Koden ovan skriver ut listan före och efter borttagning och visar hur insättnings- och borttagnings­operationer fungerar i länkade listor. Du bör se följande utskrift när du kör koden:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Söka i den länkade listan efter ett specifikt värde

Den sista operationen vi lär oss i detta kapitel är hämtning av ett specifikt värde i den länkade listan. För att göra detta bör metoden börja vid listans huvud och iterera genom varje nod, och kontrollera om nodens data matchar sök­värdet. Här är en praktisk implementering av denna operation:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

För att hitta specifika värden i den länkade lista vi har skapat uppdaterar du din main-funktion för att inkludera sökmetoden vi just skapat:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Koden ovan ger följande utskrift:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

Ordet ”quick” har hittats i den länkade listan eftersom det finns på den första positionen i listan. Däremot är ordet ”lazy” inte en del av listan, vilket är anledningen till att det inte har hittats.

Avslutande tankar

Om du har tagit dig ända hit, grattis! Du har nu en stabil förståelse för de grundläggande principerna bakom länkade listor, inklusive deras struktur, typer, hur man lägger till och tar bort element samt hur man traverserar dem.

Men resan slutar inte här. Länkade listor är bara början på världen av datastrukturer och algoritmer. Här är några möjliga nästa steg för att fördjupa din förståelse av ämnet:

Skapa ditt eget projekt

Fördjupa dig i praktiska tillämpningar av länkade listor genom att integrera dem i ett kodnings- eller data science-projekt. Länkade listor används för att utveckla filsystem, konstruera hashtabeller och till och med skapa GPS-navigationssystem och brädspel. För att komma igång med egna projekt, kolla in våra kostnadsfria guidade data science-projekt som lär dig att lösa verkliga problem i Python, R och SQL.

Lär dig mer om datastrukturer och algoritmer

Att lära sig andra datastrukturer, såsom träd, stackar och köer, är ett naturligt steg efter att du förstått länkade listor. Dessa strukturer bygger vidare på principerna bakom länkade listor och hjälper dig att lösa ett bredare spektrum av beräkningsproblem effektivt. Träd och binära sökträd, till exempel, utökar konceptet med länkade listor till en hierarkisk form, vilket gör att varje nod kan kopplas till flera element i datastrukturen.

Om dessa koncept låter ovana för dig, oroa dig inte! Datacamp har en hel kurs om datastrukturer och algoritmer i Python som går igenom dessa koncept mer detaljerat. Du kommer först att lära dig om datastrukturer som stackar, träd, hashtabeller, köer och grafer. Allteftersom du tar dig igenom kursen kommer du att få förståelse för sök- och sorteringsalgoritmer, vilket hjälper dig att bli en mer effektiv programmerare och problemlösare.

Utforska avancerade koncept för länkade listor

Vi har implementerat enkelriktade länkade listor i denna handledning och täckt operationer som insättning, borttagning och traversering.

Du kan ta detta ett steg vidare genom att lära dig implementeringen av dubbellänkade och cirkulära länkade listor. Skip-lists är en annan utvidgning av länkade listor som möjliggör snabbare sökningar genom att underlätta snabbare åtkomst till element.

Att lära sig dessa mer avancerade datastrukturer kommer att ta dina tekniska färdigheter till nästa nivå och dramatiskt förbättra dina programmeringsmöjligheter, och förbereda dig för mer komplexa utmaningar inom områden som data science, mjukvaruutveckling och maskininlärnings­engineering.

Om du vill ha en mer nybörjarvänlig introduktion till programmering innan du tar dig an dessa avancerade ämnen, utforska vår färdighetsväg Python Programming. Den erbjuder en serie kurser som lär dig grunderna i språket.