Hallo nochmal! Im Vorfeld des Starts des Python Developer- Kurses haben wir für Sie ein kleines Autorenmaterial zu verknüpften Listen in Python vorbereitet.
Python ist eine sehr praktische und facettenreiche Sprache, verfügt jedoch standardmäßig nicht über eine Datenstruktur wie eine verknüpfte Liste oder eine verknüpfte Liste. Heute werde ich meine Best Practices zu diesem Thema teilen und ein wenig über diese Datenstruktur sprechen. Dieser Artikel ist für diejenigen von Interesse, die zuerst auf das Thema verknüpfte Listen stoßen und verstehen möchten, wie sie aus algorithmischer Sicht funktionieren.
Was ist eine LinkedList?
Eine LinkedList oder eine Linked List ist eine Datenstruktur. Eine verknüpfte Liste bietet die Möglichkeit, aus beliebigen Elementen eine bidirektionale Warteschlange zu erstellen. Jedes Element einer solchen Liste wird als Knoten betrachtet. Tatsächlich hat ein Knoten seinen Wert sowie zwei Links zu den vorherigen und nachfolgenden Knoten. Das heißt, die Liste wird durch Knoten „verknüpft“, die dabei helfen, die Liste nach oben oder unten zu verschieben. Aufgrund dieser strukturellen Merkmale können Sie einen Stapel, eine Warteschlange oder eine doppelte Warteschlange aus einer verknüpften Liste organisieren.
Lassen Sie uns trockene Definitionen visualisieren. Jetzt haben wir Katzen, die in Kisten sitzen. Und auf jeder Box steht, was in Ordnung ist und wofür es stehen soll.
Was wir mit einer verknüpften Liste machen werden:- Überprüfen Sie, ob dieses oder jenes Element darin enthalten ist.
- Fügen Sie am Ende Knoten hinzu.
- Ermitteln Sie den Wert eines Knotens anhand des Index.
- Knoten löschen.
Tatsächlich gibt es viel mehr Möglichkeiten, mit ihnen zu arbeiten, aber wir werden uns mit der Umsetzung dieser grundlegenden Schritte befassen. Nachdem Sie verstanden haben, nach welchem Prinzip sie aufgebaut sind, können Sie selbst problemlos Ihre eigenen Methoden implementieren.
Sie müssen zunächst zwei Klassen erstellen:
class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
Im allgemeinen Fall haben wir einen Knoten, der einen Wert enthält - eine Katze und eine Verknüpfung zum nächsten Knoten. Das heißt, in der Box-Klasse gibt es jeweils eine Katze und einen Link zur nächsten Box. Wie jede Liste hat auch die Kohärenz einen Anfang, nämlich den Kopf. Da anfangs nichts vorhanden ist, wird das Startelement auf Keine gesetzt.
Ist das Element in der Liste
Beginnen wir mit einem einfachen. Um zu überprüfen, ob sich in einem der Felder in Reihe eine bestimmte Katze befindet, müssen Sie die gesamte Liste durchlaufen und den vorhandenen Wert mit den Werten des Elements in der Liste überprüfen.
def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False
Knoten am Ende der Liste hinzufügen
Zuerst müssen Sie eine neue Box erstellen und bereits eine neue Katze hineinlegen. Danach müssen Sie ab dem Anfang der verknüpften Liste prüfen, ob im aktuellen Knoten ein Link zum nächsten vorhanden ist, und wenn es einen gibt, dann gehen Sie zu diesem Knoten, andernfalls ist der Knoten der letzte. Sie müssen also einen Link zum nächsten Knoten erstellen und dasselbe neue Feld darin einfügen. was wir geschaffen haben.
def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox
Holen Sie sich einen Knoten nach Index
Mit dem Index catIndex möchten wir einen Boxknoten erhalten, aber da der Index nicht für die Knoten als solche bereitgestellt wird, müssen wir eine Art Ersatz finden, nämlich eine Variable, die als Index fungiert. Diese Variable ist boxIndex. Wir gehen die gesamte Liste durch und überprüfen die "Seriennummer" des Knotens. Wenn sie mit dem gewünschten Index übereinstimmt, erzeugen wir das Ergebnis.
def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat
Knoten löschen
Hier betrachten wir das Entfernen eines Elements nicht nach Index, sondern nach Wert, um zumindest eine gewisse Vielfalt einzuführen.
Die Suche beginnt am Kopf der Liste, dh am ersten Feld in einer Reihe, und wird fortgesetzt, bis die Felder leer sind, dh bis der Headcat zu None wird. Wir prüfen, ob der im aktuellen Knoten gespeicherte Wert mit dem Wert übereinstimmt, den wir löschen möchten. Wenn nicht, dann machen wir einfach weiter. Wenn es jedoch übereinstimmt, löschen wir es und "verknüpfen" die Links erneut, dh wir löschen das N-te Feld, während das N-1-Feld jetzt auf das N + 1-Feld verweist.
def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None
Das ist alles, danke fürs Lesen des Materials! Tatsächlich ist die LinkedList-Struktur nicht kompliziert und es ist wichtig zu verstehen, wie sie von innen funktioniert. Natürlich hätte es in Python in Lambda-Ausdrücken implementiert werden können, es hätte viel weniger Platz in Anspruch genommen, aber hier wollte ich seine Struktur und das Prinzip seiner Funktionsweise in Python so detailliert wie möglich erklären, anstatt der Optimierung nachzujagen.
Den Quellcode finden
Sie hier .