Tässä artikkelissa opimme linkitetyn luettelon käyttöönotosta Python . Käytämme linkitetyn luettelon toteuttamiseksi Pythonissa luokat Pythonissa . Nyt tiedämme, että linkitetty luettelo koostuu solmuista ja solmuissa on kaksi elementtiä eli data ja viittaus toiseen solmuun. Toteutetaan solmu ensin.
Mikä on linkitetty luettelo Pythonissa
Linkitetty lista on eräänlainen lineaarinen tietorakenne, joka muistuttaa taulukoita. Se on kokoelma solmuja, jotka on linkitetty toisiinsa. Solmu sisältää kaksi asiaa, ensinnäkin dataa ja toiseksi linkin, joka yhdistää sen toiseen solmuun. Alla on esimerkki linkitetystä luettelosta, jossa on neljä solmua ja jokainen solmu sisältää merkkidataa ja linkin toiseen solmuun. Ensimmäinen solmumme on missä pää pisteitä ja voimme käyttää kaikkia linkitetyn luettelon elementtejä käyttämällä pää.
Linkitetty lista
Linkitetyn luettelon luominen Pythonissa
Tässä LinkedList-luokassa käytämme Node-luokkaa linkitetyn luettelon luomiseen. Tällä luokalla meillä on __kuuma__ menetelmä, joka alustaa linkitetyn luettelon tyhjällä otsikolla. Seuraavaksi olemme luoneet an insertAtBegin() menetelmä solmun lisäämiseksi linkitetyn luettelon alkuun, an insertAtIndex() menetelmä solmun lisäämiseksi linkitetyn luettelon annettuun hakemistoon, ja insertAtEnd() menetelmä lisää solmun linkitetyn luettelon loppuun. Sen jälkeen meillä on poista_solmu() menetelmä, joka käyttää dataa argumenttina kyseisen solmun poistamiseksi. Vuonna poista_solmu() -menetelmällä kuljemme linkitetyn luettelon läpi, jos solmu on yhtä suuri kuin data, poistamme kyseisen solmun linkitetystä luettelosta. Sitten meillä on sizeOfLL() menetelmä saada linkitetyn luettelon nykyinen koko ja LinkedList-luokan viimeinen menetelmä on printLL() joka kulkee linkitetyn luettelon läpi ja tulostaa kunkin solmun tiedot.
Solmuluokan luominen
Olemme luoneet Node-luokan, jossa olemme määrittäneet a __kuuma__ funktio alustaa solmun argumenttina välitetyillä tiedoilla ja viitteellä Ei mitään, koska jos meillä on vain yksi solmu, sen viitteessä ei ole mitään.
Python 3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Lisäys linkitettyyn luetteloon
Lisäys linkitetyn luettelon alussa
Tämä menetelmä lisää solmun linkitetyn luettelon alkuun. Tällä menetelmällä luomme a uusi_solmu annettujen kanssa tiedot ja tarkista, onko pää tyhjä solmu vai ei, jos pää on tyhjä, teemme uusi_solmu kuten pää ja palata muuten asetamme pään seuraavaan uusi_solmu ja tee pää yhtä kuin uusi_solmu.
Python 3
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> |
>
>
Lisää solmu linkitetyn luettelon tiettyyn kohtaan
Tämä menetelmä lisää solmun annetussa indeksissä linkitettyyn luetteloon. Tällä menetelmällä luomme a uusi_solmu annetuilla tiedoilla , nykyinen_solmu, joka on yhtä suuri kuin pää, ja laskuri 'asema' alustetaan kanssa 0. Nyt, jos indeksi on yhtä suuri kuin nolla, se tarkoittaa, että solmu on lisättävä alussa, joten kutsuimme insertAtBegin() -metodi muuten ajamme jonkin aikaa silmukka kunnes nykyinen_solmu ei ole yhtä suuri kuin Ei mitään tai (sijainti +1) ei ole yhtä suuri kuin indeksi, joka meidän on yhdessä paikassa takaisin lisättäväksesi tiettyyn kohtaan solmujen linkittämistä varten, ja jokaisessa iteraatiossa lisäämme sijaintia yhdellä ja teemme nykyinen_solmu sen seuraavaksi. Kun silmukka katkeaa ja jos nykyinen_solmu ei ole yhtä suuri kuin Ei mitään lisäämme new_node at after -kohtaan nykyinen_solmu. Jos nykyinen_solmu on yhtä suuri kuin Ei mitään se tarkoittaa, että indeksi ei ole luettelossa ja tulostamme Indeksiä ei ole.
Python 3
# 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'>)> |
>
>
Lisäys linkitettyyn luetteloon lopussa
Tämä menetelmä lisää solmun linkitetyn luettelon loppuun. Tällä menetelmällä luomme a uusi_solmu annetuilla tiedoilla ja tarkista, onko pää on tyhjä solmu vai ei, jos pää on tyhjä, teemme sen uusi_solmu kuten pää ja palata muu teemme a nykyinen_solmu yhtä suuri to pää kulkea viimeiseen asti solmu linkitetystä luettelosta ja milloin saamme Ei mitään nykyisen_solmun jälkeen while-silmukka katkeaa ja lisää uusi_solmu seuraavassa nykyinen_solmu joka on linkitetyn luettelon viimeinen solmu.
Python 3
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> |
>
>
Päivitä linkitetyn luettelon solmu
Tämä koodi määrittelee menetelmän nimeltä updateNode linkitetyssä luetteloluokassa. Sitä käytetään linkitetyn luettelon tietyssä kohdassa olevan solmun arvon päivittämiseen.
Python 3
# 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'>)> |
mylivericket
>
>
Poista solmu linkitetystä luettelosta
Poista ensimmäinen solmu linkitetystä luettelosta
Tämä menetelmä poistaa linkitetyn luettelon ensimmäisen solmun yksinkertaisesti tekemällä toisen solmun pää linkitetystä luettelosta.
Python 3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Poista viimeinen solmu linkitetystä luettelosta
Tässä menetelmässä poistamme viimeisen solmun. Ensin siirrymme toiseksi viimeiseen solmuun while-silmukkaa käyttäen ja sitten teemme tämän solmun seuraavan Ei mitään ja viimeinen solmu poistetaan.
Python 3
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> |
>
>
Poista linkitetyn luettelon solmu tietyssä paikassa
Tässä menetelmässä poistamme solmun annetusta indeksistä, tämä menetelmä on samanlainen kuin the insert_at_inded() menetelmä. Tässä menetelmässä, jos pää On Ei mitään me yksinkertaisesti palata muuten alustamme a nykyinen_solmu kanssa itse.pää ja asema kanssa 0. Jos sijainti on yhtä suuri kuin indeksi, jota kutsumme nimellä poista_ensimmäinen_solmu() menetelmä muussa tapauksessa kuljemme yhteen solmuun, jota ennen haluamme poistaa while-silmukan avulla. Sen jälkeen kun olemme poistuneet while-silmukasta, tarkistamme että nykyinen_solmu on yhtä suuri kuin Ei mitään jos ei, teemme nykyisen_solmun seuraavasta yhtä suureksi kuin sen solmun seuraava, jonka haluamme poistaa, muuten tulostamme viestin Indeksiä ei ole koska nykyinen_solmu on yhtä suuri kuin Ei mitään.
Python 3
# 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'>)> |
>
>
Poista tietyn datan linkitetyn luettelon solmu
Tämä menetelmä poistaa solmun annetuilla tiedoilla linkitetystä luettelosta. Tällä menetelmällä teimme ensin a nykyinen_solmu yhtä suuri kuin pää ja ajaa a kun silmukka linkitetyn luettelon läpi. Tämä while-silmukka katkeaa, kun nykyinen_solmu tulee Ei mitään tai nykyisen solmun vieressä oleva data on sama kuin argumentissa annettu data. Nyt, kun tuli ulos silmukasta, jos nykyinen_solmu on yhtä suuri kuin Ei mitään se tarkoittaa, että solmu ei ole läsnä tiedoissa ja palaamme vain, ja jos tiedot vieressä nykyinen_solmu on yhtä suuri kuin annettu data, niin poistamme kyseisen solmun tekemällä poistetun_solmun seuraavaksi nykyisen_solmun seuraavaksi. Ja tämä toteutetaan if else -ehdon avulla.
Python 3
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 Pythonissa
Tämä menetelmä kulkee linkitetyn luettelon läpi ja tulostaa kunkin solmun tiedot. Tällä menetelmällä teimme a nykyinen_solmu yhtä suuri kuin pää ja iteroi linkitetyn luettelon läpi käyttämällä a kun silmukka kunnes nykyinen_solmu muuttuu Ei mitään ja tulosta tiedot nykyinen_solmu jokaisessa iteraatiossa ja tee nykyinen_solmu sen vieressä.
Python 3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Hanki linkitetyn luettelon pituus Pythonissa
Tämä menetelmä palauttaa linkitetyn luettelon koon. Tässä menetelmässä olemme alustaneet laskurin 'koko' 0, ja sitten jos pää ei ole yhtä suuri kuin Ei mitään, kuljemme linkitetyn luettelon läpi käyttämällä a kun silmukka ja lisää koko 1 jokaisessa iteraatiossa ja palauta koko kun nykyinen_solmu tulee Ei kukaan muu palautamme 0.
Python 3
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> |
>
>
Esimerkki linkitetystä luettelosta Pythonissa
Tässä esimerkissä Node- ja LinkedList-luokan määrittämisen jälkeen olemme luoneet linkitetyn luettelon nimeltä lista käyttämällä linkitettyä luetteloluokkaa ja lisää sitten neljä solmua merkkitiedoilla 'a', 'b', 'c', 'd' ja 'g' linkitetyssä luettelossa, sitten tulostamme linkitetyn luettelon käyttämällä printLL() menetelmällä linkitetty listaluokka, jonka jälkeen olemme poistaneet joitain solmuja poistomenetelmillä ja tulosta sitten linkitetty luettelo uudelleen ja voimme nähdä lähdössä, että solmu on poistettu onnistuneesti. Tämän jälkeen tulostamme myös linkitetyn listan koon.
Python 3
# 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())> |
>
>Lähtö
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>