Förstå implementering av länkade listor i Python

Datastrukturer utgör en fundamental del inom programmering. De ger oss verktyg för att organisera information på ett sätt som möjliggör effektiv användning.

I denna genomgång kommer vi att undersöka den enkellänkade listan och den dubbellänkade listan.

En länkad lista är en linjär struktur för datalagring. Till skillnad från arrayer, lagrar den inte data i sammanhängande minnesutrymmen. Varje element i en länkad lista kallas en nod, och dessa noder är sammankopplade med hjälp av referenser, ofta kallade pekare. Den första noden i listan benämns som huvud.

Länkade listor har dynamisk storlek, vilket innebär att vi kan inkludera så många noder vi behöver, förutsatt att det finns tillgängligt minne.

Länkade listor finns i två huvudvarianter. Låt oss detaljerat gå igenom dem en efter en.

#1. Enkelt Länkad Lista

En enkellänkad lista karakteriseras av att varje nod har en enda pekare som refererar till nästa nod i listan. För varje nod i en enkellänkad lista behöver vi lagra både datan och en pekare.

Den sista noden i en enkellänkad lista innehåller en null-pekare som ”nästa”, vilket markerar slutet på listan.

Nedan ser du en visualisering av hur en enkellänkad lista är strukturerad.

Med denna grundläggande förståelse, ska vi nu undersöka hur vi implementerar en enkellänkad lista i Python.

Implementering av Enkellänkad Lista

1. Det första steget handlar om att konstruera en nod för listan.

Hur går vi tillväga?

I Python kan vi enkelt skapa en nod med hjälp av en klass. Klassen kommer att hålla nodens data samt en pekare till nästa nod.

Här är koden för en nod.

class Node:
    def __init__(self, data):
        ## data för noden
        self.data = data
        ## pekare till nästa nod
        self.next = None

Ovanstående klass gör det möjligt att skapa noder med valfri datatyp. Vi kommer att se ett exempel strax.

Med noden definierad, behöver vi nu en länkade lista med flera noder. Vi skapar en ny klass för detta ändamål.

2. Skapa en klass vid namn LinkedList. Huvudet börjar som None. Koden ser ut så här:

class LinkedList:
    def __init__(self):
        ## initierar huvudet till None
        self.head = None

3. Nu har vi klasserna Node och LinkedList. Hur infogar vi en ny nod i listan? Ett enkelt sätt är genom att använda en metod i klassen LinkedList. Låt oss skapa en sådan metod.

Följande steg behövs för att infoga en ny nod i listan:

Här är stegen:

  • Kontrollera om huvudet är tomt.
  • Om huvudet är tomt, tilldela den nya noden till huvudet.
  • Om huvudet inte är tomt, hitta den sista noden i listan.
  • Tilldela den nya noden till den sista nodens nästa-pekare.

Låt oss se hur koden för insättning av en ny nod ser ut:

class LinkedList:
    ####
    def insert(self, new_node):
        ## kolla om huvudet är tomt eller ej
        if self.head:
            ## finner den sista noden
            last_node = self.head
            while last_node.next != None:
                last_node = last_node.next
            ## tilldelar den nya noden till den sista nodens next-pekare
            last_node.next = new_node
        else:
            ## huvudet är tomt
            ## tilldelar noden till huvudet
            self.head = new_node

Bra! Nu har vi en metod för att lägga till nya noder. Men hur kommer vi åt datan i noderna?

För att få tillgång till datan i listan, måste vi iterera genom listan med hjälp av next-pekare, på samma sätt som när vi söker den sista noden. Vi skapar en metod i klassen LinkedList som skriver ut alla noders data.

4. Här är stegen för att skriva ut all noddata i listan:

  • Initiera en temporär variabel med huvud.
  • Skapa en loop som fortsätter tills vi når slutet av listan.
    • Skriv ut nodens data.
    • Flytta till nästa nod.

Här är koden:

class LinkedList:
    ####
    def display(self):
        ## variabel för iteration
        temp_node = self.head
        ## itererar tills vi når slutet av listan
        while temp_node != None:
            ## skriver ut noddata
            print(temp_node.data, end='->')
            ## går till nästa nod
            temp_node = temp_node.next
        print('Null')

Pust! Vi har skapat en länkad lista med alla nödvändiga metoder. Nu testar vi den genom att instansiera den med lite data.

Vi kan skapa noder med anrop som `Node(1)`. Här är hela koden för implementeringen av den länkade listan, med exempel:

