W tym artykule dowiemy się o implementacji połączonej listy w Pyton . Aby zaimplementować połączoną listę w Pythonie, użyjemy zajęcia w Pythonie . Teraz wiemy, że lista połączona składa się z węzłów, a węzły mają dwa elementy, tj. dane i odniesienie do innego węzła. Najpierw zaimplementujmy węzeł.
Co to jest lista połączona w Pythonie
Połączona lista to rodzaj liniowej struktury danych podobny do tablic. Jest to zbiór węzłów, które są ze sobą powiązane. Węzeł zawiera dwie rzeczy: pierwsza to dane, a druga to łącze łączące go z innym węzłem. Poniżej znajduje się przykład połączonej listy z czterema węzłami, a każdy węzeł zawiera dane znakowe i łącze do innego węzła. Nasz pierwszy węzeł to Where głowa punktów i możemy uzyskać dostęp do wszystkich elementów połączonej listy za pomocą głowa.
Połączona lista
Tworzenie połączonej listy w Pythonie
W tej klasie LinkedList użyjemy klasy Node do utworzenia połączonej listy. W tej klasie mamy __gorący__ metoda inicjująca połączoną listę z pustą głową. Następnie stworzyliśmy plik wstawAtBegin() metoda wstawiania węzła na początku połączonej listy, an wstawAtIndex() metoda wstawiania węzła pod danym indeksem połączonej listy oraz wstawAtEnd() Metoda wstawia węzeł na końcu połączonej listy. Po tym mamy usuń_węzeł() metoda, która przyjmuje dane jako argument do usunięcia tego węzła. w usuń_węzeł() metodą przechodzimy przez połączoną listę, jeśli obecny jest węzeł równy danym, następnie usuwamy ten węzeł z połączonej listy. Następnie mamy rozmiarOfLL() metodą uzyskania bieżącego rozmiaru połączonej listy, a ostatnią metodą klasy LinkedList jest drukujLL() który przechodzi przez połączoną listę i drukuje dane każdego węzła.
Tworzenie klasy węzła
Stworzyliśmy klasę Node, w której zdefiniowaliśmy a __gorący__ funkcja inicjująca węzeł danymi przekazanymi jako argument i referencja z None, ponieważ jeśli mamy tylko jeden węzeł, to nie ma nic w jego referencji.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Wstawienie na listę powiązaną
Wstawianie na początku na liście połączonej
Ta metoda wstawia węzeł na początku połączonej listy. W tej metodzie tworzymy nowy_węzeł z danym dane i sprawdzamy, czy głowa jest pustym węzłem, czy nie, czy głowa jest pusta, wtedy wykonujemy nowy_węzeł Jak głowa I powrót w przeciwnym razie wstawiamy głowę w następnym nowy_węzeł i zrób głowa równy nowy_węzeł.
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> |
>
>
Wstaw węzeł w określonej pozycji na połączonej liście
Ta metoda wstawia węzeł o podanym indeksie na połączonej liście. W tej metodzie tworzymy nowy_węzeł z podanymi danymi, bieżącym węzłem równym głowie i licznikiem 'pozycja' inicjuje za pomocą 0. Teraz, jeśli indeks jest równy zero, oznacza to, że węzeł ma zostać wstawiony na początku, więc wywołaliśmy metoda wstawAtBegin(). w przeciwnym razie uruchamiamy pętlę while, aż do bieżący węzeł nie jest równe Nic Lub (pozycja +1) nie jest równy indeksowi, który musimy w jednej pozycji z powrotem wstawić w danej pozycji, aby dokonać połączenia węzłów i w każdej iteracji zwiększamy pozycję o 1 i wykonujemy bieżący węzeł następny. Kiedy pętla się zepsuje i jeśli bieżący węzeł nie jest równe Nic wstawiamy new_node po do bieżący węzeł. Jeśli bieżący węzeł jest równe Nic oznacza to, że indeksu nie ma na liście i drukujemy Brak indeksu.
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'>)> |
>
>
Wstawienie do listy połączonej na końcu
Ta metoda wstawia węzeł na końcu połączonej listy. W tej metodzie tworzymy nowy_węzeł z podanymi danymi i sprawdź, czy głowa jest pustym węzłem, czy nie, jeśli głowa jest pusty, wówczas tworzymy nowy_węzeł Jak głowa I powrót w przeciwnym razie robimy bieżący węzeł równy Do głowa przejść do ostatniego węzeł połączonej listy i kiedy otrzymamy Nic po bieżącym węźle pętla while przerywa i wstawia nowy_węzeł w następnym bieżący_węzeł który jest ostatnim węzłem połączonej listy.
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> |
>
>
Zaktualizuj węzeł połączonej listy
Ten kod definiuje metodę o nazwie updateNode w klasie połączonej listy. Służy do aktualizacji wartości węzła na danej pozycji na połączonej liście.
mamta kulkarni aktor
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'>)> |
>
>
Usuń węzeł z połączonej listy
Usuń pierwszy węzeł z połączonej listy
Ta metoda usuwa pierwszy węzeł połączonej listy, po prostu tworząc drugi węzeł głowa z połączonej listy.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Usuń ostatni węzeł z połączonej listy
W tej metodzie usuniemy ostatni węzeł. Najpierw przechodzimy do drugiego od końca węzła za pomocą pętli while, a następnie tworzymy następny węzeł Nic i ostatni węzeł zostanie usunięty.
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> |
>
>
Usuń węzeł listy połączonej w danej pozycji
W tej metodzie usuniemy węzeł o podanym indeksie, metoda ta jest podobna do the wstaw_w_inded() metoda. W tej metodzie, jeśli głowa Jest Nic my po prostu powrót w przeciwnym razie inicjujemy a bieżący_węzeł z głowa I pozycja z 0. Jeśli pozycja jest równa indeksowi, który nazywamy usuń_pierwszy_węzeł() w przeciwnym razie przechodzimy do węzła znajdującego się wcześniej, który chcemy usunąć, za pomocą pętli while. Potem, kiedy wyjdziemy z pętli while, sprawdzamy ten bieżący_węzeł jest równe Nic jeśli nie, to następny z bieżącego_węzła będzie równy następnemu z węzłów, który chcemy usunąć, w przeciwnym razie wypiszemy wiadomość Brak indeksu ponieważ bieżący_węzeł jest równe Nic.
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'>)> |
>
>
Usuń węzeł listy połączonej danych
Metoda ta usuwa węzeł z podanymi danymi z połączonej listy. W tej metodzie najpierw zrobiliśmy bieżący_węzeł równy głowa i uruchom A pętla while aby przeglądać połączoną listę. Ta pętla while przerywa kiedy bieżący_węzeł staje się Nic lub dane obok bieżącego węzła są równe danym podanym w argumencie. Teraz, po wyjściu z pętli if bieżący węzeł jest równe Nic oznacza to, że węzła nie ma w danych i po prostu zwracamy, a jeśli dane obok bieżący_węzeł jest równy podanym danym, wówczas usuwamy ten węzeł, łącząc następny usunięty_węzeł z następnym bieżącym_węzłem. Jest to realizowane przy użyciu warunku 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> |
>
>
Przeglądanie połączonej listy w Pythonie
Ta metoda przegląda połączoną listę i drukuje dane każdego węzła. W tej metodzie wykonaliśmy bieżący_węzeł równy głowa i iteruj po połączonej liście za pomocą a pętla while dopóki bieżący_węzeł zmień na Brak i wydrukuj dane bieżący węzeł w każdej iteracji i wykonaj bieżący_węzeł obok tego.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Uzyskaj długość połączonej listy w Pythonie
Ta metoda zwraca rozmiar połączonej listy. W tej metodzie zainicjowaliśmy licznik 'rozmiar' z 0, a następnie, jeśli głowa nie jest równa None, przeglądamy połączoną listę za pomocą a pętla while i zwiększ rozmiar z 1 w każdej iteracji i zwróć rozmiar kiedy bieżący węzeł staje się Nikt inny zwracamy 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> |
>
polecenie rozciągania programu AutoCAD
>
Przykład listy połączonej w Pythonie
W tym przykładzie Po zdefiniowaniu klasy Node i LinkedList utworzyliśmy połączoną listę o nazwie lista używając klasy połączonej listy, a następnie wstaw cztery węzły z danymi znakowymi „a”, „b”, „c”, „d” I 'G' na połączonej liście, następnie drukujemy połączoną listę za pomocą drukujLL() metoda połączonej listy, po czym usunęliśmy niektóre węzły za pomocą metod usuwania a następnie ponownie wydrukuj połączoną listę, a na wynikach zobaczymy, że węzeł został pomyślnie usunięty. Następnie drukujemy również rozmiar połączonej listy.
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())> |
>
>Wyjście
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>