Gelinkte lijsten in Python: tutorial met voorbeelden

Een gelinkte lijst is een datastructuur die een cruciale rol speelt bij het organiseren en beheren van data. Ze bevat een reeks knooppunten (nodes) die op willekeurige locaties in het geheugen zijn opgeslagen, wat efficiënter geheugenbeheer mogelijk maakt. Elk knooppunt in een gelinkte lijst bevat twee hoofdonderdelen: het gegevensgedeelte en een verwijzing naar het volgende knooppunt in de reeks.

Klinkt dit in eerste instantie ingewikkeld? Geen zorgen!

We brengen het terug tot de basis om uit te leggen wat gelinkte lijsten zijn, waarom we ze gebruiken en welke unieke voordelen ze bieden.

Waarom gelinkte lijsten?

Gelinkte lijsten zijn ontwikkeld om verschillende nadelen van het opslaan van data in gewone lijsten en arrays te omzeilen, zoals hieronder beschreven:

Gemak van invoegen en verwijderen

In lijsten vereist het invoegen of verwijderen van een element op een andere positie dan het einde dat alle daaropvolgende items opschuiven naar een andere positie. Dit proces heeft een tijdscomplexiteit van O(n) en kan de prestaties aanzienlijk verminderen, zeker naarmate de lijst groter wordt. Als je nog niet bekend bent met hoe lijsten werken of hoe ze zijn geïmplementeerd, kun je onze tutorial over Python-lijsten lezen.

Gelinkte lijsten werken echter anders. Ze slaan elementen op in verschillende, niet-aaneengesloten geheugenlocaties en verbinden ze via pointers naar opvolgende knooppunten. Dankzij deze structuur kunnen gelinkte lijsten op elke positie elementen toevoegen of verwijderen door simpelweg de links aan te passen om een nieuw element op te nemen of het verwijderde element over te slaan.

Zodra je een directe verwijzing hebt naar het knooppunt op het invoeg- of verwijderpunt, is de bewerking zelf O(1). Het vinden van die positie vereist nog steeds O(n) traverseren, dus het O(1)-voordeel geldt alleen wanneer je al een pointer naar het relevante knooppunt hebt (zoals wanneer je aan het begin van de lijst werkt).

Dynamische grootte

Python-lijsten zijn dynamische arrays, wat betekent dat ze de flexibiliteit bieden om van grootte te veranderen.

Dit proces omvat echter een reeks complexe operaties, waaronder het heralloceren van de array naar een nieuw, groter geheugenblok. Zo’n herallocatie is inefficiënt omdat elementen naar een nieuw blok worden gekopieerd, waarbij mogelijk meer ruimte wordt toegewezen dan direct nodig is.

Gelinkte lijsten daarentegen kunnen dynamisch groeien en krimpen zonder herallocatie of resizing. Dit maakt ze een betere keuze voor taken die veel flexibiliteit vereisen.

Geheugenefficiëntie

Lijsten reserveren geheugen voor al hun elementen in één aaneengesloten blok. Als een lijst groter moet worden dan de initiële grootte, moet er een nieuw, groter aaneengesloten geheugenblok worden toegewezen en moeten alle bestaande elementen naar dit nieuwe blok worden gekopieerd. Dit is tijdrovend en inefficiënt, vooral voor grote lijsten. Aan de andere kant, als de initiële grootte te ruim is ingeschat, gaat ongebruikt geheugen verloren.

Gelinkte lijsten reserveren daarentegen voor elk element apart geheugen. Deze structuur leidt tot beter geheugengebruik, omdat geheugen voor nieuwe elementen kan worden toegewezen wanneer ze worden toegevoegd.

Wanneer gebruik je gelinkte lijsten?

Hoewel gelinkte lijsten bepaalde voordelen bieden ten opzichte van gewone lijsten en arrays, zoals dynamische grootte en geheugenefficiëntie, hebben ze ook hun beperkingen. Omdat voor elk element pointers moeten worden opgeslagen om naar het volgende knooppunt te verwijzen, is het geheugengebruik per element hoger bij gelinkte lijsten. Ook staat deze datastructuur geen directe toegang tot data toe. Het opvragen van een element vereist sequentieel doorlopen vanaf het begin van de lijst, wat resulteert in een zoektijdscomplexiteit van O(n).

De keuze tussen een gelinkte lijst of een array hangt af van de specifieke behoeften van de toepassing. Gelinkte lijsten zijn het meest nuttig wanneer:

