I den här artikeln kommer vi att lära oss om implementeringen av en länkad lista i Pytonorm . För att implementera den länkade listan i Python kommer vi att använda klasser i Python . Nu vet vi att en länkad lista består av noder och noder har två element, dvs data och en referens till en annan nod. Låt oss implementera noden först.
Vad är länkad lista i Python
En länkad lista är en typ av linjär datastruktur som liknar arrayer. Det är en samling noder som är länkade med varandra. En nod innehåller två saker för det första är data och för det andra är en länk som förbinder den med en annan nod. Nedan är ett exempel på en länkad lista med fyra noder och varje nod innehåller teckendata och en länk till en annan nod. Vår första nod är var huvud poäng och vi kan komma åt alla element i den länkade listan med hjälp av huvud.
Länkad lista
Skapa en länkad lista i Python
I den här klassen LinkedList kommer vi att använda klassen Node för att skapa en länkad lista. I den här klassen har vi en __varm__ metod som initierar den länkade listan med ett tomt huvud. Därefter har vi skapat en insertAtBegin() metod för att infoga en nod i början av den länkade listan, en insertAtIndex() metod för att infoga en nod vid det givna indexet för den länkade listan, och insertAtEnd() metod infogar en nod i slutet av den länkade listan. Efter det har vi remove_node() metod som tar data som ett argument för att ta bort den noden. I den remove_node() metod vi korsar den länkade listan om en nod är närvarande lika med data så tar vi bort den noden från den länkade listan. Då har vi sizeOfLL() metod för att få den aktuella storleken på den länkade listan och den sista metoden i klassen LinkedList är printLL() som går igenom den länkade listan och skriver ut data för varje nod.
Skapa en nodklass
Vi har skapat en Node-klass där vi har definierat en __varm__ funktion för att initiera noden med data som skickas som ett argument och en referens med None eftersom om vi bara har en nod så finns det ingenting i dess referens.
Python3
numrering av alfabetet
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Infogning i länkad lista
Infogning vid början i länkad lista
Denna metod infogar noden i början av den länkade listan. I denna metod skapar vi en ny_nod med det givna data och kontrollera om huvudet är en tom nod eller inte om huvudet är tomt så gör vi ny_nod som huvud och lämna tillbaka annars sätter vi in huvudet vid nästa ny_nod och göra huvud lika med ny_nod.
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> |
>
>
Infoga en nod på en specifik position i en länkad lista
Denna metod infogar noden vid det givna indexet i den länkade listan. I denna metod skapar vi en ny_nod med givna data, en aktuell_nod som är lika med huvudet och en räknare 'placera' initieras med 0. Nu, om indexet är lika med noll betyder det att noden ska infogas i början så vi anropade insertAtBegin() metod annars kör vi en stund loop tills aktuell_nod är inte lika med Ingen eller (position+1) är inte lika med indexet vi måste vid en position tillbaka för att infoga vid en given position för att göra länkningen av noder och i varje iteration ökar vi positionen med 1 och gör aktuell_nod nästa av det. När slingan går sönder och om aktuell_nod är inte lika med Ingen vi infogar new_node vid efter till aktuell_nod. Om aktuell_nod är lika med Ingen det betyder att indexet inte finns i listan och vi skriver ut Index saknas.
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'>)> |
>
>
Infogning i länkad lista i slutet
Denna metod infogar noden i slutet av den länkade listan. I denna metod skapar vi en ny_nod med de givna uppgifterna och kontrollera om huvud är en tom nod eller inte om huvud är tom så gör vi den ny_nod som huvud och lämna tillbaka annan vi gör en nuvarande_nod lika till huvudet gå till det sista nod av den länkade listan och när vi får Ingen efter current_node bryter while-slingan och infogar ny_nod i nästa av aktuell_nod som är den sista noden i länkad lista.
Python3
np stoppning
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> |
>
>
Uppdatera noden för en länkad lista
Denna kod definierar en metod som kallas updateNode i en länkad listklass. Den används för att uppdatera värdet på en nod vid en given position i den länkade listan.
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'>)> |
>
>
Ta bort nod i en länkad lista
Ta bort första nod från länkad lista
Denna metod tar bort den första noden i den länkade listan genom att helt enkelt skapa den andra noden huvud av den länkade listan.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Ta bort sista nod från länkad lista
I den här metoden tar vi bort den sista noden. Först går vi till den näst sista noden med while-loopen, och sedan gör vi nästa av den noden Ingen och sista noden kommer att tas bort.
Python3
string.format java sträng
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> |
>
>
Ta bort en länkad listnod på en given position
I den här metoden kommer vi att ta bort noden vid det givna indexet, denna metod liknar de insert_at_inded() metod. I denna metod, om huvud är Ingen vi helt enkelt lämna tillbaka annars initierar vi en aktuell_nod med själv.huvud och placera med 0. Om positionen är lika med indexet kallade vi remove_first_node() metod annars går vi till den ena noden innan som vi vill ta bort med while-loopen. Efter det när vi kommer ur while-slingan kollar vi den aktuella_noden är lika med Ingen om inte så gör vi nästa av current_node lika med nästa av nod som vi vill ta bort annars skriver vi ut meddelandet Index saknas därför att aktuell_nod är lika 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'>)> |
>
>
Ta bort en länkad listnod för en given data
Denna metod tar bort noden med givna data från den länkade listan. I den här metoden gjorde vi först en aktuell_nod lika med huvud och kör a medan loop för att gå igenom den länkade listan. Detta medan loop bryter när aktuell_nod blir Ingen eller så är data bredvid den aktuella noden lika med data som ges i argumentet. Nu, efter att ha kommit ut ur slingan om aktuell_nod är lika med Ingen det betyder att noden inte är närvarande i data och vi bara återvänder, och om data bredvid aktuell_nod är lika med den data som ges så tar vi bort den noden genom att göra nästa av den remove_node till nästa av current_node. Och detta implementeras med hjälp av if else-villkoret.
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
Denna metod går igenom den länkade listan och skriver ut data för varje nod. I denna metod gjorde vi en aktuell_nod lika med huvud och iterera genom den länkade listan med a medan loop tills aktuell_nod bli Ingen och skriv ut data för aktuell_nod i varje iteration och gör aktuell_nod bredvid den.
preg_match
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Få längden på en länkad lista i Python
Denna metod returnerar storleken på den länkade listan. I denna metod har vi initierat en räknare 'storlek' med 0, och sedan, om huvudet inte är lika med Ingen, går vi igenom den länkade listan med a medan loop och öka storlek med 1 i varje iteration och returnera storleken när aktuell_nod blir Ingen annan vi returnerar 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> |
>
>
Exempel på länkad lista i Python
I det här exemplet, efter att ha definierat klassen Node och LinkedList har vi skapat en länkad lista med namnet llista använda den länkade listklassen och infoga sedan fyra noder med teckendata 'a', 'b', 'c', 'd' och 'g' i den länkade listan så skriver vi ut den länkade listan med hjälp av printLL() metod länkad listklass efter det har vi tagit bort några noder med borttagningsmetoder och skriv sedan ut den länkade listan igen och vi kan se i utgången att noden har raderats framgångsrikt. Efter det skriver vi även ut storleken på den länkade listan.
java-anslutning
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())> |
>
>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>