In diesem Artikel erfahren Sie mehr über die Implementierung einer verknüpften Liste in Python . Um die verknüpfte Liste in Python zu implementieren, verwenden wir Klassen in Python . Jetzt wissen wir, dass eine verknüpfte Liste aus Knoten besteht und dass Knoten zwei Elemente haben, nämlich Daten und einen Verweis auf einen anderen Knoten. Lassen Sie uns zuerst den Knoten implementieren.
Was ist eine verknüpfte Liste in Python?
Eine verknüpfte Liste ist eine Art linearer Datenstruktur, die Arrays ähnelt. Es handelt sich um eine Sammlung von Knoten, die miteinander verknüpft sind. Ein Knoten enthält zwei Dinge: erstens Daten und zweitens eine Verbindung, die ihn mit einem anderen Knoten verbindet. Unten sehen Sie ein Beispiel für eine verknüpfte Liste mit vier Knoten. Jeder Knoten enthält Zeichendaten und einen Link zu einem anderen Knoten. Unser erster Knoten ist wo Kopf Punkte und wir können über die auf alle Elemente der verknüpften Liste zugreifen Kopf.
Verlinkte Liste
Erstellen einer verknüpften Liste in Python
In dieser LinkedList-Klasse verwenden wir die Node-Klasse, um eine verknüpfte Liste zu erstellen. In dieser Klasse haben wir eine __heiß__ Methode, die die verknüpfte Liste mit einem leeren Kopf initialisiert. Als nächstes haben wir eine erstellt insertAtBegin() Methode zum Einfügen eines Knotens am Anfang der verknüpften Liste, an insertAtIndex() Methode zum Einfügen eines Knotens am angegebenen Index der verknüpften Liste und insertAtEnd() Die Methode fügt einen Knoten am Ende der verknüpften Liste ein. Danach haben wir die remove_node() Methode, die die Daten als Argument zum Löschen dieses Knotens verwendet. Im remove_node() Methode durchlaufen wir die verknüpfte Liste. Wenn ein Knoten vorhanden ist, der den Daten entspricht, löschen wir diesen Knoten aus der verknüpften Liste. Dann haben wir das sizeOfLL() Methode zum Abrufen der aktuellen Größe der verknüpften Liste und die letzte Methode der LinkedList-Klasse ist printLL() Dies durchläuft die verknüpfte Liste und druckt die Daten jedes Knotens.
Erstellen einer Knotenklasse
Wir haben eine Node-Klasse erstellt, in der wir eine definiert haben __heiß__ Funktion zum Initialisieren des Knotens mit den als Argument übergebenen Daten und einer Referenz mit None, denn wenn wir nur einen Knoten haben, enthält seine Referenz nichts.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Einfügen in eine verknüpfte Liste
Einfügen am Anfang in die verknüpfte Liste
Diese Methode fügt den Knoten am Anfang der verknüpften Liste ein. Bei dieser Methode erstellen wir eine neuer_Knoten mit dem Gegebenen Daten und prüfen, ob der Kopf ein leerer Knoten ist oder nicht. Wenn der Kopf leer ist, erstellen wir das neuer_Knoten als Kopf Und zurückkehren sonst stecken wir als nächstes den Kopf ein neuer_Knoten und mache das Kopf gleich neuer_Knoten.
Java-Substring-Methode
Python3
def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> |
>
>
Fügen Sie einen Knoten an einer bestimmten Position in einer verknüpften Liste ein
Diese Methode fügt den Knoten am angegebenen Index in die verknüpfte Liste ein. Bei dieser Methode erstellen wir eine neuer_Knoten mit gegebenen Daten, einem aktuellen_Knoten, der dem Kopf entspricht, und einem Zähler 'Position' initialisiert mit 0. Wenn der Index nun gleich Null ist, bedeutet dies, dass der Knoten am Anfang eingefügt werden soll, also haben wir aufgerufen insertAtBegin()-Methode andernfalls führen wir eine while-Schleife durch, bis die aktueller_Knoten ist ungleich zu Keiner oder (Position+1) nicht gleich dem Index ist, den wir an der einen Position zurücksetzen müssen, um an einer bestimmten Position einzufügen, um die Verknüpfung von Knoten herzustellen, und in jeder Iteration erhöhen wir die Position um 1 und machen das aktueller_Knoten als nächstes davon. Wenn die Schleife unterbrochen wird und wenn aktueller_Knoten ist ungleich zu Keiner Wir fügen danach new_node ein aktueller_Knoten. Wenn aktueller_Knoten ist gleich Keiner Dies bedeutet, dass der Index nicht in der Liste vorhanden ist und wir drucken Index nicht vorhanden.
Python3
# Indexing starts from 0.> def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> |
>
>
Einfügen in die verknüpfte Liste am Ende
Diese Methode fügt den Knoten am Ende der verknüpften Liste ein. Bei dieser Methode erstellen wir eine neuer_Knoten mit den angegebenen Daten und prüfen Sie, ob die Kopf ist ein leerer Knoten oder nicht, wenn der Kopf leer ist, dann machen wir das neuer_Knoten als Kopf Und zurückkehren anders wir machen ein current_node gleich Zu der Kopf bis zum letzten durchqueren Knoten der verknüpften Liste und wann wir sie erhalten Keiner Nach dem current_node unterbricht die while-Schleife und fügt die ein neuer_Knoten im nächsten von aktueller_Knoten Dies ist der letzte Knoten der verknüpften Liste.
Python3
def> inserAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> |
>
>
Aktualisieren Sie den Knoten einer verknüpften Liste
Dieser Code definiert eine Methode namens updateNode in einer verknüpften Listenklasse. Es wird verwendet, um den Wert eines Knotens an einer bestimmten Position in der verknüpften Liste zu aktualisieren.
Python3
# Update node of a linked list> # at given position> def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> |
Java-Methode
>
>
Knoten in einer verknüpften Liste löschen
Entfernen Sie den ersten Knoten aus der verknüpften Liste
Diese Methode entfernt den ersten Knoten der verknüpften Liste, indem einfach der zweite Knoten erstellt wird Kopf der verknüpften Liste.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Letzten Knoten aus der verknüpften Liste entfernen
Bei dieser Methode löschen wir den letzten Knoten. Zuerst durchlaufen wir mithilfe der while-Schleife den vorletzten Knoten und erstellen dann den nächsten Knoten dieses Knotens Keiner und der letzte Knoten wird entfernt.
Python3
def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> |
>
>
Löschen Sie einen verknüpften Listenknoten an einer bestimmten Position
Bei dieser Methode entfernen wir den Knoten am angegebenen Index, diese Methode ähnelt Die insert_at_inded() Methode. Wenn bei dieser Methode die Kopf Ist Keiner wir einfach zurückkehren sonst initialisieren wir a aktueller_Knoten mit Selbstkopf Und Position mit 0. Wenn die Position gleich dem Index ist, den wir aufgerufen haben remove_first_node() Methode, andernfalls durchlaufen wir mithilfe der while-Schleife den einen Knoten davor, den wir entfernen möchten. Danach überprüfen wir, wenn wir die while-Schleife verlassen haben dieser current_node ist gleich Keiner Wenn nicht, machen wir den nächsten aktuellen_Knoten gleich dem nächsten Knoten, den wir entfernen möchten, andernfalls drucken wir die Nachricht Index nicht vorhanden Weil aktueller_Knoten ist gleich Keiner.
Python3
# Method to remove at given index> def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> |
>
>
Löschen Sie einen verknüpften Listenknoten bestimmter Daten
Diese Methode entfernt den Knoten mit den angegebenen Daten aus der verknüpften Liste. Bei dieser Methode haben wir zunächst eine erstellt aktueller_Knoten gleich dem Kopf und führe a aus while-Schleife um die verknüpfte Liste zu durchlaufen. Diese While-Schleife wird unterbrochen, wenn aktueller_Knoten wird Keiner oder die Daten neben dem aktuellen Knoten sind gleich den im Argument angegebenen Daten. Nun, nachdem ich aus der Schleife herausgekommen bin, wenn das aktueller_Knoten ist gleich Keiner Dies bedeutet, dass der Knoten in den Daten nicht vorhanden ist und wir einfach zurückkehren, und wenn die Daten neben dem liegen aktueller_Knoten gleich den angegebenen Daten ist, entfernen wir diesen Knoten, indem wir den nächsten entfernten_Knoten zum nächsten aktuellen_Knoten machen. Und dies wird mithilfe der if else-Bedingung implementiert.
Python3
sonst wenn Java
def> remove_node(>self>, data):> >current_node>=> self>.head> ># Check if the head node contains the specified data> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while> current_node>is> not> None> and> current_node.>next>.data !>=> data:> >current_node>=> current_node.>next> >if> current_node>is> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> |
>
>
Durchquerung verknüpfter Listen in Python
Diese Methode durchläuft die verknüpfte Liste und druckt die Daten jedes Knotens. Bei dieser Methode haben wir eine gemacht aktueller_Knoten gleich dem Kopf und iterieren Sie mit a durch die verknüpfte Liste while-Schleife bis zum aktueller_Knoten werden zu None und drucken die Daten von aktueller_Knoten in jeder Iteration und machen Sie die aktueller_Knoten Daneben.
Python3
Numpy Meshgrid
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Ermitteln Sie die Länge einer verknüpften Liste in Python
Diese Methode gibt die Größe der verknüpften Liste zurück. Bei dieser Methode haben wir einen Zähler initialisiert 'Größe' mit 0, und wenn der Kopf dann nicht gleich None ist, durchlaufen wir die verknüpfte Liste mit a while-Schleife und erhöhen Sie die Größe mit 1 in jeder Iteration und geben Sie die Größe zurück, wenn aktueller_Knoten wird Sonst niemand wir geben 0 zurück.
Python3
def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> |
>
>
Beispiel für die verknüpfte Liste in Python
In diesem Beispiel haben wir nach der Definition der Node- und LinkedList-Klasse eine verknüpfte Liste mit dem Namen erstellt Liste Verwenden Sie die verknüpfte Listenklasse und fügen Sie dann vier Knoten mit Zeichendaten ein 'A B C D' Und 'G' in der verknüpften Liste drucken wir dann die verknüpfte Liste mit aus printLL() Danach haben wir einige Knoten mithilfe der Remove-Methoden entfernt und drucken Sie dann die verknüpfte Liste erneut aus. In der Ausgabe können wir sehen, dass der Knoten erfolgreich gelöscht wurde. Danach drucken wir auch die Größe der verknüpften Liste aus.
Python3
# Create a Node class to create a node> class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> # Create a LinkedList class> class> LinkedList:> >def> __init__(>self>):> >self>.head>=> None> ># Method to add a node at begin of LL> >def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> ># Method to add a node at any index> ># Indexing starts from 0.> >def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> ># Method to add a node at the end of LL> >def> insertAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> ># Update node of a linked list> ># at given position> >def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> ># Method to remove first node of linked list> >def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> >self>.head>=> self>.head.>next> ># Method to remove last node of linked list> >def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> ># Method to remove at given index> >def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> ># Method to remove a node from linked list> >def> remove_node(>self>, data):> >current_node>=> self>.head> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while>(current_node !>=> None> and> current_node.>next>.data !>=> data):> >current_node>=> current_node.>next> >if> current_node>=>=> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> ># Print the size of linked list> >def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> ># print method for the linked list> >def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> # create a new linked list> llist>=> LinkedList()> # add nodes to the linked list> llist.insertAtEnd(>'a'>)> llist.insertAtEnd(>'b'>)> llist.insertAtBegin(>'c'>)> llist.insertAtEnd(>'d'>)> llist.insertAtIndex(>'g'>,>2>)> # print the linked list> print>(>'Node Data'>)> llist.printLL()> # remove a nodes from the linked list> print>(>'
Remove First Node'>)> llist.remove_first_node()> print>(>'Remove Last Node'>)> llist.remove_last_node()> print>(>'Remove Node at Index 1'>)> llist.remove_at_index(>1>)> # print the linked list again> print>(>'
Linked list after removing a node:'>)> llist.printLL()> print>(>'
Update node Value'>)> llist.updateNode(>'z'>,>0>)> llist.printLL()> print>(>'
Size of linked list :'>, end>=>' '>)> print>(llist.sizeOfLL())> |
>
>Ausgabe
Node Data c a g b d Remove First Node Remove Last Node Remove Node at Index 1 Linked list after removing a node: a b Update node Value z b Size of linked list : 2>