En aquest article, coneixerem la implementació d'una llista enllaçada a Python . Per implementar la llista enllaçada a Python, farem servir classes en Python . Ara, sabem que una llista enllaçada consta de nodes i que els nodes tenen dos elements, és a dir, dades i una referència a un altre node. Primer implementem el node.
Què és la llista enllaçada a Python
Una llista enllaçada és un tipus d'estructura de dades lineal similar a les matrius. És una col·lecció de nodes que estan enllaçats entre si. Un node conté dues coses primer són dades i segon és un enllaç que el connecta amb un altre node. A continuació es mostra un exemple d'una llista enllaçada amb quatre nodes i cada node conté dades de caràcters i un enllaç a un altre node. El nostre primer node és on cap punts i podem accedir a tots els elements de la llista enllaçada mitjançant el cap.
Llista enllaçada
Creació d'una llista enllaçada en Python
En aquesta classe LinkedList, utilitzarem la classe Node per crear una llista enllaçada. En aquesta classe, tenim un __calent__ mètode que inicialitza la llista enllaçada amb un capçal buit. A continuació, hem creat un insertAtBegin() mètode per inserir un node al principi de la llista enllaçada, a insertAtIndex() mètode per inserir un node a l'índex donat de la llista enllaçada, i insertAtEnd() El mètode insereix un node al final de la llista enllaçada. Després d'això, tenim el remove_node() mètode que pren les dades com a argument per eliminar aquest node. En el remove_node() mètode travessem la llista enllaçada si hi ha un node igual a les dades, llavors eliminem aquest node de la llista enllaçada. Llavors tenim el sizeOfLL() mètode per obtenir la mida actual de la llista enllaçada i l'últim mètode de la classe LinkedList és printLL() que recorre la llista enllaçada i imprimeix les dades de cada node.
Creació d'una classe de nodes
Hem creat una classe Node en la qual hem definit a __calent__ funció per inicialitzar el node amb les dades passades com a argument i una referència amb Cap perquè si només tenim un node, no hi ha res a la seva referència.
Python 3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Inserció a la llista enllaçada
Inserció a l'inici de la llista enllaçada
Aquest mètode insereix el node al principi de la llista enllaçada. En aquest mètode, creem un nou_node amb el donat dades i comproveu si el capçal és un node buit o no si el capçal està buit llavors fem el nou_node com cap i tornar sinó inserim el cap al següent nou_node i fes el cap igual a nou_node.
Python 3
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> |
>
>
Insereix un node en una posició específica en una llista enllaçada
Aquest mètode insereix el node a l'índex donat a la llista enllaçada. En aquest mètode, creem un nou_node amb dades donades, un current_node igual al cap i un comptador 'posició' inicialitza amb 0. Ara, si l'índex és igual a zero, vol dir que el node s'ha d'inserir a l'inici, així que hem cridat Mètode insertAtBegin(). en cas contrari, fem un bucle while fins al node_actual no és igual a Cap o (posició+1) no és igual a l'índex que hem de fer a una posició enrere per inserir en una posició donada per fer l'enllaç de nodes i en cada iteració, incrementem la posició en 1 i fem el node_actual següent d'ella. Quan es trenca el bucle i si node_actual no és igual a Cap inserim nou_node després al node_actual. Si node_actual és igual a Cap vol dir que l'índex no està present a la llista i imprimim Índex no present.
Python 3
# 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'>)> |
>
>
Inserció a la llista enllaçada al final
Aquest mètode insereix el node al final de la llista enllaçada. En aquest mètode, creem un nou_node amb les dades proporcionades i comproveu si cap és un node buit o no si el cap està buit llavors fem el nou_node com cap i tornar altra cosa fem a current_node igual a el cap travessa fins a l'últim node de la llista enllaçada i quan arribem Cap després del current_node, el bucle while es trenca i inseriu el fitxer nou_node al següent de node_actual que és l'últim node de la llista enllaçada.
Python 3
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> |
>
>
Actualitzeu el node d'una llista enllaçada
Aquest codi defineix un mètode anomenat updateNode en una classe de llista enllaçada. S'utilitza per actualitzar el valor d'un node en una posició determinada de la llista enllaçada.
Python 3
# 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'>)> |
>
>
Suprimeix el node d'una llista enllaçada
Elimina el primer node de la llista enllaçada
Aquest mètode elimina el primer node de la llista enllaçada simplement fent el segon node cap de la llista enllaçada.
Python 3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Elimina l'últim node de la llista enllaçada
En aquest mètode, esborrarem l'últim node. En primer lloc, travessem fins al darrer node utilitzant el bucle while, i després fem el següent d'aquest node Cap i l'últim node s'eliminarà.
Python 3
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> |
>
>
Suprimeix un node de llista enllaçada en una posició determinada
En aquest mètode, eliminarem el node de l'índex donat, aquest mètode és similar el insert_at_inded() mètode. En aquest mètode, si el cap és Cap nosaltres senzillament tornar sinó inicialitzem a node_actual amb auto.cap i posició amb 0. Si la posició és igual a l'índex hem anomenat remove_first_node() En cas contrari, travessem al node anterior que volem eliminar mitjançant el bucle while. Després d'això, quan sortim del bucle while, comprovem aquest node_actual és igual a Cap si no, fem que el següent de current_node sigui igual al següent de node que volem eliminar, sinó imprimirem el missatge Índex no present perquè node_actual és igual a Cap.
Python 3
# 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'>)> |
>
>
Suprimeix un node de llista enllaçada d'una dada determinada
Aquest mètode elimina el node amb les dades proporcionades de la llista enllaçada. En aquest mètode, primer hem fet un node_actual igual a la cap i córrer a bucle while per recórrer la llista enllaçada. Aquest bucle while es trenca quan node_actual esdevé Cap o les dades al costat del node actual són iguals a les dades proporcionades a l'argument. Ara, després de sortir del bucle si el node_actual és igual a Cap vol dir que el node no està present a les dades i només tornem, i si les dades al costat del node_actual és igual a les dades proporcionades, llavors eliminem aquest node fent que el següent node_eliminat sigui el següent del node_actual. I això s'implementa mitjançant la condició if else.
nombre enter java a cadena
Python 3
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> |
>
>
Travessia de llista enllaçada a Python
Aquest mètode recorre la llista enllaçada i imprimeix les dades de cada node. En aquest mètode, hem fet un node_actual igual a la cap i itera per la llista enllaçada utilitzant a bucle while fins el node_actual convertir-se en Cap i imprimir les dades de node_actual en cada iteració i fer el node_actual al costat.
Python 3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Obteniu la longitud d'una llista enllaçada a Python
Aquest mètode retorna la mida de la llista enllaçada. En aquest mètode, hem inicialitzat un comptador 'mida' amb 0, i després si el cap no és igual a Cap, recorrem la llista enllaçada amb a bucle while i augmentar el mida amb 1 a cada iteració i retornar la mida quan node_actual esdevé Cap més tornem 0.
Python 3
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> |
>
>
Exemple de la llista enllaçada a Python
En aquest exemple, després de definir la classe Node i LinkedList hem creat una llista enllaçada anomenada llist utilitzant la classe de llista enllaçada i després inseriu quatre nodes amb dades de caràcters 'a', 'b', 'c', 'd' i 'g' a la llista enllaçada després imprimim la llista enllaçada utilitzant printLL() classe de llista enllaçada amb mètodes després d'haver eliminat alguns nodes mitjançant mètodes d'eliminació i després imprimiu de nou la llista enllaçada i podem veure a la sortida que el node s'ha eliminat correctament. Després d'això, també imprimim la mida de la llista enllaçada.
Python 3
# 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())> |
>
>Sortida
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>