Python Linked Lists: Tutorial mit Beispielen

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

Klingt das auf den ersten Blick kompliziert? Kein Stress!

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

Warum Linked Lists?

Linked Lists 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 erfordert das Einfügen oder Löschen eines Elements an einer anderen Position als am Ende, dass alle nachfolgenden Elemente verschoben werden. 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 vertraut damit bist, wie Listen funktionieren oder implementiert sind, lies unser Tutorial zu Python-Listen.

Linked Lists funktionieren hingegen anders. Sie speichern Elemente an verschiedenen, nicht zusammenhängenden Speicherorten und verknüpfen sie über Zeiger mit den nachfolgenden Knoten. Dadurch können Linked Lists Elemente an jeder Position 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 die Operation selbst O(1). Die Suche nach dieser Position erfordert jedoch weiterhin eine Traversierung in O(n). 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, das heißt, ihre Größe lässt sich flexibel anpassen.

Allerdings umfasst dieser Prozess mehrere aufwendige Schritte, darunter die Neuallokation des Arrays in einen größeren Speicherblock. Diese Neuallokation ist ineffizient, da die Elemente kopiert werden müssen und unter Umständen mehr Platz reserviert wird, als aktuell nötig ist.

Linked Lists hingegen können dynamisch wachsen und schrumpfen, ohne Neuallokation oder Größenänderung. Das macht sie zur besseren Wahl für Aufgaben, die hohe Flexibilität erfordern.

Speichereffizienz

Listen reservieren für alle Elemente einen zusammenhängenden Speicherblock. Wenn eine Liste über ihre anfängliche Größe hinaus wachsen muss, benötigt sie einen neuen, größeren zusammenhängenden Block und kopiert alle existierenden Elemente dorthin. Das ist zeitaufwendig und ineffizient, insbesondere bei großen Listen. Wird die Anfangsgröße überschätzt, bleibt ungenutzter Speicher ungenutzt.

Linked Lists reservieren dagegen für jedes Element separat Speicher. So wird der Speicher besser genutzt, da Platz für neue Elemente erst beim Hinzufügen belegt wird.

Wann solltest du Linked Lists einsetzen?

Obwohl Linked Lists Vorteile gegenüber regulären Listen und Arrays bieten, wie dynamische Größe und Speichereffizienz, haben sie auch Einschränkungen. Da für jedes Element ein Zeiger auf den nächsten Knoten gespeichert werden muss, ist der Speicherverbrauch pro Element höher. Außerdem erlaubt diese Datenstruktur keinen Direktzugriff auf Elemente. Das Zugreifen auf ein Element erfordert eine sequentielle Traversierung ab dem Listenanfang, was eine Suchzeitkomplexität von O(n) bedeutet.

Die Entscheidung zwischen Linked List und Array hängt vom konkreten Einsatzzweck ab. Linked Lists sind besonders nützlich, wenn:

• Du häufig viele Elemente einfügen und löschen musst
• Die Datenmenge unvorhersehbar ist oder sich oft ändert
• Direkter Zugriff auf Elemente nicht erforderlich ist
• Der Datensatz große Elemente oder Strukturen enthält

Arten von Linked Lists

Es gibt drei Arten von Linked Lists, die jeweils in unterschiedlichen Szenarien Vorteile bieten:

Einfach verkettete Listen (Singly-linked lists)

Singly-linked list

Eine einfach verkettete Liste ist der simpelste Typ: Jeder Knoten enthält Daten und einen Verweis auf den nächsten Knoten. Sie lässt sich nur in eine Richtung durchlaufen – vom Kopf (erstes Element) bis zum Ende (letztes Element).

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

• Daten: Die tatsächlich im Knoten gespeicherten Informationen.
• Nächster Zeiger: Ein Verweis auf den nächsten Knoten. Beim letzten Knoten ist dieser Zeiger in der Regel auf null gesetzt.

Da diese Struktur nur in eine Richtung traversiert werden kann, erfordert der Zugriff auf ein bestimmtes Element (per Wert oder Index) das Starten am Kopf und das sequentielle Durchlaufen bis zum gewünschten Knoten. Das hat eine Zeitkomplexität von O(n) und ist bei 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 allerdings eine Traversierung bis zu dieser Position und ist daher O(n).

