Verkettete Listen in Python: Tutorial mit Beispielen

Eine verkettete Liste ist eine Datenstruktur, die eine zentrale Rolle bei der Organisation und Verwaltung von Daten spielt. Sie besteht aus einer Reihe von Knoten, die an zufälligen Speicheradressen liegen und so eine effiziente Speichernutzung ermöglichen. Jeder Knoten in einer verketteten Liste enthält zwei Hauptkomponenten: den Datenteil und eine Referenz auf den nächsten Knoten in der Sequenz.

Klingt das auf den ersten Blick kompliziert? Kein Grund zur Sorge!

Wir zerlegen das Thema in seine Grundlagen und erklären, was verkettete Listen sind, warum wir sie verwenden und welche besonderen Vorteile sie bieten.

Warum verkettete Listen?

Verkettete Listen wurden entwickelt, um verschiedene Nachteile beim Speichern von Daten in normalen Listen und Arrays zu umgehen, wie unten beschrieben:

Einfaches Einfügen und Löschen

In Listen erfordern Einfügen oder Löschen an einer anderen Position als am Ende das Verschieben aller nachfolgenden Elemente. Dieser Vorgang hat eine Zeitkomplexität von O(n) und kann die Performance deutlich beeinträchtigen, insbesondere wenn die Liste wächst. Falls du noch nicht genau weißt, wie Listen funktionieren oder implementiert sind, wirf einen Blick in unser Tutorial zu Python-Listen.

Verkettete Listen funktionieren hingegen anders. Sie speichern Elemente an verschiedenen, nicht zusammenhängenden Speicherorten und verbinden sie über Zeiger mit den folgenden Knoten. Dadurch lassen sich Elemente an beliebigen Positionen hinzufügen oder entfernen, indem lediglich die Verknüpfungen angepasst werden, um ein neues Element einzufügen oder ein gelöschtes zu überspringen.

Sobald du eine direkte Referenz auf den Knoten an der Einfüge- oder Löschposition hast, ist der eigentliche Vorgang O(1). Das Auffinden dieser Position erfordert jedoch weiterhin eine O(n)-Traversal. Der O(1)-Vorteil gilt also nur, wenn du bereits einen Zeiger auf den relevanten Knoten hältst (zum Beispiel wenn du am Kopf der Liste arbeitest).

Dynamische Größe

Python-Listen sind dynamische Arrays und bieten damit die Flexibilität, ihre Größe zu verändern.

Allerdings umfasst dieser Prozess mehrere aufwendige Schritte, darunter das Neuallozieren des Arrays in einen größeren Speicherblock. Diese Reallokation ist ineffizient, da Elemente in einen neuen Block kopiert werden müssen und dabei möglicherweise mehr Platz reserviert wird, als zunächst benötigt.

Im Gegensatz dazu können verkettete Listen dynamisch wachsen und schrumpfen, ohne Reallokation oder Größenanpassungen. Dadurch sind sie ideal für Aufgaben, die hohe Flexibilität erfordern.

Speichereffizienz

Listen reservieren den Speicher für alle Elemente in einem zusammenhängenden Block. Wenn eine Liste über ihre Anfangsgröße hinaus wachsen muss, braucht sie einen neuen, größeren, zusammenhängenden Block und kopiert alle Elemente dorthin. Das ist zeitaufwendig und ineffizient, besonders bei großen Listen. Wird die Anfangsgröße hingegen überschätzt, bleibt ungenutzter Speicher unproduktiv.

Verkettete Listen reservieren hingegen für jedes Element separat Speicher. So wird der Speicher besser ausgenutzt, da neuer Speicher jeweils nur dann belegt wird, wenn ein weiteres Element hinzukommt.

Wann solltest du verkettete Listen verwenden?

Verkettete Listen bieten gegenüber normalen Listen und Arrays Vorteile wie dynamische Größe und bessere Speichernutzung, haben aber auch Grenzen. Da für jedes Element ein Zeiger auf den nächsten Knoten gespeichert werden muss, ist der Speicherbedarf pro Element höher. Außerdem erlaubt diese Datenstruktur keinen direkten Zugriff. Um ein Element zu erreichen, muss von Beginn der Liste sequentiell traversiert werden, was zu einer Suchkomplexität von O(n) führt.

