În acest articol, vom afla despre implementarea unei liste legate în Piton . Pentru a implementa lista legată în Python, vom folosi cursuri în Python . Acum, știm că o listă legată constă din noduri și nodurile au două elemente, adică date și o referință la un alt nod. Să implementăm mai întâi nodul.
Ce este Linked List în Python
O listă legată este un tip de structură de date liniară similară cu tablourile. Este o colecție de noduri care sunt legate între ele. Un nod conține două lucruri, în primul rând date, iar al doilea este o legătură care îl conectează cu un alt nod. Mai jos este un exemplu de listă legată cu patru noduri și fiecare nod conține date de caracter și o legătură către un alt nod. Primul nostru nod este unde cap puncte și putem accesa toate elementele listei legate folosind cap.
Lista legată
Crearea unei liste legate în Python
În această clasă LinkedList, vom folosi clasa Node pentru a crea o listă legată. În această clasă, avem un __Fierbinte__ metodă care inițializează lista legată cu un cap gol. În continuare, am creat un insertAtBegin() metoda de a insera un nod la începutul listei legate, an insertAtIndex() metoda de a insera un nod la indexul dat al listei legate și insertAtEnd() metoda inserează un nod la sfârșitul listei legate. După aceea, avem remove_node() metodă care ia datele ca argument pentru a șterge acel nod. În remove_node() metoda parcurgem lista legata daca un nod este prezent egal cu date, apoi stergem acel nod din lista legata. Apoi avem sizeOfLL() metoda pentru a obține dimensiunea curentă a listei legate și ultima metodă a clasei LinkedList este printLL() care parcurge lista legată și imprimă datele fiecărui nod.
Crearea unei clase de nod
Am creat o clasă Node în care am definit a __Fierbinte__ funcția de inițializare a nodului cu datele transmise ca argument și o referință cu None deoarece dacă avem un singur nod atunci nu există nimic în referința lui.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Inserare în lista legată
Inserarea la început în lista legată
Această metodă inserează nodul la începutul listei legate. În această metodă, creăm un nod_nou cu dat date și verificați dacă capul este un nod gol sau nu dacă capul este gol, atunci facem nod_nou la fel de cap și întoarcere altfel introducem capul la următorul nod_nou și faceți cap egal cu nod_nou.
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> |
>
>
Inserați un nod într-o poziție specifică într-o listă legată
Această metodă inserează nodul la indexul dat în lista legată. În această metodă, creăm un nod_nou cu date date, un current_node care este egal cu capul și un contor 'poziţie' se inițializează cu 0. Acum, dacă indicele este egal cu zero, înseamnă că nodul trebuie inserat la început, așa că am apelat metoda insertAtBegin(). altfel rulăm o buclă while până când nod_curent nu este egal cu Nici unul sau (poziție+1) nu este egal cu indicele pe care trebuie să-l inserăm într-o poziție din spate pentru a face legătura dintre noduri și în fiecare iterație, creștem poziția cu 1 și facem nod_curent alaturi de ea. Când bucla se rupe și dacă nod_curent nu este egal cu Nici unul inserăm new_node at after la nod_curent. Dacă nod_curent este egal cu Nici unul înseamnă că indexul nu este prezent în listă și tipărim Indicele nu este prezent.
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'>)> |
>
>
Inserarea în lista legată la sfârșit
Această metodă inserează nodul la sfârșitul listei legate. În această metodă, creăm un nod_nou cu datele date și verificați dacă cap este un nod gol sau nu dacă cap este gol, atunci facem nod_nou la fel de cap și întoarcere altfel facem o current_node egal la capul traversează până la ultimul nodul din lista legată și când primim Nici unul după current_node, bucla while se întrerupe și introduceți nod_nou în următorul de nod_curent care este ultimul nod al listei legate.
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> |
>
>
Actualizați nodul unei liste legate
Acest cod definește o metodă numită updateNode într-o clasă de listă legată. Este folosit pentru a actualiza valoarea unui nod la o anumită poziție din lista legată.
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'>)> |
>
>
Ștergeți nodul dintr-o listă legată
Eliminați primul nod din lista legată
Această metodă îndepărtează primul nod din lista legată pur și simplu prin realizarea celui de-al doilea nod cap din lista legată.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
format șir de caractere java
>
>
Eliminați ultimul nod din lista legată
În această metodă, vom șterge ultimul nod. Mai întâi, trecem la ultimul nod folosind bucla while, apoi facem următorul nod Nici unul iar ultimul nod va fi eliminat.
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> |
>
>
Ștergeți un nod de listă legat la o anumită poziție
În această metodă, vom elimina nodul la indexul dat, această metodă este similară cu cel insert_at_inded() metodă. În această metodă, dacă cap este Nici unul noi pur și simplu întoarcere altfel inițializam a nod_curent cu sine.cap și poziţie cu 0. Dacă poziția este egală cu indicele l-am numit remove_first_node() Altfel, trecem la un nod anterior pe care vrem să-l eliminăm folosind bucla while. După aceea, când ieșim din bucla while, verificăm acel nod_curent este egal cu Nici unul dacă nu, atunci facem următorul nod_curent egal cu următorul nod pe care vrem să-l eliminăm, altfel imprimăm mesajul Indicele nu este prezent deoarece nod_curent este egal cu Nici unul.
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'>)> |
>
>
Ștergeți un nod de listă conectat al unei date date
Această metodă elimină nodul cu datele date din lista legată. În această metodă, în primul rând am realizat un nod_curent egală cu cap și alergați a buclă while pentru a parcurge lista legată. Această buclă while se întrerupe când nod_curent devine Nici unul sau datele de lângă nodul curent sunt egale cu datele date în argument. Acum, după ce a ieșit din buclă dacă nod_curent este egal cu Nici unul înseamnă că nodul nu este prezent în date și doar revenim, iar dacă datele de lângă nod_curent este egal cu datele date, atunci eliminăm acel nod făcând următorul nod_eliminat la următorul nod_actual. Și acest lucru este implementat folosind condiția 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> |
>
>
Traversarea listelor legate în Python
Această metodă parcurge lista legată și tipărește datele fiecărui nod. În această metodă, am realizat un nod_curent egal cu cap și iterați prin lista legată folosind a buclă while pană la nod_curent devin None și tipăriți datele de nod_curent în fiecare iterație și faceți nod_curent lângă el.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Obțineți lungimea unei liste legate în Python
Această metodă returnează dimensiunea listei legate. În această metodă, am inițializat un contor 'mărimea' cu 0, iar apoi dacă capul nu este egal cu None, parcurgem lista legată folosind a buclă while și creșteți mărimea cu 1 în fiecare iterație și returnează dimensiunea când nod_curent devine Nimeni altcineva revenim 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> |
>
diferența dintre gheață și zăpadă
>
Exemplu de listă Linked în Python
În acest exemplu, după definirea clasei Node și LinkedList, am creat o listă legată numită llist folosind clasa de listă legată și apoi inserați patru noduri cu date de caractere „a”, „b”, „c”, „d” și ‘g’ în lista legată apoi tipărim lista legată folosind printLL() clasă listă legată de metode după aceea am eliminat unele noduri folosind metodele de eliminare și apoi tipăriți din nou lista legată și putem vedea în rezultat că nodul este șters cu succes. După aceea, imprimăm și dimensiunea listei legate.
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())> |
>
>Ieșire
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>