V tem članku bomo spoznali implementacijo povezanega seznama v Python . Za izvedbo povezanega seznama v Pythonu bomo uporabili razrede v Pythonu . Zdaj vemo, da je povezan seznam sestavljen iz vozlišč, vozlišča pa imajo dva elementa, tj. podatke in sklic na drugo vozlišče. Najprej implementirajmo vozlišče.
Kaj je povezan seznam v Pythonu
Povezan seznam je vrsta linearne podatkovne strukture, podobne nizom. Je zbirka vozlišč, ki so med seboj povezana. Vozlišče vsebuje dve stvari, najprej so podatki, drugo pa je povezava, ki ga povezuje z drugim vozliščem. Spodaj je primer povezanega seznama s štirimi vozlišči in vsako vozlišče vsebuje znakovne podatke in povezavo do drugega vozlišča. Naše prvo vozlišče je kje glavo točke in lahko dostopamo do vseh elementov povezanega seznama z uporabo glavo.
Povezan seznam
Ustvarjanje povezanega seznama v Pythonu
V tem razredu LinkedList bomo uporabili razred Node za ustvarjanje povezanega seznama. V tem razredu imamo __vroče__ metoda, ki inicializira povezani seznam s prazno glavo. Nato smo ustvarili vstaviNaZačetek() metoda za vstavljanje vozlišča na začetek povezanega seznama, an vstaviAtIndex() metoda za vstavljanje vozlišča na dani indeks povezanega seznama in vstaviNaKonec() metoda vstavi vozlišče na konec povezanega seznama. Po tem imamo odstrani_vozlišče() metoda, ki vzame podatke kot argument za brisanje tega vozlišča. V odstrani_vozlišče() metodo prečkamo povezani seznam, če je prisotno vozlišče enako podatkom, potem to vozlišče izbrišemo s povezanega seznama. Potem imamo velikostOfLL() metoda za pridobitev trenutne velikosti povezanega seznama in zadnja metoda razreda LinkedList je printLL() ki prečka povezani seznam in natisne podatke vsakega vozlišča.
Ustvarjanje razreda vozlišča
Ustvarili smo razred Node, v katerem smo definirali a __vroče__ funkcijo za inicializacijo vozlišča s podatki, posredovanimi kot argument in referenco z None, ker če imamo samo eno vozlišče, potem v njegovem sklicu ni ničesar.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Vstavljanje v povezani seznam
Vstavljanje na začetek povezanega seznama
Ta metoda vstavi vozlišče na začetek povezanega seznama. Pri tej metodi ustvarimo a novo_vozlišče z danim podatke in preverimo, ali je glava prazno vozlišče ali ne, če je glava prazna, naredimo novo_vozlišče kot glavo in vrnitev drugače vstavimo glavo na naslednjo novo_vozlišče in naredite glavo enako novo_vozlišče.
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> |
>
>
Vstavite vozlišče na določeno mesto na povezanem seznamu
Ta metoda vstavi vozlišče na danem indeksu na povezanem seznamu. Pri tej metodi ustvarimo a novo_vozlišče z danimi podatki, trenutnim_vozliščem, ki je enako glavi, in števcem 'položaj' inicializira z 0. Zdaj, če je indeks enak nič, to pomeni, da je treba vozlišče vstaviti na začetku, zato smo poklicali metoda insertAtBegin(). drugače izvajamo zanko medtem, dokler trenutno_vozlišče ni enako Noben oz (položaj+1) ni enak indeksu, ki ga moramo na eno pozicijo nazaj, da vstavimo na dano pozicijo, da naredimo povezavo vozlišč in v vsaki ponovitvi povečamo pozicijo za 1 in naredimo trenutno_vozlišče poleg tega. Ko se zanka prekine in če trenutno_vozlišče ni enako Noben vstavimo new_node na za trenutno_vozlišče. če trenutno_vozlišče je enako Noben pomeni, da indeksa ni na seznamu in natisnemo Indeks ni prisoten.
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'>)> |
>
>
Vstavljanje v povezani seznam na koncu
Ta metoda vstavi vozlišče na konec povezanega seznama. Pri tej metodi ustvarimo a novo_vozlišče z navedenimi podatki in preverite, če glavo je prazno vozlišče ali ne, če je glavo je prazen, potem naredimo novo_vozlišče kot glavo in vrnitev drugače naredimo a trenutno_vozlišče enako do glava prečkati do zadnjega vozlišče povezanega seznama in ko dobimo Noben po current_node se zanka while prekine in vstavi novo_vozlišče v naslednjem od trenutno_vozlišče ki je zadnje vozlišče povezanega seznama.
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> |
>
>
Posodobite vozlišče povezanega seznama
Ta koda definira metodo z imenom updateNode v razredu povezanega seznama. Uporablja se za posodobitev vrednosti vozlišča na danem mestu na povezanem seznamu.
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'>)> |
>
>
Izbrišite vozlišče na povezanem seznamu
Odstranite prvo vozlišče s povezanega seznama
Ta metoda odstrani prvo vozlišče povezanega seznama preprosto tako, da ustvari drugo vozlišče glavo povezanega seznama.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Odstrani zadnje vozlišče s povezanega seznama
Pri tej metodi bomo izbrisali zadnje vozlišče. Najprej gremo do predzadnjega vozlišča z uporabo zanke while, nato pa iz tega vozlišča naredimo naslednje Noben in zadnje vozlišče bo odstranjeno.
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> |
>
>
Izbrišite vozlišče povezanega seznama na danem položaju
Pri tej metodi bomo odstranili vozlišče na danem indeksu, ta metoda je podobna the insert_at_inded() metoda. Pri tej metodi, če glavo je Noben mi preprosto vrnitev drugače inicializiramo a trenutno_vozlišče z sam.glava in položaj z 0. Če je položaj enak indeksu, ki smo ga imenovali odstrani_prvo_vozlišče() drugače preidemo do enega vozlišča pred tem, ki ga želimo odstraniti z uporabo zanke while. Po tem, ko izstopimo iz zanke while, preverimo to trenutno_vozlišče je enako Noben če ne, naredimo naslednje od trenutnega_vozlišča enako naslednjemu od vozlišča, ki ga želimo odstraniti, drugače natisnemo sporočilo Indeks ni prisoten Ker trenutno_vozlišče je enako Noben.
Python3
xd pomen
# 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'>)> |
>
>
Izbrišite vozlišče povezanega seznama danih podatkov
Ta metoda odstrani vozlišče z danimi podatki s povezanega seznama. Pri tej metodi smo najprej naredili a trenutno_vozlišče enako glavo in zaženite a medtem ko zanka za prečkanje povezanega seznama. Ta zanka medtem se prekine, ko trenutno_vozlišče postane Noben ali so podatki poleg trenutnega vozlišča enaki podatkom, podanim v argumentu. Zdaj, ko je prišel iz zanke, če je trenutno_vozlišče je enako Noben to pomeni, da vozlišče ni prisotno v podatkih in se samo vrnemo, in če so podatki poleg trenutno_vozlišče je enako danim podatkom, potem to vozlišče odstranimo tako, da naslednje od tega odstranjenega_vozlišča postavimo na naslednjega od trenutnega_vozlišča. In to se izvede z uporabo pogoja 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> |
>
>
Prehod povezanega seznama v Pythonu
Ta metoda prečka povezani seznam in natisne podatke vsakega vozlišča. Pri tej metodi smo naredili a trenutno_vozlišče enaka glavo in ponovite po povezanem seznamu z uporabo a medtem ko zanka do trenutno_vozlišče postane None in natisne podatke trenutno_vozlišče v vsaki ponovitvi in naredite trenutno_vozlišče zraven.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Pridobite dolžino povezanega seznama v Pythonu
Ta metoda vrne velikost povezanega seznama. Pri tej metodi smo inicializirali števec 'velikost' z 0 in nato, če glava ni enaka Brez, prečkamo povezani seznam z uporabo a medtem ko zanka in povečati velikost z 1 v vsaki ponovitvi in vrne velikost, ko trenutno_vozlišče postane Nihče drug vrnemo 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> |
>
>
Primer povezanega seznama v Pythonu
V tem primeru smo po definiranju razreda Node in LinkedList ustvarili povezan seznam z imenom lllist z uporabo razreda povezanega seznama in nato vstavite štiri vozlišča z znakovnimi podatki 'a', 'b', 'c', 'd' in 'g' na povezanem seznamu, potem natisnemo povezani seznam z uporabo printLL() razred povezanega seznama z metodo, po tem smo z metodami odstranili nekaj vozlišč in nato znova natisnite povezani seznam in v izhodu lahko vidimo, da je vozlišče uspešno izbrisano. Nato natisnemo še velikost povezanega seznama.
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())> |
>
>Izhod
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>