Wie implementiere ich eine verknüpfte Liste in Python?



Dieser Artikel zeigt, wie Sie eine verknüpfte Liste in Python mit verschiedenen Methoden erstellen können, um Aktualisierungen einzufügen und die Elemente in der verknüpften Liste zu entfernen.

Die Programmiersprache Python ist eine Open-Source-Sprache mit verschiedenen sofort einsatzbereiten Implementierungen, die sie einzigartig und leichter zu erlernen macht. Obwohl unterstützt das Konzept einer verknüpften Liste nicht, es gibt einen Weg, es durch eine andere Implementierung zu umgehen, um eine verknüpfte Liste zu erhalten. In diesem Artikel erfahren Sie, wie Sie eine verknüpfte Liste in Python erstellen können. Im Folgenden sind die Themen aufgeführt, die in diesem Blog behandelt werden:

Lass uns anfangen!!





Was ist eine verknüpfte Liste?

Die Verknüpfungsliste ist eine Folge von Knoten mit einem ähnlichen Datentyp. Jeder Knoten enthält ein Datenobjekt und einen Zeiger auf den nächsten Knoten.

Eine verknüpfte Liste ist eine lineare Datenstruktur mit der Sammlung mehrerer Knoten. Wo eJedes Element speichert seine eigenen Daten und einen Zeiger auf die Position des nächsten Elements. Das letzte Glied in einer verknüpften Liste zeigt auf null und gibt das Ende der Kette an. Ein Element in einer verknüpften Liste heißt a Knoten . Der erste Knoten heißt Kopf .Der letzte Knoten wird aufgerufendas Schwanz .
verknüpfte Liste - verknüpfte Liste in Python - EdurekaDie Standard-Python-Bibliothek verfügt nicht über eine verknüpfte Liste. Wir können das Konzept der Linklistendatenstruktur implementieren, indem wir das Konzept der Knoten verwenden.



Jetzt haben wir gelernt, was verbunden ist. Fahren wir also mit der Implementierung einer verknüpften Liste fort.

Implementieren einer verknüpften Liste

Zum Erstellen einer verknüpften Liste erstellen wir ein Knotenobjekt und eine andere Klasse, um dieses Knotenobjekt zu verwenden.
Code zum Erstellen der Knotenklasse.
Das obige Programm erstellt eine verknüpfte Liste mit drei Datenelementen.

Klassenknoten (Objekt): # Konstruktor zum Initialisieren von Klassenvariablen def __init __ (self, data = None, next_node = None): self.data = data self.next_node = next_node #get data def get_data (self): return self.data # get next value def get_next (self): return self.next_node # set next data def set_next (self, new_next): self.next_node = new_next

Die Implementierung einer Verknüpfungsliste besteht aus den folgenden Funktionen in einer verknüpften Liste
ein. Einfügen : Diese Methode fügt einen neuen Knoten in eine verknüpfte Liste ein.
2. Größe : Diese Methode gibt die Größe der verknüpften Liste zurück.
3. Suche : Diese Methode gibt einen Knoten zurück, der die Daten enthält, andernfalls wird ein Fehler ausgelöst
Vier. Löschen : Diese Methode löscht einen Knoten, der die Daten enthält, andernfalls wird ein Fehler ausgelöst



Sehen wir uns die Liste der verknüpften Methoden an

Init-Methode in einer verknüpften Liste

Klasse LinkedList (Objekt): def __init __ (self, head = None): self.head = head

Die Init-Methode wird zur Initialisierung von a verwendet Klasse Variable Wenn die Liste keine Knoten hat, wird sie auf keine gesetzt.

Einfügen:

def insert (self, data): new_node = Knoten (Daten) new_node.set_next (self.head) self.head = new_node

Diese Einfügemethode nimmt Daten auf, initialisiert einen neuen Knoten mit den angegebenen Daten und fügt sie der Liste hinzu. Technisch gesehen können Sie einen Knoten an einer beliebigen Stelle in der Liste einfügen. Der einfachste Weg, dies zu tun, besteht darin, ihn am Kopf der Liste zu platzieren und den neuen Knoten auf den alten Kopf zu richten (indem Sie die anderen Knoten auf der Linie nach unten schieben).

Größe