Ob du eine verkettete Liste oder ein Array nutzt, hängt vom konkreten Anwendungsfall ab. Besonders sinnvoll sind verkettete Listen, wenn:

• Du häufig viele Elemente einfügst und löschst
• Die Datenmenge unvorhersehbar ist oder sich oft ändert
• Direkter Zugriff auf Elemente nicht erforderlich ist
• Die Daten große Elemente oder Strukturen enthalten

Arten verketteter Listen

Es gibt drei Arten verketteter Listen, die je nach Szenario unterschiedliche Vorteile bieten. Diese Typen sind:

Einfach verkettete Listen

Einfach verkettete Liste

Eine einfach verkettete Liste ist die einfachste Form: Jeder Knoten enthält Daten und eine Referenz auf den nächsten Knoten in der Sequenz. Sie lässt sich nur in eine Richtung durchlaufen – vom Kopf (erster Knoten) bis zum Ende (letzter Knoten).

Ein Knoten in einer einfach verketteten Liste besteht typischerweise aus zwei Teilen:

• Daten: Die eigentlichen Informationen im Knoten.
• Nächster Zeiger: Eine Referenz auf den nächsten Knoten. Beim letzten Knoten ist dieser Zeiger in der Regel auf null gesetzt.

Da diese Datenstruktur nur in eine Richtung durchlaufen werden kann, musst du zum Zugriff auf ein bestimmtes Element (per Wert oder Index) am Kopf beginnen und die Knoten nacheinander prüfen, bis der gewünschte gefunden ist. Das hat eine Zeitkomplexität von O(n) und ist bei sehr großen Listen weniger effizient.

Das Einfügen und Löschen am Anfang einer einfach verketteten Liste ist sehr effizient mit O(1). Einfügen oder Löschen in der Mitte oder am Ende erfordert jedoch das Traversieren bis zu dieser Position und damit O(n).

Aufgrund ihres Aufbaus sind einfach verkettete Listen besonders nützlich, wenn die meisten Operationen am Listenanfang stattfinden.

Doppelt verkettete Listen

Doppelt verkettete Liste

Ein Nachteil einfach verketteter Listen ist, dass man sie nur in eine Richtung durchlaufen kann und nicht zum vorherigen Knoten zurückkehren kann. Das schränkt Operationen ein, die eine Navigation in beide Richtungen erfordern.

Doppelt verkettete Listen lösen dieses Problem durch einen zusätzlichen Zeiger in jedem Knoten, sodass die Liste in beide Richtungen traversiert werden kann. Jeder Knoten enthält drei Elemente: die Daten, einen Zeiger auf den nächsten und einen Zeiger auf den vorherigen Knoten.

Zyklisch verkettete Listen

Zyklisch verkettete Liste

Zyklisch verkettete Listen sind eine Spezialform, bei der der letzte Knoten wieder auf den ersten zeigt und so eine Schleife bildet. Anders als bei einfach oder doppelt verketteten Listen endet die Struktur also nicht, sondern läuft im Kreis.

Diese zyklische Natur macht sie ideal für Szenarien, die kontinuierlich durchlaufen werden, etwa Brettspiele, in denen nach dem letzten wieder der erste Spieler an der Reihe ist, oder in Algorithmen wie Round-Robin-Scheduling.

Zeitkomplexität im Überblick

Praktisch ist ein schneller Vergleich von verketteten Listen mit Python-Listen:

Das Wichtigste in Kürze: Verkettete Listen sind beim Einfügen und Löschen am Kopf klar im Vorteil (O(1)), schneiden bei allem anderen aber schlechter ab. Wenn du nicht häufig Elemente am Anfang deiner Datenstruktur hinzufügst oder entfernst, ist eine normale Python-Liste in der Regel die bessere Wahl.

So erstellst du eine verkettete Liste in Python

Jetzt wissen wir, was verkettete Listen sind, warum wir sie nutzen und welche Varianten es gibt. Als Nächstes implementieren wir sie in Python. Das Notebook zu diesem Tutorial findest du auch in diesem DataLab-Workbook. Wenn du eine Kopie erstellst, kannst du den Code bearbeiten und ausführen — perfekt, falls es lokal zu Problemen kommt!

