Python Linked Lists: Tutorial mit Beispielen

Eine verknüpfte Liste ist eine Datenstruktur, die eine wichtige Rolle bei der Datenorganisation und -verwaltung spielt. Sie enthält eine Reihe von Knotenpunkten, die an zufälligen Stellen im Speicher abgelegt werden, was eine effiziente Speicherverwaltung ermöglicht. Jeder Knoten in einer verketteten Liste enthält zwei Hauptkomponenten: den Datenteil und einen Verweis auf den nächsten Knoten in der Reihenfolge.

Wenn sich dieses Konzept auf den ersten Blick kompliziert anhört, mach dir keine Sorgen!

Wir erklären dir, was verknüpfte Listen sind, warum wir sie verwenden und welche einzigartigen Vorteile sie bieten.

Warum Linked Lists?

Verlinkte Listen wurden entwickelt, um verschiedene Nachteile zu überwinden, die mit der Speicherung von Daten in regulären Listen und Arrays verbunden sind, wie unten beschrieben:

Einfaches Einfügen und Löschen

Wenn du in Listen ein Element an einer anderen Position als dem Ende einfügst oder löschst, müssen alle nachfolgenden Elemente an eine andere Position verschoben werden. Dieser Prozess hat eine Zeitkomplexität von O(n) und kann die Leistung erheblich beeinträchtigen, insbesondere wenn die Liste größer wird. Wenn du noch nicht weißt, wie Listen funktionieren oder wie sie implementiert werden, kannst du unser Tutorial über Python-Listen lesen.

Verknüpfte Listen funktionieren jedoch anders. Sie speichern Elemente an verschiedenen, nicht zusammenhängenden Speicherplätzen und verbinden sie durch Zeiger mit nachfolgenden Knoten. Mit dieser Struktur können verknüpfte Listen an jeder beliebigen Stelle Elemente hinzufügen oder entfernen, indem du einfach die Verknüpfungen so änderst, dass sie ein neues Element einschließen oder das gelöschte Element umgehen.

Sobald die Position des Elements bekannt ist und ein direkter Zugriff auf den Punkt des Einfügens oder Löschens besteht, kann das Hinzufügen oder Entfernen von Knoten in O(1) Zeit erfolgen.

Dynamische Größe

Python-Listen sind dynamische Arrays, d.h. sie bieten die Flexibilität, die Größe zu ändern.

Dieser Prozess beinhaltet jedoch eine Reihe komplexer Vorgänge, einschließlich der Neuzuweisung des Arrays in einen neuen, größeren Speicherblock. Eine solche Neuzuteilung ist ineffizient, da Elemente in einen neuen Block kopiert werden, wodurch möglicherweise mehr Platz zugewiesen wird, als unmittelbar erforderlich ist.

Im Gegensatz dazu können verknüpfte Listen dynamisch wachsen und schrumpfen, ohne dass sie neu zugewiesen oder in ihrer Größe verändert werden müssen. Das macht sie zu einer bevorzugten Option für Aufgaben, die eine hohe Flexibilität erfordern.

Speichereffizienz

Listen weisen Speicher für alle ihre Elemente in einem zusammenhängenden Block zu. Wenn eine Liste über ihre ursprüngliche Größe hinaus wachsen muss, muss sie einen neuen, größeren Block zusammenhängenden Speichers zuweisen und dann alle vorhandenen Elemente in diesen neuen Block kopieren. Dieser Prozess ist zeitaufwändig und ineffizient, besonders bei großen Listen. Wird die anfängliche Größe der Liste hingegen überschätzt, wird der ungenutzte Speicher verschwendet.

Im Gegensatz dazu wird bei verknüpften Listen für jedes Element separat Speicher zugewiesen. Diese Struktur führt zu einer besseren Speichernutzung, da Speicher für neue Elemente zugewiesen werden kann, wenn sie hinzugefügt werden.

Wann solltest du Linked Lists verwenden?

Obwohl verknüpfte Listen bestimmte Vorteile gegenüber normalen Listen und Arrays bieten, wie z.B. dynamische Größe und Speichereffizienz, haben sie auch ihre Grenzen. Da für jedes Element Zeiger gespeichert werden müssen, um den nächsten Knoten zu referenzieren, ist der Speicherverbrauch pro Element bei der Verwendung von verknüpften Listen höher. Außerdem erlaubt diese Datenstruktur keinen direkten Zugriff auf die Daten. Der Zugriff auf ein Element erfordert ein sequentielles Traversieren vom Anfang der Liste aus, was zu einer O(n) Suchzeitkomplexität führt.

Die Entscheidung, ob eine verknüpfte Liste oder ein Array verwendet wird, hängt von den spezifischen Anforderungen der Anwendung ab. Verknüpfte Listen sind besonders nützlich, wenn:

• Du musst häufig viele Elemente einfügen und löschen
• Die Datengröße ist unvorhersehbar oder wird sich wahrscheinlich häufig ändern
• Direkter Zugang zu den Elementen ist keine Voraussetzung
• Der Datensatz enthält große Elemente oder Strukturen

Arten von verknüpften Listen

Es gibt drei Arten von verknüpften Listen, die jeweils einzigartige Vorteile für verschiedene Szenarien bieten. Diese Typen sind:

Einzeln verknüpfte Listen

Einzeln verknüpfte Liste

Eine einfach verkettete Liste ist die einfachste Art einer verketteten Liste, bei der jeder Knoten einige Daten und einen Verweis auf den nächsten Knoten in der Folge enthält. Sie können nur in einer einzigen Richtung durchlaufen werden - vom Kopf (dem ersten Knoten) zum Schwanz (dem letzten Knoten).

Jeder Knoten in einer einfach verketteten Liste besteht normalerweise aus zwei Teilen:

• Daten: Die tatsächlichen Informationen, die in dem Knoten gespeichert sind.
• Nächster Pointer: Ein Verweis auf den nächsten Knoten. Der nächste Zeiger des letzten Knotens wird normalerweise auf Null gesetzt.

Da diese Datenstrukturen nur in eine Richtung durchlaufen werden können, muss man für den Zugriff auf ein bestimmtes Element nach Wert oder Index am Kopf beginnen und sich sequentiell durch die Knoten bewegen, bis man den gewünschten Knoten gefunden hat. Diese Operation hat eine Zeitkomplexität von O(n), was sie für große Listen weniger effizient macht.

Das Einfügen und Löschen eines Knotens am Anfang einer einfach verketteten Liste ist mit einer Zeitkomplexität von O(1) sehr effizient. Das Einfügen und Löschen in der Mitte oder am Ende erfordert jedoch das Durchlaufen der Liste bis zu diesem Punkt, was zu einer Zeitkomplexität von O(n) führt.

Das Design von einfach verketteten Listen macht sie zu einer nützlichen Datenstruktur für Operationen, die am Anfang der Liste stattfinden.

Doppelt verknüpfte Listen

Doppelt verknüpfte Liste

Ein Nachteil von einfach verketteten Listen ist, dass wir sie nur in eine Richtung durchlaufen können und bei Bedarf nicht zum vorherigen Knoten zurückkehren können. Diese Einschränkung schränkt unsere Möglichkeiten ein, Operationen durchzuführen, die eine bidirektionale Navigation erfordern.

Doppelt verkettete Listen lösen dieses Problem, indem sie in jedem Knoten einen zusätzlichen Zeiger enthalten, der sicherstellt, dass die Liste in beide Richtungen durchlaufen werden kann. Jeder Knoten in einer doppelt verketteten Liste enthält drei Elemente: die Daten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten.

Zirkulär verknüpfte Listen

Zirkulär verknüpfte Liste

Zirkulär verknüpfte Listen sind eine spezielle Form der verknüpften Liste, bei der der letzte Knoten auf den ersten Knoten zurückverweist und so eine kreisförmige Struktur entsteht. Das bedeutet, dass die zirkulär verknüpfte Liste im Gegensatz zu den einfach und doppelt verknüpften Listen, die wir bisher gesehen haben, nicht endet, sondern in einer Schleife weiterläuft.

Die zyklische Natur von zirkulären verknüpften Listen macht sie ideal für Szenarien, die in einer Schleife durchlaufen werden müssen, wie z.B. Brettspiele, die vom letzten Spieler zum ersten zurückkehren, oder in Rechenalgorithmen wie der Round-Robin-Planung.

Wie man eine verkettete Liste in Python erstellt

Da wir nun wissen, was verknüpfte Listen sind, warum wir sie verwenden und welche Varianten es gibt, wollen wir diese Datenstrukturen in Python implementieren. Das Notizbuch für diesen Lehrgang ist auch in dieser DataLab-Arbeitsmappe verfügbar; wenn du eine Kopie erstellst, kannst du den Code bearbeiten und ausführen. Dies ist eine gute Option, wenn du Probleme hast, den Code selbst auszuführen!

Initialisierung eines Knotens

Wie wir bereits gelernt haben, ist ein Knoten ein Element in der verketteten Liste, das Daten und einen Verweis auf den nächsten Knoten in der Sequenz speichert. Hier siehst du, wie du einen Knoten in Python definieren kannst:

class Node:
    def __init__(self, data):
        self.data = data  # Assigns the given data to the node
        self.next = None  # Initialize the next attribute to null