Durch dieses Design eignen sich einfach verkettete Listen besonders für Operationen am Listenanfang.

Doppelt verkettete Listen (Doubly-linked lists)

Doubly-linked list

Ein Nachteil einfach verketteter Listen ist, dass sie nur in eine Richtung durchlaufen werden können. Ein Zurückspringen zum vorherigen Knoten ist nicht möglich. Das schränkt Operationen ein, die eine Navigation in beide Richtungen benötigen.

Doppelt verkettete Listen beheben dies, indem jeder Knoten einen zusätzlichen Zeiger enthält. So lässt sich die Liste in beide Richtungen traversieren. Jeder Knoten enthält drei Elemente: die Daten, einen Zeiger auf den nächsten und einen Zeiger auf den vorherigen Knoten.

Zirkuläre Linked Lists (Circular linked lists)

Circular linked list

Zirkuläre Linked Lists sind eine spezielle Form, bei der der letzte Knoten auf den ersten zeigt und so eine Schleife bildet. Anders als bei einfach und doppelt verketteten Listen endet die Liste also nicht, sondern läuft im Kreis.

Diese zyklische Eigenschaft eignet sich ideal für Szenarien, die kontinuierlich durchlaufen werden, etwa Brettspiele, die vom letzten wieder zum ersten Spieler springen, oder in der Informatik für Algorithmen wie Round-Robin-Scheduling.

Zusammenfassung der Zeitkomplexität

Praktisch ist ein schneller Vergleich mit Python-Listen:

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

So erstellst du eine Linked List in Python

Jetzt, da wir wissen, was Linked Lists sind, warum wir sie nutzen und welche Varianten es gibt, 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. Das ist ideal, falls du beim lokalen Ausführen auf Probleme stößt!

Einen Knoten initialisieren

Wie wir gelernt haben, ist ein Knoten ein Element der Linked List, das Daten und einen Verweis 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 und führt dabei zwei Hauptaktionen aus: Das Attribut „data“ des Knotens erhält einen Wert, der die eigentlichen Informationen repräsentiert. Das Attribut „next“ steht für die Adresse des nächsten Knotens. Es ist zunächst auf None gesetzt, was bedeutet, dass aktuell keine Verknüpfung zu einem weiteren Knoten besteht. Sobald wir neue Knoten zur Linked List hinzufügen, wird dieses Attribut aktualisiert und auf den nachfolgenden Knoten gesetzt.

Eine Linked-List-Klasse erstellen

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

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

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

Einen neuen Knoten am Anfang einer Linked List einfügen

Innerhalb der LinkedList-Klasse fügen wir nun eine Methode hinzu, die einen neuen Knoten erzeugt und an den Anfang der Liste stellt:

    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 erzeugt. Der Next-Zeiger dieses neuen Knotens wird auf den aktuellen Kopf der Liste gesetzt, wodurch der Knoten vor den bisherigen Knoten einsortiert wird. Abschließend wird der neue Knoten zum Kopf der Liste.

Um das Einfügen besser zu verstehen, füllen wir die Linked List jetzt mit einer Reihe von Wörtern. Dafür erstellen wir zunächst eine Methode, die die Liste traversiert und ihre Inhalte 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

Die obige Methode gibt die Inhalte unserer Linked List aus. Nutzen wir nun die definierten Methoden, um die Liste mit den Wörtern „the quick brown fox“ zu fü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 einer Linked List einfügen

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

    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 erzeugt zunächst einen neuen Knoten. Dann prüft sie, ob die Liste leer ist; falls ja, wird der neue Knoten als Kopf gesetzt. Andernfalls traversiert sie die Liste bis zum letzten Knoten und setzt dessen Zeiger auf den neuen Knoten.

Binde diese Methode nun in deine LinkedList-Klasse ein und nutze sie, um ein Wort ans Ende der Liste zu hängen. Ändere dazu deine 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 haben hier einfach die Methode insertAtEnd aufgerufen, um das Wort „jumps“ am Ende der Liste auszugeben. Der Code sollte folgende Ausgabe erzeugen:

