V tomto článku se dozvíme o implementaci propojeného seznamu v Krajta . K implementaci propojeného seznamu v Pythonu použijeme třídy v Pythonu . Nyní víme, že propojený seznam se skládá z uzlů a uzly mají dva prvky, tj. data a odkaz na jiný uzel. Nejprve implementujeme uzel.

Co je Linked List v Pythonu

Propojený seznam je typ lineární datové struktury podobné polím. Je to soubor uzlů, které jsou vzájemně propojeny. Uzel obsahuje dvě věci, první jsou data a druhá je odkaz, který jej spojuje s jiným uzlem. Níže je uveden příklad propojeného seznamu se čtyřmi uzly a každý uzel obsahuje znaková data a odkaz na jiný uzel. Náš první uzel je kde hlava body a můžeme přistupovat ke všem prvkům propojeného seznamu pomocí hlava.

Spojový seznam

Vytvoření propojeného seznamu v Pythonu

V této třídě LinkedList použijeme třídu Node k vytvoření propojeného seznamu. V této třídě máme __horký__ metoda, která inicializuje propojený seznam s prázdnou hlavou. Dále jsme vytvořili insertAtBegin() metoda pro vložení uzlu na začátek propojeného seznamu, an insertAtIndex() metoda pro vložení uzlu na daný index propojeného seznamu a insertAtEnd() metoda vloží uzel na konec propojeného seznamu. Poté máme remove_node() metoda, která bere data jako argument pro odstranění tohoto uzlu. V remove_node() Procházíme propojený seznam, pokud je přítomen uzel rovný datům, pak tento uzel z propojeného seznamu odstraníme. Pak máme sizeOfLL() metoda pro získání aktuální velikosti propojeného seznamu a poslední metodou třídy LinkedList je printLL() který prochází propojeným seznamem a tiskne data každého uzlu.

Vytvoření třídy uzlů

Vytvořili jsme třídu Node, ve které jsme definovali a __horký__ funkce pro inicializaci uzlu s daty předanými jako argument a odkazem s None, protože pokud máme pouze jeden uzel, pak v jeho odkazu není nic.

Python3

class> Node:> > def> __init__(> self> , data):> > self> .data> => data> > self> .> next> => None>

Vložení do propojeného seznamu

Vložení na začátku do propojeného seznamu

Tato metoda vloží uzel na začátek propojeného seznamu. Při této metodě vytvoříme a nový_uzel s daným data a zkontrolujte, zda je hlava prázdný uzel nebo ne, pokud je hlava prázdná, pak uděláme nový_uzel tak jako hlava a vrátit se jinak vložíme hlavu na další nový_uzel a udělat hlava rovná nový_uzel.

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 uzel na konkrétní pozici v propojeném seznamu

Tato metoda vloží uzel na daný index v propojeném seznamu. Při této metodě vytvoříme a nový_uzel s danými daty , aktuálním uzlem, který se rovná hlavě, a čítačem 'pozice' inicializuje se s 0. Nyní, pokud je index roven nule, znamená to, že uzel má být vložen na začátek, jak jsme zavolali metoda insertAtBegin(). jinak spustíme smyčku while, dokud nebude aktuální_uzel se nerovná Žádný nebo (pozice+1) se nerovná indexu, který musíme na jedné pozici zpět vložit na danou pozici, abychom provedli propojení uzlů a v každé iteraci zvýšíme pozici o 1 a vytvoříme aktuální_uzel další z toho. Když se smyčka přeruší a pokud aktuální_uzel se nerovná Žádný vložíme nový_uzel na za do aktuální_uzel. Li aktuální_uzel je rovný Žádný to znamená, že index není v seznamu a tiskneme Index není k dispozici.

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žení do propojeného seznamu na konci

Tato metoda vloží uzel na konec propojeného seznamu. Při této metodě vytvoříme a nový_uzel s danými údaji a zkontrolujte, zda hlava je prázdný uzel nebo ne, pokud hlava je prázdný, pak uděláme nový_uzel tak jako hlava a vrátit se jiný děláme a aktuální_uzel rovný na hlava traverz do posledního uzel propojeného seznamu a kdy se dostaneme Žádný za uzel current_node se smyčka while přeruší a vloží se nový_uzel v dalším z aktuální_uzel což je poslední uzel propojeného seznamu.

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 uzel propojeného seznamu