Der obige Code initialisiert einen Knoten, indem er zwei Hauptaktionen durchführt: Dem Attribut "Daten" des Knotens wird ein Wert zugewiesen, der die eigentliche Information darstellt, die der Knoten enthalten soll. Das Attribut "next" steht für die Adresse des nächsten Knotens. Dieser ist derzeit auf None gesetzt, was bedeutet, dass er mit keinem anderen Knoten in der Liste verknüpft ist. Wenn wir der verknüpften Liste weitere Knoten hinzufügen, wird dieses Attribut aktualisiert und verweist auf den nächsten Knoten.

Erstellen einer verknüpften Listenklasse

Als Nächstes müssen wir die Klasse der verknüpften Liste erstellen. Diese kapselt alle Vorgänge zur Verwaltung der Knoten, wie das Einfügen und Entfernen. Wir beginnen mit der Initialisierung der verknüpften Liste:

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

Indem wir self.head auf None setzen, geben wir an, dass die verknüpfte Liste anfangs leer ist und dass es keine Knoten in der Liste gibt, auf die wir zeigen können. Wir werden nun die Liste auffüllen, indem wir neue Knotenpunkte einfügen.

Einen neuen Knoten am Anfang einer verknüpften Liste einfügen

In der Klasse LinkedList fügen wir eine Methode hinzu, mit der wir einen neuen Knoten erstellen und ihn an den Anfang der Liste setzen:

    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 die oben genannte Methode aufrufst, wird ein neuer Knoten mit den von dir angegebenen Daten erstellt. Der nächste Zeiger dieses neuen Knotens wird auf den aktuellen Kopf der Liste gesetzt, wodurch dieser Knoten vor den bestehenden Knoten platziert wird. Schließlich wird der neu erstellte Knoten zum Kopf der Liste gemacht.

Wir werden diese verknüpfte Liste nun mit einer Reihe von Wörtern füllen, um ein besseres Verständnis dafür zu bekommen, wie das Einfügen funktioniert. Um das zu erreichen, erstellen wir zunächst eine Methode, die den Inhalt der Liste durchläuft und 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 druckt den Inhalt unserer verknüpften Liste aus. Verwenden wir nun die Methoden, die wir definiert haben, um unsere Liste mit einer Reihe von Wörtern zu füllen: "Der schlaue braune Fuchs".

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 Codezeilen sollten die folgende Ausgabe liefern:

"the quick brown fox"

Einen neuen Knoten am Ende einer verketteten Liste einfügen

Wir werden nun eine Methode namens insertAtEnd in der Klasse LinkedList erstellen, um einen neuen Knoten am Ende der Liste zu erstellen. Wenn die Liste leer ist, wird der neue Knoten der Kopf der Liste. Andernfalls wird er an den aktuell letzten Knoten in der Liste angehängt. Schauen wir mal, wie das in der Praxis funktioniert:

def insertAtEnd(self, new_data):
        new_node = Node(new_data)  # Create a new node
        if self.head is None:
            self.head = new_node  # If the list is empty, make the new node the head
            return
        last = self.head 
        while last.next:  # Otherwise, traverse the list to find the last node
            last = last.next
        last.next = new_node  # Make the new node the next node of the last node

Die obige Methode beginnt mit der Erstellung eines neuen Knotens. Dann wird geprüft, ob die Liste leer ist, und wenn ja, wird der neue Knoten als Kopf der Liste zugewiesen. Andernfalls durchläuft er die Liste, um den letzten Knoten zu finden und setzt den Zeiger dieses Knotens auf den neuen Knoten.

Wir müssen diese Methode nun in unsere Klasse LinkedList einbinden und sie verwenden, um ein Wort am Ende unserer Liste hinzuzufügen. Um dies zu erreichen, ändere deine Hauptfunktion 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()

Beachte, dass wir einfach die Methode insertAtEnd aufgerufen haben, um das Wort "jumps" am Ende der Liste zu drucken. Der obige Code sollte die folgende Ausgabe liefern:

"the quick brown fox jumps"

Löschen eines Knotens vom Anfang einer verknüpften Liste

Das Löschen des ersten Knotens einer verketteten Liste ist einfach, denn dazu musst du nur den Kopf der Liste auf den zweiten Knoten richten. Auf diese Weise wird der erste Knoten nicht mehr Teil der Liste sein. Um dies zu erreichen, füge die folgende Methode in die Klasse LinkedList 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

Löschen eines Knotens am Ende einer verknüpften Liste

Um den letzten Knoten einer verknüpften Liste zu löschen, müssen wir die Liste durchlaufen, um den vorletzten Knoten zu finden, und seinen nächsten Zeiger in None ändern. Auf diese Weise wird der letzte Knoten nicht mehr Teil der Liste sein. Kopiere die folgende Methode und füge sie in deine LinkedList Klasse ein, um dies zu erreichen:

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 obige Methode prüft zunächst, ob die verknüpfte Liste leer ist, und gibt in diesem Fall eine Meldung an den Benutzer zurück. Andernfalls, wenn die Liste einen einzelnen Knoten enthält, wird dieser Knoten entfernt. Bei Listen mit mehreren Knoten sucht die Methode den vorletzten Knoten und der nächste Knotenverweis wird auf None aktualisiert.

