V tomto článku sa dozvieme o implementácii prepojeného zoznamu v Python . Na implementáciu prepojeného zoznamu v Pythone použijeme triedy v Pythone . Teraz vieme, že prepojený zoznam pozostáva z uzlov a uzly majú dva prvky, t. j. údaje a odkaz na iný uzol. Najprv implementujme uzol.
Čo je prepojený zoznam v Pythone
Prepojený zoznam je typ lineárnej dátovej štruktúry podobnej poliam. Je to súbor uzlov, ktoré sú navzájom prepojené. Uzol obsahuje dve veci, prvé sú dáta a druhé je prepojenie, ktoré ho spája s iným uzlom. Nižšie je uvedený príklad prepojeného zoznamu so štyrmi uzlami a každý uzol obsahuje znakové údaje a prepojenie na iný uzol. Náš prvý uzol je kde hlavu body a môžeme pristupovať ku všetkým prvkom prepojeného zoznamu pomocou hlavu.
Prepojený zoznam
Vytvorenie prepojeného zoznamu v Pythone
V tejto triede LinkedList použijeme triedu Node na vytvorenie prepojeného zoznamu. V tejto triede máme __horúce__ metóda, ktorá inicializuje prepojený zoznam s prázdnou hlavou. Ďalej sme vytvorili insertAtBegin() metóda na vloženie uzla na začiatok prepojeného zoznamu, an insertAtIndex() metóda na vloženie uzla do daného indexu prepojeného zoznamu a insertAtEnd() metóda vloží uzol na koniec prepojeného zoznamu. Po tom máme remove_node() metóda, ktorá berie údaje ako argument na odstránenie tohto uzla. V remove_node() metódou prechádzame prepojeným zoznamom, ak je prítomný uzol rovný údajom, potom tento uzol vymažeme z prepojeného zoznamu. Potom máme sizeOfLL() metóda na získanie aktuálnej veľkosti prepojeného zoznamu a posledná metóda triedy LinkedList je printLL() ktorý prechádza prepojeným zoznamom a vytlačí údaje každého uzla.
Vytvorenie triedy uzlov
Vytvorili sme triedu Node, v ktorej sme definovali a __horúce__ funkcia na inicializáciu uzla s údajmi odovzdanými ako argument a odkaz s None, pretože ak máme iba jeden uzol, potom v jeho odkaze nie je nič.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
java hashmap
>
>
Vloženie do prepojeného zoznamu
Vloženie na začiatku do prepojeného zoznamu
Táto metóda vloží uzol na začiatok prepojeného zoznamu. Pri tejto metóde vytvoríme a nový_uzol s daným údajov a skontrolujte, či je hlava prázdnym uzlom alebo nie, ak je hlava prázdna, potom urobíme nový_uzol ako hlavu a vrátiť inak vložíme hlavu na ďalšie nový_uzol a urobte hlavu rovná nový_uzol.
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> |
>
>
Vložte uzol na konkrétnu pozíciu v prepojenom zozname
Táto metóda vloží uzol na daný index v prepojenom zozname. Pri tejto metóde vytvoríme a nový_uzol s danými údajmi, aktuálny_uzol, ktorý sa rovná hlave, a počítadlo 'pozícia' inicializuje sa s 0. Teraz, ak je index rovný nule, znamená to, že uzol sa má vložiť na začiatok, ako sme zavolali metóda insertAtBegin(). inak spustíme slučku while až do aktuálny_uzol sa nerovná žiadne alebo (pozícia + 1) sa nerovná indexu, ktorý musíme na jednej pozícii späť vložiť na danú pozíciu, aby sme vytvorili prepojenie uzlov a v každej iterácii zväčšíme pozíciu o 1 a vytvoríme aktuálny_uzol ďalší z toho. Keď sa slučka pretrhne a ak aktuálny_uzol sa nerovná žiadne vložíme nový_uzol na za do aktuálny_uzol. Ak aktuálny_uzol rovná sa žiadne znamená to, že index sa v zozname nenachádza a tlačíme Index nie je prítomný.
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'>)> |
>
>
Vloženie do prepojeného zoznamu na konci
Táto metóda vloží uzol na koniec prepojeného zoznamu. Pri tejto metóde vytvoríme a nový_uzol s danými údajmi a skontrolujte, či hlavu je prázdny uzol alebo nie, ak hlavu je prázdny, potom urobíme nový_uzol ako hlavu a vrátiť inak robíme a current_node rovný do hlava traverz do posledného uzol prepojeného zoznamu a kedy dostaneme žiadne za uzlom current_node sa slučka while preruší a vloží sa nový_uzol v ďalšom z aktuálny_uzol čo je posledný uzol prepojeného zoznamu.
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> |
>
>
Aktualizujte uzol prepojeného zoznamu
Tento kód definuje metódu s názvom updateNode v triede prepojeného zoznamu. Používa sa na aktualizáciu hodnoty uzla na danej pozícii v prepojenom zozname.
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'>)> |
>
>
Odstrániť uzol v prepojenom zozname
Odstráňte prvý uzol z prepojeného zoznamu
Táto metóda odstráni prvý uzol prepojeného zoznamu jednoduchým vytvorením druhého uzla hlavu prepojeného zoznamu.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Odstrániť posledný uzol z prepojeného zoznamu
Pri tejto metóde vymažeme posledný uzol. Najprv prejdeme do predposledného uzla pomocou cyklu while a potom urobíme ďalší z tohto uzla žiadne a posledný uzol bude odstránený.
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> |
>
>
Odstráňte uzol prepojeného zoznamu na danej pozícii
V tejto metóde odstránime uzol na danom indexe, táto metóda je podobná a insert_at_inded() metóda. Pri tejto metóde, ak hlavu je žiadne my jednoducho vrátiť inak inicializujeme a aktuálny_uzol s seba.hlava a pozíciu s 0. Ak sa pozícia rovná indexu, ktorý sme nazvali remove_first_node() inak prejdeme k predchádzajúcemu uzlu, ktorý chceme odstrániť, pomocou cyklu while. Potom, keď vyjdeme zo slučky while, skontrolujeme že aktuálny_uzol rovná sa žiadne ak nie, potom urobíme, aby sa ďalší z aktuálny_uzol rovnal ďalšiemu z uzla, ktorý chceme odstrániť, inak správu vytlačíme Index nie je prítomný pretože aktuálny_uzol rovná sa žiadne.
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'>)> |
>
>
Odstráňte uzol prepojeného zoznamu pre dané údaje
Táto metóda odstráni uzol s danými údajmi z prepojeného zoznamu. Pri tejto metóde sme najprv urobili a aktuálny_uzol rovná sa hlavu a spustiť a pričom slučka na prechádzanie prepojeného zoznamu. Táto slučka while sa preruší, keď aktuálny_uzol sa stáva žiadne alebo údaje vedľa aktuálneho uzla sa rovnajú údajom uvedeným v argumente. Teraz, po vystúpení zo slučky, ak aktuálny_uzol rovná sa žiadne to znamená, že uzol nie je prítomný v dátach a my sa len vrátime, a ak dáta vedľa aktuálny_uzol sa rovná daným údajom, potom tento uzol odstránime tak, že ďalší z tohto odstráneného_uzla urobíme nasledujúci z aktuálneho_uzla. A to sa implementuje pomocou podmienky 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> |
>
>
Prechádzanie prepojeného zoznamu v Pythone
Táto metóda prechádza prepojeným zoznamom a vytlačí údaje každého uzla. Pri tejto metóde sme urobili a aktuálny_uzol rovná sa hlavu a iterujte cez prepojený zoznam pomocou a pričom slučka až pokým aktuálny_uzol zmeniť na Žiadne a vytlačiť údaje z aktuálny_uzol v každej iterácii a urobte aktuálny_uzol vedľa toho.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Získajte dĺžku prepojeného zoznamu v Pythone
Táto metóda vráti veľkosť prepojeného zoznamu. Pri tejto metóde sme inicializovali počítadlo 'veľkosť' s 0, a ak sa hlavička nerovná žiadnej, prechádzame prepojeným zoznamom pomocou a pričom slučka a zvýšiť veľkosť s 1 v každej iterácii a vrátiť veľkosť, keď aktuálny_uzol sa stáva Žiadna iná vraciame 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> |
>
zoznam fontov gimp
>
Príklad prepojeného zoznamu v Pythone
V tomto príklade sme po definovaní triedy Node a LinkedList vytvorili prepojený zoznam s názvom llist pomocou triedy prepojeného zoznamu a potom vložte štyri uzly so znakovými údajmi 'a B C d' a „g“ v prepojenom zozname potom vytlačíme prepojený zoznam pomocou printLL() trieda zoznamu prepojených metód potom sme odstránili niektoré uzly pomocou metód odstránenia a potom znova vytlačte prepojený zoznam a vo výstupe vidíme, že uzol bol úspešne odstránený. Potom vytlačíme aj veľkosť prepojeného zoznamu.
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())> |
>
>Výkon
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>