Šiame straipsnyje sužinosime apie susieto sąrašo įgyvendinimą Python . Norėdami įdiegti susietą sąrašą Python, naudosime klasės Python . Dabar žinome, kad susietą sąrašą sudaro mazgai, o mazgai turi du elementus, ty duomenis ir nuorodą į kitą mazgą. Pirmiausia įgyvendinkime mazgą.
Kas yra susietų sąrašas Python
Susietas sąrašas yra linijinės duomenų struktūros tipas, panašus į masyvus. Tai mazgų, susietų vienas su kitu, rinkinys. Mazgą sudaro du dalykai, pirma, duomenys, o antrasis – saitas, jungiantis jį su kitu mazgu. Toliau pateikiamas susieto sąrašo su keturiais mazgais pavyzdys, kiekviename mazge yra simbolių duomenys ir nuoroda į kitą mazgą. Mūsų pirmasis mazgas yra kur galva taškus ir galime pasiekti visus susieto sąrašo elementus naudodami galva.
Susietas sąrašas
Susieto sąrašo kūrimas Python
Šioje „LinkedList“ klasėje mes naudosime „Node“ klasę, kad sukurtume susietą sąrašą. Šioje klasėje mes turime __karšta__ metodas, kuris inicijuoja susietą sąrašą tuščia galvute. Toliau sukūrėme an insertAtBegin() būdas įterpti mazgą susieto sąrašo pradžioje, an insertAtIndex() būdas įterpti mazgą į nurodytą susieto sąrašo indeksą ir insertAtEnd() metodas įterpia mazgą susieto sąrašo pabaigoje. Po to mes turime pašalinti_mazgas() metodas, kuris ima duomenis kaip argumentą, kad pašalintų tą mazgą. Viduje pašalinti_mazgas() Metodas perkeliame susietą sąrašą, jei mazgas yra lygus duomenims, tada tą mazgą pašaliname iš susieto sąrašo. Tada mes turime dydisOfLL() būdas gauti dabartinį susieto sąrašo dydį ir paskutinis LinkedList klasės metodas printLL() kuri eina per susietą sąrašą ir spausdina kiekvieno mazgo duomenis.
Mazgo klasės kūrimas
Sukūrėme Node klasę, kurioje apibrėžėme a __karšta__ funkcija inicijuoti mazgą su duomenimis, perduotais kaip argumentas ir nuoroda su None, nes jei turime tik vieną mazgą, tada jo nuorodoje nieko nėra.
Python3
kaip pervardyti katalogą Linux
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Įterpimas į susietų sąrašą
Įterpimas susieto sąrašo pradžioje
Šis metodas įterpia mazgą susieto sąrašo pradžioje. Šiuo metodu sukuriame a naujas_mazgas su duotu duomenis ir patikrinkite, ar galvutė yra tuščias mazgas, ar ne, jei galva tuščia, tada padarome naujas_mazgas kaip galva ir grąžinti kitu atveju įkišame galvą į kitą naujas_mazgas ir padaryti galva lygus naujas_mazgas.
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> |
>
>
Įtraukite mazgą konkrečioje pozicijoje susietame sąraše
Šis metodas įterpia mazgą nurodytame indekse į susietą sąrašą. Šiuo metodu sukuriame a naujas_mazgas su nurodytais duomenimis , srovės_mazgas, lygus galvutei, ir skaitiklis 'pozicija' inicijuoja su 0. Dabar, jei indeksas yra lygus nuliui, tai reiškia, kad mazgas turi būti įterptas pradžioje, todėl mes vadiname insertAtBegin() metodas kitaip mes paleidžiame o kilpą, kol dabartinis_mazgas nėra lygus Nė vienas arba (pozicija+1) nėra lygus indeksui, kurį turime vienoje pozicijoje įterpti tam tikroje padėtyje, kad būtų galima susieti mazgus, ir kiekvienoje iteracijoje padėtį padidiname 1 ir padarome dabartinis_mazgas šalia jo. Kai nutrūksta kilpa ir jei dabartinis_mazgas nėra lygus Nė vienas įterpiame new_node at after į dabartinis_mazgas. Jeigu dabartinis_mazgas yra lygus Nė vienas tai reiškia, kad indekso sąraše nėra ir mes spausdiname Indekso nėra.
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'>)> |
>
>
Įterpimas į susietą sąrašą pabaigoje
Šis metodas įterpia mazgą susieto sąrašo pabaigoje. Šiuo metodu sukuriame a naujas_mazgas su pateiktais duomenimis ir patikrinkite, ar galva yra tuščias mazgas, ar ne, jei galva yra tuščias, tada padarome naujas_mazgas kaip galva ir grąžinti Kitas darome a dabartinis_mazgas lygus į vadovas pereiti į paskutinį mazgas susieto sąrašo ir kada gausime Nė vienas po current_node nutrūksta while ciklas ir įterpiamas naujas_mazgas kitame iš dabartinis_mazgas kuris yra paskutinis susieto sąrašo mazgas.
Python3
objektų lygybė 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> |
>
>
Atnaujinkite susieto sąrašo mazgą
Šis kodas apibrėžia metodą, vadinamą updateNode susieto sąrašo klasėje. Jis naudojamas tam tikroje susieto sąrašo pozicijoje esančio mazgo vertei atnaujinti.
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'>)> |
>
>
Ištrinkite mazgą susietame sąraše
Pašalinkite pirmąjį mazgą iš susietųjų sąrašo
Šis metodas pašalina pirmąjį susieto sąrašo mazgą tiesiog sukuriant antrąjį mazgą galva susieto sąrašo.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Pašalinkite paskutinį mazgą iš susietųjų sąrašo
Šiuo metodu ištrinsime paskutinį mazgą. Pirmiausia pereiname prie antrojo paskutinio mazgo naudodami while kilpą, o tada sukuriame kitą to mazgo Nė vienas ir paskutinis mazgas bus pašalintas.
Python3
java konvertuoti į eilutę
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> |
>
>
Ištrinkite susieto sąrašo mazgą tam tikroje pozicijoje
Šiuo metodu pašalinsime mazgą, esantį nurodytoje indekse, šis metodas yra panašus į į insert_at_inded() metodas. Taikant šį metodą, jei galva yra Nė vienas mes tiesiog grąžinti kitu atveju inicijuojame a dabartinis_mazgas su save.galva ir padėtis su 0. Jei padėtis yra lygi indeksui, kurį vadiname pašalinti_pirmas_mazgas() kitu metodu pereiname į vieną mazgą, prieš kurį norime pašalinti naudodami while kilpą. Po to, kai išeiname iš while ciklo, patikriname kad dabartinis_mazgas yra lygus Nė vienas jei ne, mes padarome sekantį dabartinį_mazgą lygų kitam mazgo, kurį norime pašalinti, kitu atveju išspausdiname pranešimą Indekso nėra nes dabartinis_mazgas yra lygus Nė vienas.
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'>)> |
>
>
Ištrinkite nurodytų duomenų susieto sąrašo mazgą
Šis metodas pašalina mazgą su nurodytais duomenimis iš susieto sąrašo. Šiuo metodu pirmiausia padarėme a dabartinis_mazgas lygus galva ir paleisti a o kilpa norėdami pereiti susietą sąrašą. Tai while kilpa nutrūksta, kai dabartinis_mazgas tampa Nė vienas arba šalia esamo mazgo esantys duomenys yra lygūs argumente nurodytiems duomenims. Dabar, išėjus iš kilpos, jei dabartinis_mazgas yra lygus Nė vienas tai reiškia, kad mazgo nėra duomenyse ir mes tiesiog grįžtame, o jei duomenys šalia dabartinis_mazgas yra lygus pateiktiems duomenims, tada pašaliname tą mazgą, kitą iš to pašalinto_mazgo paversdami sekančiu iš dabartinio_mazgo. Ir tai įgyvendinama naudojant sąlygą if else.
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> |
>
>
Susieto sąrašo peržiūra Python
Šis metodas eina per susietą sąrašą ir spausdina kiekvieno mazgo duomenis. Šiuo metodu padarėme a dabartinis_mazgas lygus galva ir kartokite susietą sąrašą naudodami a o kilpa iki dabartinis_mazgas tapkite Nėra ir išspausdinkite duomenis dabartinis_mazgas kiekvienoje iteracijoje ir padarykite dabartinis_mazgas šalia jo.
myflixr
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Gaukite susieto sąrašo ilgį Python
Šis metodas grąžina susieto sąrašo dydį. Šiuo metodu inicijavome skaitiklį 'dydis' su 0, o tada, jei galva nėra lygi Nėra, perkeliame susietą sąrašą naudodami a o kilpa ir padidinkite dydis su 1 kiekvienoje iteracijoje ir grąžinkite dydį, kai dabartinis_mazgas tampa Niekas kitas grąžiname 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> |
>
>
Python susieto sąrašo pavyzdys
Šiame pavyzdyje, apibrėžę Node ir LinkedList klasę, sukūrėme susietą sąrašą pavadinimu sąrašas naudodami susieto sąrašo klasę ir įterpkite keturis mazgus su simbolių duomenimis „a“, „b“, „c“, „d“ ir 'g' susietame sąraše, tada spausdiname susietą sąrašą naudodami printLL() su metodu susieto sąrašo klasė po to pašalinome kai kuriuos mazgus naudodami pašalinimo metodus ir vėl atspausdinkite susietą sąrašą ir išvestyje pamatysime, kad mazgas sėkmingai ištrintas. Po to taip pat atspausdiname susieto sąrašo dydį.
Python3
sąrašų rūšiavimas 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())> |
>
>Išvestis
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>