Einen Knoten initialisieren

Wie wir gelernt haben, ist ein Knoten ein Element der verketteten Liste, das Daten und eine Referenz auf den nächsten Knoten speichert. So definierst du einen Knoten in Python:

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

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

Der obige Code initialisiert einen Knoten mit zwei zentralen Schritten: Dem Attribut „data" wird der Wert zugewiesen, also die eigentlichen Informationen, die der Knoten enthalten soll. Das Attribut „next" steht für die Adresse des nächsten Knotens. Es ist zunächst auf None gesetzt und verweist damit auf keinen weiteren Knoten. Sobald wir weitere Knoten zur Liste hinzufügen, wird dieses Attribut aktualisiert und zeigt auf den jeweils folgenden Knoten.

Eine LinkedList-Klasse erstellen

Als Nächstes legen wir die Klasse für die verkettete Liste an. Sie kapselt alle Operationen zur Verwaltung der Knoten, etwa Einfügen und Entfernen. Wir beginnen mit der Initialisierung:

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

Indem wir self.head auf None setzen, sagen wir aus, dass die Liste anfangs leer ist und es noch keinen Knoten gibt, auf den verwiesen werden könnte. Als Nächstes füllen wir die Liste, indem wir neue Knoten einfügen.

Einen neuen Knoten am Anfang einfügen

Innerhalb der LinkedList-Klasse fügen wir nun eine Methode hinzu, die einen neuen Knoten erstellt und ihn am Anfang der Liste platziert:

    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

Jedes Mal, wenn du diese Methode aufrufst, wird ein neuer Knoten mit den angegebenen Daten erstellt. Dessen Next-Zeiger zeigt auf den aktuellen Kopf der Liste, wodurch der neue Knoten vor den bestehenden einsortiert wird. Abschließend wird der neue Knoten zum Kopf der Liste.

Um besser zu verstehen, wie das Einfügen funktioniert, füllen wir die Liste jetzt mit einer Reihe von Wörtern. Zuerst erstellen wir eine Methode, die die Liste durchläuft und ihren Inhalt ausgibt:

    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

Diese Methode gibt den Inhalt unserer verketteten Liste aus. Jetzt nutzen wir die definierten Methoden, um die Liste mit den Wörtern „the quick brown fox" zu befüllen:

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

Die obigen Zeilen erzeugen folgende Ausgabe:

"the quick brown fox"

Einen neuen Knoten am Ende einfügen

Jetzt erstellen wir in der LinkedList-Klasse eine Methode namens insertAtEnd, die einen neuen Knoten am Ende der Liste anfügt. Ist die Liste leer, wird der neue Knoten zum Kopf. Andernfalls wird er an den aktuellen letzten Knoten angehängt. So funktioniert es:

    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

Die Methode erstellt zunächst einen neuen Knoten. Ist die Liste leer, wird er als Kopf gesetzt. Andernfalls wird die Liste bis zum letzten Knoten traversiert und dessen Zeiger auf den neuen Knoten gesetzt.

Binde diese Methode nun in deine LinkedList-Klasse ein und nutze sie, um ein Wort am Ende hinzuzufügen. Ergänze dafür die main-Funktion wie folgt:

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

Wir rufen hier einfach insertAtEnd auf, um das Wort „jumps" am Ende der Liste auszugeben. Die Ausgabe sollte wie folgt aussehen:

"the quick brown fox jumps"

Einen Knoten am Anfang löschen

Das Löschen des ersten Knotens ist einfach: Der Kopf der Liste wird auf den zweiten Knoten gesetzt. So gehört der erste Knoten nicht länger zur Liste. Füge dazu folgende Methode in die LinkedList-Klasse ein:

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

Einen Knoten am Ende löschen

Um den letzten Knoten zu löschen, traversieren wir bis zum vorletzten Knoten und setzen dessen Next-Zeiger auf None. Dadurch gehört der bisher letzte Knoten nicht länger zur Liste. Kopiere die folgende Methode in deine LinkedList-Klasse:

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