• Je vaak veel elementen moet invoegen en verwijderen
• De datasize onvoorspelbaar is of waarschijnlijk vaak verandert
• Directe toegang tot elementen geen vereiste is
• De dataset grote elementen of structuren bevat

Typen gelinkte lijsten

Er zijn drie typen gelinkte lijsten, elk met eigen voordelen voor verschillende scenario’s. Deze typen zijn:

Singly-linked lists

Enkelvoudig gelinkte lijst

Een enkelvoudig gelinkte lijst is het eenvoudigste type gelinkte lijst, waarbij elk knooppunt data bevat en een verwijzing naar het volgende knooppunt in de reeks. Je kunt ze slechts in één richting doorlopen: van de head (het eerste knooppunt) naar de tail (het laatste knooppunt).

Elk knooppunt in een enkelvoudig gelinkte lijst bestaat doorgaans uit twee delen:

• Data: De eigenlijke informatie die in het knooppunt is opgeslagen.
• Next-pointer: Een verwijzing naar het volgende knooppunt. De next-pointer van het laatste knooppunt is meestal ingesteld op null.

Omdat deze datastructuren slechts in één richting kunnen worden doorlopen, vereist het opvragen van een specifiek element op waarde of index dat je bij de head begint en sequentieel door de knooppunten gaat totdat het gewenste knooppunt is gevonden. Deze operatie heeft een tijdscomplexiteit van O(n), wat minder efficiënt is voor grote lijsten.

Het invoegen en verwijderen van een knooppunt aan het begin van een enkelvoudig gelinkte lijst is zeer efficiënt met een tijdscomplexiteit van O(1). Invoegen en verwijderen in het midden of aan het einde vereist echter het doorlopen van de lijst tot dat punt, wat leidt tot een tijdscomplexiteit van O(n).

Door hun ontwerp zijn enkelvoudig gelinkte lijsten nuttig bij bewerkingen die plaatsvinden aan het begin van de lijst.

Doubly-linked lists

Dubbel gelinkte lijst

Een nadeel van enkelvoudig gelinkte lijsten is dat je ze slechts in één richting kunt doorlopen en niet kunt teruggaan naar het vorige knooppunt indien nodig. Deze beperking beperkt de mogelijkheid om bewerkingen uit te voeren die bidirectionele navigatie vereisen.

Dubbel gelinkte lijsten lossen dit probleem op door een extra pointer in elk knooppunt op te nemen, zodat de lijst in beide richtingen kan worden doorlopen. Elk knooppunt in een dubbel gelinkte lijst bevat drie elementen: de data, een pointer naar het volgende knooppunt en een pointer naar het vorige knooppunt.

Circulaire gelinkte lijsten

Circulair gelinkte lijst

Circulaire gelinkte lijsten zijn een gespecialiseerd type gelinkte lijst waarbij het laatste knooppunt terugverwijst naar het eerste knooppunt, waardoor een cirkelvormige structuur ontstaat. Dit betekent dat, in tegenstelling tot de enkelvoudig en dubbel gelinkte lijsten die we tot nu toe hebben gezien, de circulair gelinkte lijst niet eindigt; in plaats daarvan loopt hij rond.

Door hun cyclische karakter zijn circulaire gelinkte lijsten ideaal voor scenario’s die continu moeten worden doorlopen, zoals bordspellen die teruggaan van de laatste speler naar de eerste, of in algoritmen zoals round-robin scheduling.

Samenvatting tijdscomplexiteit

Het is handig om in één oogopslag te zien hoe gelinkte lijsten zich verhouden tot Python-lijsten:

De kernboodschap: gelinkte lijsten winnen bij invoegen en verwijderen aan de kop (O(1)), maar verliezen op vrijwel al het andere. Als je niet vaak elementen toevoegt of verwijdert aan het begin van je datastructuur, is een gewone Python-lijst waarschijnlijk de betere keuze.

Hoe maak je een gelinkte lijst in Python

Nu we begrijpen wat gelinkte lijsten zijn, waarom we ze gebruiken en welke varianten er zijn, gaan we deze datastructuren in Python implementeren. De notebook voor deze tutorial is ook beschikbaar in deze DataLab-werkmap; als je een kopie maakt, kun je de code bewerken en uitvoeren. Dit is een prima optie als je problemen ondervindt bij het zelf draaien van de code!

Een knooppunt initialiseren

Zoals we eerder leerden, is een knooppunt een element in de gelinkte lijst dat data en een verwijzing naar het volgende knooppunt in de reeks opslaat. Zo definieer je een knooppunt in Python:

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

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