"the quick brown fox jumps"

Einen Knoten vom Anfang einer Linked List löschen

Das Löschen des ersten Knotens ist einfach: Der Kopf der Liste wird auf den zweiten Knoten gesetzt. So gehört der ursprüngliche erste Knoten nicht mehr 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 vom Ende einer Linked List 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 letzte Knoten nicht mehr zur Liste. Kopiere 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 Linked List leer ist, und gibt gegebenenfalls eine Nachricht zurück. Enthält die Liste nur einen Knoten, wird dieser entfernt. Bei mehreren Knoten wird der vorletzte Knoten ermittelt und dessen Verweis auf None gesetzt.

Aktualisieren wir nun die Main-Funktion, um Elemente am Anfang und Ende der Linked List 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 obige Code gibt die Liste vor und nach dem Löschen aus und zeigt so, wie Einfüge- und Löschoperationen in Linked Lists funktionieren. Nach dem Ausführen solltest du diese Ausgabe sehen:

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

In der Linked List nach einem bestimmten Wert suchen

Zum Schluss lernen wir das Auffinden eines bestimmten Werts in der Linked List. Dazu startet die Methode am Kopf und iteriert durch jeden Knoten, bis die Knotendaten dem Suchwert entsprechen. Hier ist eine praktische Implementierung:

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 bestimmte Werte in der erstellten Linked List zu finden, erweitere deine Main-Funktion um die eben definierte 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

Der Code erzeugt folgende Ausgabe:

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 steht. „lazy“ ist nicht Teil der Liste und wurde daher nicht gefunden.

Fazit

Glückwunsch, wenn du bis hierhin gelesen hast! Du verstehst jetzt die Grundprinzipien von Linked Lists – ihren Aufbau, die Typen, wie man Elemente hinzufügt und entfernt und wie man sie traversiert.

Aber hier endet die Reise nicht. Linked Lists sind nur der Einstieg in die Welt der Datenstrukturen und Algorithmen. Hier sind mögliche nächste Schritte, um dein Verständnis zu vertiefen:

Starte ein eigenes Projekt

Setze Linked Lists praktisch ein, indem du sie in ein Coding- oder Data-Science-Projekt integrierst. Linked Lists kommen in Dateisystemen, Hashtabellen, GPS-Navigationssystemen und sogar bei Brettspielen zum Einsatz. Für den Einstieg in eigene Projekte schau dir unsere kostenlosen geführten Data-Science-Projekte an, die dir zeigen, wie du reale Probleme in Python, R und SQL löst.

Lerne mehr über Datenstrukturen und Algorithmen

Weitere Datenstrukturen wie Bäume, Stacks und Queues sind der logische nächste Schritt. Sie bauen auf den Prinzipien von Linked Lists auf und helfen dir, ein breiteres Spektrum an Problemen effizient zu lösen. Bäume und binäre Suchbäume erweitern das Konzept etwa zu hierarchischen Strukturen, in denen ein Knoten mit mehreren Elementen verbunden sein kann.

Wenn dir diese Konzepte neu sind, keine Sorge! 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 verstehst du Such- und Sortieralgorithmen, mit denen du effizienter programmierst und Probleme löst.

Fortgeschrittene Linked-List-Konzepte erkunden

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

Darauf aufbauend kannst du doppelt und zirkulär verkettete Listen implementieren. Skip Lists sind eine weitere Erweiterung, die schnellere Suchvorgänge ermöglicht, indem sie schnelleren Zugriff auf Elemente bieten.

Mit diesen fortgeschrittenen Datenstrukturen hebst du deine technischen Fähigkeiten auf das nächste Level und verbesserst deine Programmierkompetenz deutlich – ideal zur Vorbereitung auf komplexere Aufgaben in Data Science, Softwareentwicklung und Machine Learning Engineering.

Wenn du vorab eine einsteigerfreundliche Einführung ins Programmieren möchtest, bevor du dich an fortgeschrittene Themen wagst, schau dir unseren Python Programmer Career Track an. Er umfasst eine Reihe von Kursen, die dir die Grundlagen der Sprache vermitteln.