In dit artikel leren we over de implementatie van een gekoppelde lijst in Python . Om de gekoppelde lijst in Python te implementeren, zullen we gebruiken lessen in Python . Nu weten we dat een gekoppelde lijst uit knooppunten bestaat en dat knooppunten twee elementen hebben, namelijk gegevens en een verwijzing naar een ander knooppunt. Laten we eerst het knooppunt implementeren.
Wat is een gekoppelde lijst in Python
Een gekoppelde lijst is een type lineaire gegevensstructuur vergelijkbaar met arrays. Het is een verzameling knooppunten die met elkaar verbonden zijn. Een knooppunt bevat twee dingen: ten eerste gegevens en ten tweede een link die het verbindt met een ander knooppunt. Hieronder ziet u een voorbeeld van een gekoppelde lijst met vier knooppunten en elk knooppunt bevat tekengegevens en een link naar een ander knooppunt. Ons eerste knooppunt is waar hoofd punten en we hebben toegang tot alle elementen van de gekoppelde lijst met behulp van de hoofd.
Gekoppelde lijst
Een gekoppelde lijst maken in Python
In deze LinkedList-klasse gebruiken we de Node-klasse om een gekoppelde lijst te maken. In deze klasse hebben we een __heet__ methode die de gekoppelde lijst initialiseert met een lege kop. Vervolgens hebben we een insertAtBegin() methode om een knooppunt aan het begin van de gekoppelde lijst in te voegen, an insertAtIndex() methode om een knooppunt in te voegen bij de gegeven index van de gekoppelde lijst, en insertAtEnd() methode voegt een knooppunt in aan het einde van de gekoppelde lijst. Daarna hebben we de verwijder_node() methode die de gegevens als argument gebruikt om dat knooppunt te verwijderen. In de verwijder_node() Met deze methode doorkruisen we de gekoppelde lijst als er een knooppunt aanwezig is dat gelijk is aan gegevens, dan verwijderen we dat knooppunt uit de gekoppelde lijst. Dan hebben wij de grootteVanLL() methode om de huidige grootte van de gekoppelde lijst te krijgen en de laatste methode van de klasse LinkedList is printLL() die de gekoppelde lijst doorkruist en de gegevens van elk knooppunt afdrukt.
Een knooppuntklasse maken
We hebben een Node-klasse gemaakt waarin we a hebben gedefinieerd __heet__ functie om het knooppunt te initialiseren met de gegevens doorgegeven als argument en een referentie met Geen, want als we maar één knooppunt hebben, staat er niets in de referentie.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
GB versus MB
>
Invoeging in gekoppelde lijst
Invoeging aan het begin van de gekoppelde lijst
Deze methode voegt het knooppunt aan het begin van de gekoppelde lijst in. Bij deze methode creëren we een nieuwe_knooppunt met het gegeven gegevens en controleren of het hoofd een leeg knooppunt is of niet. Als het hoofd leeg is, maken we de nieuwe_knooppunt als hoofd En opbrengst anders plaatsen we de kop bij de volgende nieuwe_knooppunt en maak de hoofd gelijk aan nieuwe_knooppunt.
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> |
>
>
Voeg een knooppunt in op een specifieke positie in een gekoppelde lijst
Deze methode voegt het knooppunt in op de gegeven index in de gekoppelde lijst. Bij deze methode creëren we een nieuwe_knooppunt met gegeven gegevens, een current_node die gelijk is aan de head, en een teller 'positie' initialiseert met 0. Als de index nu gelijk is aan nul, betekent dit dat het knooppunt aan het begin moet worden ingevoegd, zo hebben we gebeld insertAtBegin() methode anders voeren we een while-lus uit tot de huidig_knooppunt is niet gelijk aan Geen of (positie+1) is niet gelijk aan de index die we op de ene positie terug moeten invoegen op een bepaalde positie om de knooppunten te koppelen en in elke iteratie verhogen we de positie met 1 en maken we de huidig_knooppunt volgende ervan. Wanneer de lus breekt en of huidig_knooppunt is niet gelijk aan Geen we voegen new_node in achter in de huidig_knooppunt. Als huidig_knooppunt is gelijk aan Geen het betekent dat de index niet aanwezig is in de lijst en we afdrukken Index niet aanwezig.
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'>)> |
>
>
Invoeging in gekoppelde lijst aan einde
Deze methode voegt het knooppunt aan het einde van de gekoppelde lijst in. Bij deze methode creëren we een nieuwe_knooppunt met de opgegeven gegevens en controleer of de hoofd is een leeg knooppunt of niet als de hoofd leeg is, dan maken we de nieuwe_knooppunt als hoofd En opbrengst anders wij maken een huidige_knooppunt gelijk naar het hoofd doorkruisen tot het laatste knooppunt van de gelinkte lijst en wanneer we krijgen Geen na de current_node wordt de while-lus afgebroken en wordt de nieuwe_knooppunt in de volgende van huidig_knooppunt dat is het laatste knooppunt van de gekoppelde lijst.
Python3
wat is kaart-java
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> |
>
>
Werk het knooppunt van een gekoppelde lijst bij
Deze code definieert een methode met de naam updateNode in een gekoppelde lijstklasse. Het wordt gebruikt om de waarde van een knooppunt op een bepaalde positie in de gekoppelde lijst bij te werken.
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'>)> |
>
>
Knooppunt uit een gekoppelde lijst verwijderen
Verwijder het eerste knooppunt uit de gekoppelde lijst
Deze methode verwijdert het eerste knooppunt van de gekoppelde lijst eenvoudigweg door het tweede knooppunt te maken hoofd van de gekoppelde lijst.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Verwijder het laatste knooppunt uit de gekoppelde lijst
Bij deze methode verwijderen we het laatste knooppunt. Eerst gaan we naar het voorlaatste knooppunt met behulp van de while-lus, en dan maken we de volgende van dat knooppunt Geen en het laatste knooppunt wordt verwijderd.
Python3
anders als Java
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> |
>
>
Verwijder een gekoppeld lijstknooppunt op een bepaalde positie
Bij deze methode verwijderen we het knooppunt op de gegeven index, deze methode is vergelijkbaar met de insert_at_inded() methode. Bij deze methode, als de hoofd is Geen wij gewoon opbrengst anders initialiseren we a huidig_knooppunt met zelf.hoofd En positie met 0. Als de positie gelijk is aan de index, noemen we de remove_first_node() anders gaan we naar het ene knooppunt ervoor dat we willen verwijderen met behulp van de while-lus. Daarna, als we uit de while-lus komen, controleren we dat huidige_knooppunt is gelijk aan Geen zo niet, dan maken we de volgende van de huidige_node gelijk aan de volgende van de node die we willen verwijderen, anders drukken we het bericht af Index niet aanwezig omdat huidig_knooppunt is gelijk aan Geen.
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'>)> |
>
>
Verwijder een gekoppeld lijstknooppunt van bepaalde gegevens
Deze methode verwijdert het knooppunt met de opgegeven gegevens uit de gekoppelde lijst. Bij deze methode hebben we eerst een huidig_knooppunt gelijk aan de hoofd en voer een herhalingslus om de gekoppelde lijst te doorlopen. Deze while-lus breekt wanneer huidig_knooppunt wordt Geen of de gegevens naast het huidige knooppunt zijn gelijk aan de gegevens die in het argument zijn opgegeven. Nu, nadat ik uit de lus ben gekomen als de huidig_knooppunt is gelijk aan Geen het betekent dat het knooppunt niet aanwezig is in de gegevens en dat we gewoon terugkeren, en als de gegevens naast de huidig_knooppunt gelijk is aan de gegeven gegevens, dan verwijderen we dat knooppunt door het volgende van dat verwijderde_knooppunt naar het volgende van het huidige_knooppunt te maken. En dit wordt geïmplementeerd met behulp van de if else-voorwaarde.
Python3
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> |
>
>
Gekoppelde lijsttraversal in Python
Deze methode doorloopt de gekoppelde lijst en drukt de gegevens van elk knooppunt af. Bij deze methode hebben we een huidig_knooppunt gelijk aan de hoofd en doorloop de gekoppelde lijst met behulp van a herhalingslus tot de huidig_knooppunt wordt Geen en druk de gegevens af van huidig_knooppunt in elke iteratie en maak de huidig_knooppunt ernaast.
Java-lijst van
Python3
nginx
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Krijg de lengte van een gekoppelde lijst in Python
Deze methode retourneert de grootte van de gekoppelde lijst. Bij deze methode hebben we een teller geïnitialiseerd 'maat' met 0, en als de kop niet gelijk is aan Geen doorlopen we de gekoppelde lijst met behulp van a herhalingslus en verhoog de maat met 1 in elke iteratie en retourneer de grootte wanneer huidig_knooppunt wordt Niemand anders wij retourneren 0.
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> |
>
>
Voorbeeld van de gekoppelde lijst in Python
In dit voorbeeld hebben we, na het definiëren van de klasse Node en LinkedList, een gekoppelde lijst gemaakt met de naam lijst met behulp van de gekoppelde lijstklasse en voeg vervolgens vier knooppunten met tekengegevens in ‘a’, ‘b’, ‘c’, ‘d’ En 'G' in de gekoppelde lijst, dan drukken we de gekoppelde lijst af met behulp van printLL() methode gekoppelde lijstklasse daarna hebben we enkele knooppunten verwijderd met behulp van verwijdermethoden en druk vervolgens de gekoppelde lijst opnieuw af en we kunnen in de uitvoer zien dat het knooppunt met succes is verwijderd. Daarna printen we ook de grootte van de gekoppelde lijst.
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())> |
>
>Uitvoer
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>