De bovenstaande code initialiseert een knooppunt door twee primaire acties uit te voeren: de “data”-attribuut van het knooppunt krijgt een waarde die de eigenlijke informatie vertegenwoordigt die het knooppunt moet bevatten. Het “next”-attribuut vertegenwoordigt het adres van het volgende knooppunt. Dit staat nu op None, wat betekent dat het niet aan een ander knooppunt in de lijst is gekoppeld. Terwijl we nieuwe knooppunten aan de gelinkte lijst toevoegen, wordt dit attribuut bijgewerkt om naar het volgende knooppunt te wijzen.

Een klasse voor de gelinkte lijst maken

Vervolgens moeten we de klasse voor de gelinkte lijst maken. Deze zal alle bewerkingen voor het beheren van de knooppunten omvatten, zoals invoegen en verwijderen. We beginnen met het initialiseren van de gelinkte lijst:

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

Door self.head op None te zetten, geven we aan dat de gelinkte lijst in eerste instantie leeg is en dat er geen knooppunten zijn waarnaar kan worden verwezen. We gaan de lijst nu vullen door nieuwe knooppunten in te voegen.

Een nieuw knooppunt aan het begin van een gelinkte lijst invoegen

Binnen de klasse LinkedList voegen we een methode toe om een nieuw knooppunt te maken en aan het begin van de lijst te plaatsen:

    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

Elke keer dat je de bovenstaande methode aanroept, wordt een nieuw knooppunt gemaakt met de door jou opgegeven data. De next-pointer van dit nieuwe knooppunt wordt ingesteld op de huidige head van de lijst, waardoor dit knooppunt vóór de bestaande knooppunten komt te staan. Tot slot wordt het nieuw aangemaakte knooppunt de head van de lijst.

We gaan deze gelinkte lijst nu vullen met een reeks woorden om beter te begrijpen hoe de invoegbewerking werkt. Om dit te doen, maken we eerst een methode die is ontworpen om de lijst te doorlopen en de inhoud te printen:

    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

De bovenstaande methode print de inhoud van onze gelinkte lijst. Laten we nu de methoden die we hebben gedefinieerd gebruiken om onze lijst te vullen met de woorden: “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()

De bovenstaande code zou de volgende output moeten geven:

"the quick brown fox"

Een nieuw knooppunt aan het einde van een gelinkte lijst invoegen

We maken nu een methode genaamd insertAtEnd binnen de klasse LinkedList om een nieuw knooppunt aan het einde van de lijst te maken. Als de lijst leeg is, wordt het nieuwe knooppunt de head van de lijst. Anders wordt het toegevoegd aan het huidige laatste knooppunt in de lijst. Laten we kijken hoe dit in de praktijk werkt:

    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

De bovenstaande methode begint met het maken van een nieuw knooppunt. Vervolgens controleert ze of de lijst leeg is; zo ja, dan wordt het nieuwe knooppunt toegewezen als head van die lijst. Anders doorloopt ze de lijst om het laatste knooppunt te vinden en stelt de pointer van dit knooppunt in op het nieuwe knooppunt.

We moeten deze methode nu opnemen in onze klasse LinkedList en gebruiken om een woord aan het einde van onze lijst toe te voegen. Pas hiervoor je main-functie als volgt aan:

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()

Merk op dat we simpelweg de methode insertAtEnd hebben aangeroepen om het woord “jumps” aan het einde van de lijst te printen. De bovenstaande code zou de volgende output moeten geven:

"the quick brown fox jumps"

Een knooppunt aan het begin van een gelinkte lijst verwijderen

Het verwijderen van het eerste knooppunt van een gelinkte lijst is eenvoudig, omdat het simpelweg inhoudt dat je de head van deze lijst laat wijzen naar het tweede knooppunt. Zo maakt het eerste knooppunt geen deel meer uit van de lijst. Voeg hiervoor de volgende methode toe aan de klasse 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

Een knooppunt aan het einde van een gelinkte lijst verwijderen

Om het laatste knooppunt van een gelinkte lijst te verwijderen, moeten we de lijst doorlopen om het op één na laatste knooppunt te vinden en de next-pointer daarvan op None zetten. Op die manier maakt het laatste knooppunt geen deel meer uit van de lijst. Kopieer en plak de volgende methode in je klasse LinkedList om dit te doen:

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