class Node:
    def __init__(self, data):
        ## nodens data
        self.data = data
        ## pekare till nästa nod
        self.next = None

class LinkedList:
    def __init__(self):
        ## initierar huvudet med None
        self.head = None

    def insert(self, new_node):
        ## kolla om huvudet är tomt
        if self.head:
            ## hämta den sista noden
            last_node = self.head
            while last_node.next != None:
                last_node = last_node.next
            ## tilldela den nya noden till den sista nodens next-pekare
            last_node.next = new_node
        else:
            ## huvudet är tomt
            ## tilldela noden till huvudet
            self.head = new_node

    def display(self):
        ## variabel för iteration
        temp_node = self.head
        ## iterera tills vi når slutet av listan
        while temp_node != None:
            ## skriv ut nodens data
            print(temp_node.data, end='->')
            ## flytta till nästa nod
            temp_node = temp_node.next
        print('Null')

if __name__ == '__main__':
    ## skapar en instans av den länkade listan
    linked_list = LinkedList()
    ## lägger till data i listan
    linked_list.insert(Node(1))
    linked_list.insert(Node(2))
    linked_list.insert(Node(3))
    linked_list.insert(Node(4))
    linked_list.insert(Node(5))
    linked_list.insert(Node(6))
    linked_list.insert(Node(7))

    ## skriver ut den länkade listan
    linked_list.display()

Kör koden ovan för att få följande resultat:

1->2->3->4->5->6->7->Null

Det var allt om enkellänkade listor! Nu vet du hur man implementerar en sådan. Kunskapen härifrån hjälper dig också att implementera en dubbellänkad lista. Låt oss gå vidare till nästa del av handledningen.

#2. Dubbelt Länkad Lista

En dubbellänkad lista utmärks av att varje nod har två pekare, en som pekar bakåt till föregående nod och en som pekar framåt till nästa nod. För varje nod i en dubbellänkad lista lagrar vi datan samt två pekare.

Den första nodens ”föregående” pekare är null och den sista nodens ”nästa” pekare är också null, vilket markerar listans ändar.

Nedan kan du se en illustration av strukturen.

Implementeringen av en dubbellänkad lista är snarlik den enkellänkade listan. Istället för att gå igenom allting på nytt, uppmuntrar vi dig att studera koden och bekanta dig med den. Nu sätter vi igång!

Implementering av Dubbellänkad Lista

1. Skapa en nod för den dubbellänkade listan med pekare för föregående nod, data och pekare för nästa nod.

class Node:
        def __init__(self, data):
            ## pekare till föregående nod
            self.prev = None
            ## nodens data
            self.data = data
            ## pekare till nästa nod
            self.next = None

2. Klass för dubbellänkad lista:

class LinkedList:
        def __init__(self):
            ## initierar huvudet till None
            self.head = None

3. Metod för att lägga till en ny nod till den dubbellänkade listan.

class LinkedList:
        ####
        def insert(self, new_node):
            ## kolla om huvudet är tomt
            if self.head:
                ## hämta den sista noden
                last_node = self.head
                while last_node.next != None:
                    last_node = last_node.next
                ## tilldela den sista noden till den nya nodens prev-pekare
                new_node.prev = last_node
                ## tilldela den nya noden till den sista nodens next-pekare
                last_node.next = new_node

4. Metod för att visa data i den dubbellänkade listan:

class LinkedList:
        ####
        def display(self):
            ## skriver ut datan i normal ordning
            print("Normal Ordning: ", end='')
            temp_node = self.head
            while temp_node != None:
                print(temp_node.data, end=' ')
                temp_node = temp_node.next
            print()
            ## skriver ut datan i omvänd ordning med hjälp av previous-pekaren
            print("Omvänd Ordning: ", end='')
            ## hämta den sista noden
            last_node = self.head
            while last_node.next != None:
                last_node = last_node.next
            temp_node = last_node
            while temp_node != None:
                print(temp_node.data, end=' ')
                temp_node = temp_node.prev
            print()

Här har du koden för den dubbellänkade listan. Det saknas dock kod för hur man använder denna klass. Det lämnar vi som en övning till dig! Använd klassen på liknande sätt som i exemplet med den enkellänkade listan. Lycka till! 🙂

Slutsats

Det finns många problem som bygger på länkade listor. Det är viktigt att ha koll på de grundläggande implementationerna, som du har lärt dig i denna genomgång. Vi hoppas att du har haft en givande stund med denna introduktion till länkade listor.

Lycka till med kodningen! 🙂