Die Methode prüft zunächst, ob die Liste leer ist, und gibt in dem Fall eine Meldung zurück. Enthält die Liste nur einen Knoten, wird dieser entfernt. Bei mehreren Knoten wird der vorletzte Knoten ermittelt und dessen Referenz auf None gesetzt.

Aktualisieren wir nun die main-Funktion, um Elemente am Anfang und am Ende zu löschen:

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

Der Code gibt die Liste vor und nach dem Löschen aus und zeigt so, wie Einfüge- und Löschoperationen in verketteten Listen funktionieren. Du solltest folgende Ausgabe sehen:

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

In der verketteten Liste nach einem Wert suchen

Zum Schluss schauen wir uns das Auffinden eines bestimmten Werts in der verketteten Liste an. Die Methode startet am Kopf und iteriert durch jeden Knoten, bis die Knotendaten dem Suchwert entsprechen. So könnte die Implementierung aussehen:

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" 

Um in unserer Liste nach bestimmten Wörtern zu suchen, erweitern wir die main-Funktion um die eben erstellte Suchmethode:

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

Die Ausgabe sieht dann so aus:

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

Das Wort „quick" wurde erfolgreich gefunden, da es an erster Position in der Liste steht. „lazy" ist nicht Teil der Liste und wurde daher nicht gefunden.

Fazit

Glückwunsch, wenn du bis hierher gelesen hast! Du hast jetzt ein solides Verständnis der Grundlagen verketteter Listen: Aufbau, Typen, Einfügen und Löschen von Elementen sowie Traversierung.

Damit ist die Reise noch lange nicht zu Ende. Verkettete Listen sind nur der Einstieg in die Welt der Datenstrukturen und Algorithmen. Hier sind mögliche nächste Schritte, um dein Wissen zu vertiefen:

Starte ein eigenes Projekt

Setze verkettete Listen praktisch ein, indem du sie in ein Coding- oder Data-Science-Projekt integrierst. Sie kommen unter anderem in Dateisystemen, beim Aufbau von Hashtabellen, in GPS-Navigationssystemen und Brettspielen zum Einsatz. Für den Einstieg in eigene Projekte schau dir unsere kostenlosen geführten Data-Science-Projekte an, in denen du lernst, reale Probleme in Python, R und SQL zu lösen.

Lerne mehr über Datenstrukturen und Algorithmen

Auf verkettete Listen bauen weitere Datenstrukturen wie Bäume, Stacks und Queues auf. Mit ihnen löst du eine größere Bandbreite an Problemen effizient. Bäume und binäre Suchbäume erweitern das Konzept verketteter Listen beispielsweise zu einer Hierarchie, in der jeder Knoten mit mehreren Elementen verknüpft sein kann.

Klingen diese Konzepte noch neu für dich? Kein Problem! Datacamp bietet einen kompletten Kurs zu Datenstrukturen und Algorithmen in Python, der diese Themen im Detail behandelt. Du lernst zunächst Strukturen wie Stacks, Bäume, Hashtabellen, Queues und Graphen kennen. Danach tauchst du in Such- und Sortieralgorithmen ein und wirst so zu einer effizienteren Programmiererin oder einem effizienteren Programmierer.

Fortgeschrittene Konzepte verketteter Listen

In diesem Tutorial haben wir einfach verkettete Listen implementiert und Operationen wie Einfügen, Löschen und Traversieren abgedeckt.

Du kannst noch einen Schritt weitergehen und die Implementierung doppelt und zyklisch verketteter Listen lernen. Skip-Listen sind eine weitere Erweiterung, die durch zusätzliche Ebenen schnellere Suchen ermöglichen.

Mit diesen fortgeschrittenen Strukturen bringst du deine technischen Kompetenzen auf das nächste Level und verbesserst deine Programmierfähigkeiten deutlich — ideal als Vorbereitung auf komplexere Herausforderungen in Data Science, Softwareentwicklung und Machine Learning Engineering.

Wenn du vor den fortgeschrittenen Themen eine einsteigerfreundliche Einführung ins Programmieren möchtest, schau dir unseren Python Programming-Lernpfad an. Er enthält eine Kursreihe, die dir die Grundlagen der Sprache vermittelt.