I denne artikel lærer vi om implementeringen af en linket liste i Python . For at implementere den linkede liste i Python, vil vi bruge klasser i Python . Nu ved vi, at en sammenkædet liste består af noder, og noder har to elementer, dvs. data og en reference til en anden node. Lad os implementere noden først.
Hvad er linket liste i Python
En linket liste er en type lineær datastruktur, der ligner arrays. Det er en samling af noder, der er forbundet med hinanden. En node indeholder to ting, for det første er data, og for det andet er et link, der forbinder det med en anden node. Nedenfor er et eksempel på en sammenkædet liste med fire noder, og hver node indeholder tegndata og et link til en anden node. Vores første knudepunkt er hvor hoved point, og vi kan få adgang til alle elementerne i den linkede liste ved hjælp af hoved.
Linket liste
Oprettelse af en linket liste i Python
I denne LinkedList-klasse vil vi bruge Node-klassen til at oprette en linket liste. I denne klasse har vi en __hed__ metode, der initialiserer den linkede liste med et tomt hoved. Dernæst har vi lavet en insertAtBegin() metode til at indsætte en node i begyndelsen af den linkede liste, en insertAtIndex() metode til at indsætte en node ved det givne indeks på den linkede liste, og insertAtEnd() metode indsætter en node i slutningen af den sammenkædede liste. Derefter har vi remove_node() metode, der tager dataene som et argument for at slette den node. I den remove_node() metode vi krydser den linkede liste, hvis en node er til stede lig med data, så sletter vi den node fra den linkede liste. Så har vi sizeOfLL() metode til at få den aktuelle størrelse på den linkede liste og den sidste metode i LinkedList-klassen er printLL() som krydser den sammenkædede liste og udskriver dataene for hver node.
Oprettelse af en nodeklasse
Vi har lavet en Node-klasse, hvor vi har defineret en __hed__ funktion til at initialisere noden med data sendt som et argument og en reference med Ingen, fordi hvis vi kun har én node, er der intet i dens reference.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Indsættelse i linket liste
Indsættelse ved start i linket liste
Denne metode indsætter noden i begyndelsen af den sammenkædede liste. I denne metode skaber vi en ny_node med det givne data og kontroller, om hovedet er en tom node eller ej, hvis hovedet er tomt, så laver vi ny_node som hoved og Vend tilbage ellers indsætter vi hovedet ved det næste ny_node og lave hoved svarende til ny_node.
Python3
mylivecricket
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> |
>
>
Indsæt en node på en bestemt position i en sammenkædet liste
Denne metode indsætter noden ved det givne indeks i den linkede liste. I denne metode skaber vi en ny_node med givne data, en nuværende_node, der er lig med hovedet, og en tæller 'position' initialiseres med 0. Nu, hvis indekset er lig med nul, betyder det, at knudepunktet skal indsættes ved begyndelsen, så vi kaldte insertAtBegin() metode ellers kører vi et stykke løkke indtil den nuværende_node er ikke lig med Ingen eller (position+1) er ikke lig med det indeks, vi skal på den ene position tilbage for at indsætte på en given position for at lave sammenkædningen af noder, og i hver iteration øger vi positionen med 1 og laver nuværende_node næste af det. Når løkken går i stykker og hvis nuværende_node er ikke lig med Ingen vi indsætter new_node ved efter til nuværende_node. Hvis nuværende_node er lig med Ingen det betyder, at indekset ikke er til stede på listen, og vi udskriver Indeks ikke til stede.
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'>)> |
>
>
Indsættelse i linket liste i slutningen
Denne metode indsætter noden i slutningen af den sammenkædede liste. I denne metode skaber vi en ny_node med de givne data og kontroller, om hoved er en tom node eller ej, hvis hoved er tom, så laver vi den ny_node som hoved og Vend tilbage andet vi laver en nuværende_node lig til hovedet gå til det sidste node af den linkede liste, og hvornår vi får Ingen efter current_node pauser while-løkken og indsæt ny_node i den næste af nuværende_node som er den sidste knude på den linkede 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> |
>
>
Opdater noden på en sammenkædet liste
Denne kode definerer en metode kaldet updateNode i en linket listeklasse. Det bruges til at opdatere værdien af en node på en given position i den sammenkædede liste.
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'>)> |
>
>
Slet node i en sammenkædet liste
Fjern første node fra linket liste
Denne metode fjerner den første node på den sammenkædede liste ved blot at lave den anden node hoved af den linkede liste.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
kerne java
>
Fjern sidste node fra linket liste
I denne metode vil vi slette den sidste node. Først krydser vi til den næstsidste node ved hjælp af while-løkken, og derefter laver vi den næste af den node Ingen og sidste node vil blive fjernet.
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> |
>
>
Slet en linket listeknude på en given position
I denne metode vil vi fjerne noden ved det givne indeks, denne metode ligner det insert_at_inded() metode. I denne metode, hvis hoved er Ingen vi simpelthen Vend tilbage ellers initialiserer vi en nuværende_node med selv.hoved og position med 0. Hvis positionen er lig med indekset, kaldte vi remove_first_node() metode ellers går vi til den ene node før, som vi ønsker at fjerne ved hjælp af while-løkken. Efter at når vi ud af while-løkken tjekker vi den aktuelle_node er lig med Ingen hvis ikke, så gør vi den næste af current_node lig med den næste af node, som vi vil fjerne, ellers udskriver vi beskeden Indeks ikke til stede fordi nuværende_node er lig med Ingen.
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'>)> |
>
>
Slet en linket listeknude for en given data
Denne metode fjerner noden med de givne data fra den sammenkædede liste. I denne metode lavede vi først en nuværende_node lig med hoved og løb en mens loop for at krydse den linkede liste. Denne mens loop bryder når nuværende_node bliver til Ingen eller dataene ved siden af den aktuelle node er lig med dataene givet i argumentet. Nu, efter at komme ud af løkken, hvis nuværende_node er lig med Ingen det betyder, at noden ikke er til stede i dataene, og vi vender bare tilbage, og hvis dataene ved siden af nuværende_node er lig med de angivne data, så fjerner vi den node ved at lave den næste af den fjernede_node til den næste af den nuværende_node. Og dette implementeres ved hjælp af if else-betingelsen.
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> |
>
>
Linked List Traversal i Python
Denne metode krydser den sammenkædede liste og udskriver dataene for hver node. I denne metode lavede vi en nuværende_node lig med hoved og gentag gennem den linkede liste ved hjælp af en mens loop indtil nuværende_node bliver Ingen og udskriv dataene for nuværende_node i hver iteration og lav nuværende_node ved siden af.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Få længden af en linket liste i Python
Denne metode returnerer størrelsen af den sammenkædede liste. I denne metode har vi initialiseret en tæller 'størrelse' med 0, og hvis hovedet ikke er lig med Ingen, krydser vi den sammenkædede liste ved hjælp af en mens loop og forøg størrelse med 1 i hver iteration og returner størrelsen når nuværende_node bliver til Ingen andre vi returnerer 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> |
>
>
Eksempel på den linkede liste i Python
I dette eksempel, efter at have defineret klassen Node og LinkedList, har vi oprettet en sammenkædet liste med navnet lliste ved hjælp af den linkede listeklasse og indsæt derefter fire noder med tegndata 'a', 'b', 'c', 'd' og 'g' i den linkede liste så udskriver vi den linkede liste vha printLL() metode linket listeklasse, efter at vi har fjernet nogle noder ved hjælp af fjernmetoder og udskriv derefter den linkede liste igen, og vi kan se i outputtet, at noden er slettet. Derefter udskriver vi også størrelsen på den linkede liste.
Python3
andet hvis java
# 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())> |
>
>Produktion
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>