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>

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>

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