Aktualisieren wir nun die Hauptfunktion, um Elemente am Anfang und am Ende der verknüpften Liste 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 druckt die Liste vor und nach dem Löschen aus und zeigt, wie die Operationen Einfügen und Löschen in verknüpften Listen funktionieren. Nachdem du diesen Code ausgeführt hast, solltest du die folgende Ausgabe sehen:

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

Durchsuchen der verknüpften Liste nach einem bestimmten Wert

Die letzte Operation, die wir in diesem Kapitel lernen werden, ist das Abrufen eines bestimmten Wertes in der verknüpften Liste. Um dies zu erreichen, sollte die Methode am Anfang der Liste beginnen und jeden Knoten durchlaufen, um zu prüfen, ob die Daten des Knotens mit dem Suchwert übereinstimmen. Hier ist eine praktische Umsetzung dieses Vorgangs:

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 von uns erstellten verknüpften Liste zu finden, aktualisiere deine Hauptfunktion so, dass sie die gerade erstellte Suchmethode enthält:

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 obige Code ergibt die 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 in der verknüpften Liste gefunden, da es an der ersten Position der Liste steht. Das Wort "faul" ist jedoch nicht in der Liste enthalten, weshalb es nicht gefunden wurde.

Schlussgedanken

Wenn du es bis hierher geschafft hast, gratuliere ich dir! Du hast nun ein solides Verständnis der Grundprinzipien von verknüpften Listen, einschließlich ihrer Struktur, Typen, wie man Elemente hinzufügt und entfernt und wie man sie durchläuft.

Aber die Reise ist hier noch nicht zu Ende. Verknüpfte Listen sind nur der Anfang der Welt der Datenstrukturen und Algorithmen. Hier sind einige mögliche nächste Schritte für dich, um dein Verständnis für das Thema zu vertiefen:

Erstelle dein eigenes Projekt

Tauche in die praktischen Anwendungen von verknüpften Listen ein, indem du sie in ein Programmier- oder Data Science-Projekt integrierst. Verknüpfte Listen werden verwendet, um Dateisysteme zu entwickeln, Hashtabellen zu erstellen und sogar GPS-Navigationssysteme und Brettspiele zu entwickeln. Um mit deinen eigenen Projekten zu beginnen, schau dir unsere kostenlosen angeleiteten Data Science-Projekte an, in denen du lernst, wie du reale Probleme in Python, R und SQL lösen kannst.

Lerne Datenstrukturen und Algorithmen kennen

Das Erlernen anderer Datenstrukturen, wie z.B. Bäume, Stapel und Warteschlangen, ist eine natürliche Weiterentwicklung des Wissens über verknüpfte Listen. Diese Strukturen bauen auf den Prinzipien von verknüpften Listen auf und helfen dir, eine größere Bandbreite an Rechenaufgaben effizient zu lösen. Bäume und binäre Suchbäume zum Beispiel erweitern das Konzept der verknüpften Listen in eine hierarchische Form, so dass jeder Knoten mit mehreren Elementen in der Datenstruktur verbunden werden kann.

Wenn diese Konzepte für dich ungewohnt sind, mach dir keine Sorgen! Datacamp bietet einen ganzen Kurs über Datenstrukturen und Algorithmen in Python an, in dem du diese Konzepte genauer kennenlernst. Du wirst zunächst etwas über Datenstrukturen wie Stapel, Bäume, Hashtabellen, Warteschlangen und Graphen lernen. Im Laufe des Kurses lernst du Such- und Sortieralgorithmen kennen, die dich zu einem effizienteren Programmierer und Problemlöser machen.

Erweiterte Konzepte für verknüpfte Listen erforschen

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

Du kannst dieses Wissen noch weiter vertiefen, indem du die Implementierung von doppelt und zirkulär verknüpften Listen lernst. Sprunglisten sind eine weitere Erweiterung von verknüpften Listen, die schnellere Suchvorgänge ermöglichen, indem sie einen schnelleren Zugriff auf Elemente ermöglichen.

Das Erlernen dieser fortgeschrittenen Datenstrukturen wird deine technischen Fähigkeiten auf die nächste Stufe heben und deine Programmierfähigkeiten erheblich verbessern. Damit bist du für komplexere Herausforderungen in Bereichen wie Data Science, Softwareentwicklung und maschinelles Lernen gerüstet.

Wenn du einen einsteigerfreundlichen Einstieg in die Programmierung suchst, bevor du dich an diese fortgeschrittenen Themen heranwagst, dann schau dir unseren Berufsweg als Python-Programmierer/in an. Sie bietet eine Reihe von Kursen an, in denen du die Grundlagen der Sprache lernst.