De bovenstaande methode controleert eerst of de gelinkte lijst leeg is en geeft in dat geval een bericht terug. Als de lijst anders één knooppunt bevat, wordt dat knooppunt verwijderd. Voor lijsten met meerdere knooppunten lokaliseert de methode het op één na laatste knooppunt en wordt de verwijzing naar zijn volgende knooppunt bijgewerkt naar None.

Laten we nu de main-functie bijwerken om elementen aan het begin en einde van de gelinkte lijst te verwijderen:

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()

De bovenstaande code print de lijst vóór en na het verwijderen, zodat je ziet hoe de invoeg- en verwijderbewerkingen werken in gelinkte lijsten. Je zou na het uitvoeren van deze code de volgende output moeten zien:

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

Zoeken naar een specifieke waarde in de gelinkte lijst

De laatste bewerking die we in dit hoofdstuk leren, is het ophalen van een specifieke waarde in de gelinkte lijst. Hiervoor moet de methode beginnen bij de head van de lijst en door elk knooppunt itereren, waarbij wordt gecontroleerd of de data van het knooppunt overeenkomt met de gezochte waarde. Hier is een praktische implementatie van deze operatie:

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" 

Om specifieke waarden te vinden in de gelinkte lijst die we hebben gemaakt, werk je je main-functie bij zodat deze de zojuist gemaakte zoekmethode bevat:

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

De bovenstaande code geeft de volgende output:

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

Het woord “quick” is met succes gevonden in de gelinkte lijst, omdat het op de eerste positie van de lijst staat. Het woord “lazy” maakt echter geen deel uit van de lijst en is daarom niet gevonden.

Tot slot

Als je tot hier bent gekomen: gefeliciteerd! Je hebt nu een goed begrip van de basisprincipes van gelinkte lijsten, waaronder hun structuur, typen, hoe je elementen toevoegt en verwijdert, en hoe je ze doorloopt.

Maar hier stopt het niet. Gelinkte lijsten zijn slechts het begin van de wereld van datastructuren en algoritmen. Hier zijn enkele mogelijke vervolgstappen om je begrip te verdiepen:

Maak je eigen project

Duik in de praktische toepassingen van gelinkte lijsten door ze te integreren in een coding- of datascienceproject. Gelinkte lijsten worden gebruikt om bestandssystemen te ontwikkelen, hashtabellen te bouwen en zelfs GPS-navigatiesystemen en bordspellen te maken. Om met je eigen projecten te beginnen, bekijk onze gratis begeleide datascienceprojecten die je leren hoe je echte problemen oplost in Python, R en SQL.

Leer over datastructuren en algoritmen

Andere datastructuren leren, zoals trees, stacks en queues, is een logische volgende stap na gelinkte lijsten. Deze structuren bouwen voort op de principes van gelinkte lijsten en helpen je een breder scala aan computationele problemen efficiënt op te lossen. Trees en binaire zoekbomen breiden bijvoorbeeld het concept van gelinkte lijsten uit naar een hiërarchische vorm, waardoor elk knooppunt met meerdere elementen in de datastructuur kan verbinden.

Klinken deze concepten je nog onbekend? Geen zorgen! Datacamp heeft een volledige cursus over datastructuren en algoritmen in Python die je stap voor stap door deze onderwerpen loodst. Je leert eerst over datastructuren zoals stacks, trees, hashtabellen, queues en grafen. Terwijl je vordert in de cursus, krijg je inzicht in zoek- en sorteeralgoritmen, waardoor je een efficiëntere programmeur en probleemoplosser wordt.

Verdiep je in geavanceerde concepten van gelinkte lijsten

In deze tutorial hebben we enkelvoudig gelinkte lijsten geïmplementeerd en operaties behandeld zoals invoegen, verwijderen en traverseren.

Je kunt deze kennis uitbreiden door de implementatie van dubbel en circulair gelinkte lijsten te leren. Skip lists zijn een andere uitbreiding van gelinkte lijsten die snellere zoekoperaties mogelijk maken door sneller toegang te faciliteren.

Kennis van deze geavanceerde datastructuren tilt je technische vaardigheden naar een hoger niveau en verbetert je programmeercapaciteiten aanzienlijk, zodat je beter bent voorbereid op complexere uitdagingen in vakgebieden als data science, softwareontwikkeling en machine learning engineering.

Wil je liever eerst een beginnersvriendelijke introductie tot programmeren voordat je deze geavanceerde onderwerpen aanpakt? Bekijk dan onze Python Programming-skill track. Die biedt een reeks cursussen die je de basis van de taal leren.