Tento kód definuje metodu nazvanou updateNode ve třídě propojeného seznamu. Používá se k aktualizaci hodnoty uzlu na dané pozici v propojeném 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'> )>

Odstranit uzel v propojeném seznamu

Odebrat první uzel z propojeného seznamu

Tato metoda odstraní první uzel propojeného seznamu jednoduše vytvořením druhého uzlu hlava z propojeného seznamu.

Python3

def> remove_first_node(> self> ):> > if> (> self> .head> => => None> ):> > return> > > self> .head> => self> .head.> next>

Odebrat poslední uzel z propojeného seznamu

Při této metodě odstraníme poslední uzel. Nejprve přejdeme k předposlednímu uzlu pomocí cyklu while a poté vytvoříme další z tohoto uzlu Žádný a poslední uzel bude odstraněn.

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>

Odstranit uzel propojeného seznamu na dané pozici

V této metodě odstraníme uzel na daném indexu, tato metoda je podobná a insert_at_inded() metoda. V této metodě, pokud hlava je Žádný my prostě vrátit se jinak inicializujeme a aktuální_uzel s sebe.hlava a pozice s 0. Pokud je pozice rovna indexu, který nazýváme remove_first_node() metoda jinak přejdeme k předchozímu uzlu, který chceme odstranit, pomocí cyklu while. Poté, když opustíme smyčku while, zkontrolujeme ten aktuální_uzel je rovný Žádný pokud ne, uděláme další z aktuálního_uzlu rovným dalšímu z uzlu, který chceme odstranit, jinak zprávu vytiskneme Index není k dispozici protože aktuální_uzel je rovný Žádný.

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'> )>

Odstraňte uzel propojeného seznamu daných dat

Tato metoda odstraní uzel s danými daty z propojeného seznamu. Při této metodě jsme nejprve vytvořili a aktuální_uzel rovná se hlava a spustit a zatímco smyčka k procházení propojeného seznamu. Tato smyčka while se přeruší, když aktuální_uzel se stává Žádný nebo data vedle aktuálního uzlu se rovnají datům uvedeným v argumentu. Nyní, Po opuštění smyčky, pokud aktuální_uzel je rovný Žádný to znamená, že uzel není přítomen v datech a my se jen vrátíme, a pokud data vedle aktuální_uzel se rovná zadaným datům, pak tento uzel odstraníme tím, že uděláme další z odstraněného_uzlu na další z aktuálního_uzlu. A to je implementováno pomocí podmínky 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>

Procházení propojeného seznamu v Pythonu

Tato metoda prochází propojeným seznamem a tiskne data každého uzlu. Při této metodě jsme vytvořili a aktuální_uzel rovná se hlava a iterujte propojeným seznamem pomocí a zatímco smyčka až do aktuální_uzel změnit na Žádný a vytisknout data z aktuální_uzel v každé iteraci a vytvořte aktuální_uzel vedle toho.

Python3

def> printLL(> self> ):> > current_node> => self> .head> > while> (current_node):> > print> (current_node.data)> > current_node> => current_node.> next>

Získejte délku propojeného seznamu v Pythonu

Tato metoda vrátí velikost propojeného seznamu. V této metodě jsme inicializovali čítač 'velikost' s 0, a pokud se hlava nerovná žádné, projdeme propojený seznam pomocí a zatímco smyčka a zvýšit velikost s 1 v každé iteraci a vrátit velikost, když aktuální_uzel se stává Žádný jiný vracíme 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>

Příklad propojeného seznamu v Pythonu

V tomto příkladu jsme po definování třídy Node a LinkedList vytvořili propojený seznam s názvem llist pomocí třídy propojeného seznamu a poté vložte čtyři uzly se znakovými daty 'abeceda' a 'G' v propojeném seznamu pak vytiskneme propojený seznam pomocí printLL() třída seznamu propojených metod poté jsme odstranili některé uzly pomocí metod remove a poté znovu vytiskněte propojený seznam a ve výstupu vidíme, že uzel byl úspěšně odstraněn. Poté také vytiskneme velikost propojeného seznamu.

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ýstup

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