# Gibt die Gesamtzahl der Knoten in der Liste zurück. Def size (self): current = self.head count = 0, während current: count + = 1 current = current.get_next () return count

Die Größenmethode ist sehr einfach. Sie zählt im Wesentlichen Knoten, bis sie nicht mehr gefunden werden können, und gibt zurück, wie viele Knoten gefunden wurden. Die Methode beginnt am Kopfknoten und verläuft entlang der Knotenlinie bis zum Ende (der Strom ist am Ende Keine), während verfolgt wird, wie viele Knoten er gesehen hat.

Suche

# Gibt den Knoten in der Liste mit nodeData zurück. Ein Fehler ist aufgetreten, wenn der Knoten nicht vorhanden ist. Def search (self, nodeData): current = self.head isPresent = False, während current und isPresent False sind: if current.get_data () == nodeData: isPresent = True else: current = current.get_next () wenn current None ist: Erhöhen Sie ValueError ('Daten nicht in Liste vorhanden') und geben Sie current zurück

Die Suche ist der Größe eigentlich sehr ähnlich, aber anstatt die gesamte Liste der Knoten zu durchlaufen, wird bei jedem Stopp überprüft, ob der aktuelle Knoten die angeforderten Daten hat. Wenn ja, wird der Knoten zurückgegeben, der diese Daten enthält. Wenn die Methode die gesamte Liste durchläuft, die Daten jedoch noch nicht gefunden hat, wird ein Wertefehler ausgelöst und der Benutzer benachrichtigt, dass die Daten nicht in der Liste enthalten sind.

Löschen

c ++ Nummern in aufsteigender Reihenfolge sortieren
# Das Entfernen des Knotens aus der verknüpften Liste gibt einen Fehler zurück, wenn der Knoten nicht vorhanden ist. Def delete (self, nodeData): current = self.head previous = Keine isPresent = False, während current und isPresent False sind: if current.get_data () == nodeData: isPresent = True else: previous = current current = current.get_next () wenn current None ist: Erhöhen Sie ValueError ('Daten nicht in Liste vorhanden'), wenn previous None ist: self.head = current.get_next () else: previous.set_next ( current.get_next ())

Die Löschmethode durchläuft die Liste auf die gleiche Weise wie die Suche. Zusätzlich zum Verfolgen des aktuellen Knotens merkt sich die Löschmethode auch, dass der letzte Knoten besucht wurde. Wenn delete endlich den Knoten erreicht, den es löschen möchte. Dieser Knoten wird einfach aus der Kette entfernt, indem er übersprungen wird.

Damit meine ich, dass die Löschmethode, wenn sie den zu löschenden Knoten erreicht, den zuletzt besuchten Knoten (den 'vorherigen' Knoten) betrachtet und den Zeiger des vorherigen Knotens zurücksetzt. Anstatt auf den Knoten zu zeigen, der bald gelöscht werden soll.

Es zeigt auf den nächsten Knoten in der Zeile. Da keine Knoten auf den fehlerhaften Knoten zeigen, der gelöscht wird, wird er effektiv aus der Liste entfernt!

Dies bringt uns zum Ende dieses Artikels, wo wir gelernt haben, wie wir eine verknüpfte Liste in Python mit einer ähnlichen Implementierung erstellen können, obwohl Python das Konzept einer verknüpften Liste nicht wirklich unterstützt. Ich hoffe, Sie sind mit allem klar, was in diesem Tutorial mit Ihnen geteilt wurde.

Wenn Sie diesen Artikel unter 'Verknüpfte Liste in Python' relevant fanden, lesen Sie die Ein vertrauenswürdiges Online-Lernunternehmen mit einem Netzwerk von mehr als 250.000 zufriedenen Lernenden auf der ganzen Welt.

Wir sind hier, um Ihnen bei jedem Schritt auf Ihrer Reise zu helfen und einen Lehrplan zu erstellen, der für Studenten und Fachleute konzipiert ist, die eine sein möchten . Der Kurs soll Ihnen einen Vorsprung in die Python-Programmierung verschaffen und Sie sowohl für grundlegende als auch für fortgeschrittene Python-Konzepte sowie für verschiedene Konzepte schulen mögen

Wenn Sie auf Fragen stoßen, können Sie alle Ihre Fragen im Kommentarbereich von „Linked List In Python“ stellen. Unser Team beantwortet diese gerne.