En este artículo, aprenderemos sobre la implementación de una lista vinculada en Pitón . Para implementar la lista enlazada en Python, usaremos clases en Python . Ahora, sabemos que una lista vinculada consta de nodos y los nodos tienen dos elementos, es decir, datos y una referencia a otro nodo. Primero implementemos el nodo.
¿Qué es la lista enlazada en Python?
Una lista enlazada Es un tipo de estructura de datos lineal similar a las matrices. Es una colección de nodos que están vinculados entre sí. Un nodo contiene dos cosas: la primera son datos y la segunda es un enlace que lo conecta con otro nodo. A continuación se muestra un ejemplo de una lista vinculada con cuatro nodos y cada nodo contiene datos de caracteres y un vínculo a otro nodo. Nuestro primer nodo es donde cabeza puntos y podemos acceder a todos los elementos de la lista enlazada usando el cabeza.
Lista enlazada
Creando una lista enlazada en Python
En esta clase LinkedList, usaremos la clase Node para crear una lista vinculada. En esta clase tenemos un __caliente__ Método que inicializa la lista enlazada con un encabezado vacío. A continuación, hemos creado un insertarAlBegin() método para insertar un nodo al principio de la lista enlazada, un insertarEnIndex() método para insertar un nodo en el índice dado de la lista enlazada, y insertarAlEnd() El método inserta un nodo al final de la lista vinculada. Después de eso, tenemos el eliminar_nodo() método que toma los datos como argumento para eliminar ese nodo. En el eliminar_nodo() método, recorremos la lista vinculada si hay un nodo presente igual a los datos, luego eliminamos ese nodo de la lista vinculada. Entonces tenemos el tamañoDeLL() método para obtener el tamaño actual de la lista vinculada y el último método de la clase LinkedList es imprimirLL() que atraviesa la lista vinculada e imprime los datos de cada nodo.
Crear una clase de nodo
Hemos creado una clase Nodo en la que hemos definido un __caliente__ función para inicializar el nodo con los datos pasados como argumento y una referencia con Ninguno porque si tenemos un solo nodo entonces no hay nada en su referencia.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Inserción en lista enlazada
Inserción al principio de la lista enlazada
Este método inserta el nodo al principio de la lista vinculada. En este método creamos un nuevo_nodo con lo dado datos y verificamos si la cabeza es un nodo vacío o no, si la cabeza está vacía, entonces hacemos el nuevo_nodo como cabeza y devolver de lo contrario insertamos la cabeza en el siguiente nuevo_nodo y hacer el cabeza igual a nuevo_nodo.
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> |
>
>
Insertar un nodo en una posición específica en una lista vinculada
Este método inserta el nodo en el índice dado en la lista vinculada. En este método creamos un nuevo_nodo con datos dados, un nodo_actual que es igual al encabezado y un contador 'posición' se inicializa con 0. Ahora, si el índice es igual a cero, significa que el nodo se insertará al comienzo, por lo que llamamos método insertAtBegin() de lo contrario ejecutamos un bucle while hasta que nodo_actual no es igual a Ninguno o (posición+1) no es igual al índice que tenemos que en una posición volver a insertar en una posición determinada para realizar el enlace de nodos y en cada iteración, incrementamos la posición en 1 y hacemos el nodo_actual siguiente. Cuando el bucle se rompe y si nodo_actual no es igual a Ninguno insertamos new_node después del nodo_actual. Si nodo_actual es igual a Ninguno significa que el índice no está presente en la lista y imprimimos Índice no presente.
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'>)> |
>
>
Inserción en lista enlazada al final
Este método inserta el nodo al final de la lista vinculada. En este método creamos un nuevo_nodo con los datos proporcionados y comprobar si el cabeza es un nodo vacío o no si el cabeza está vacío entonces hacemos el nuevo_nodo como cabeza y devolver demás hacemos un nodo_actual igual a la cabeza atravesar hasta el último nodo de la lista enlazada y cuando lleguemos Ninguno después del nodo_actual, el bucle while se rompe e inserta el nuevo_nodo en el próximo de nodo_actual que es el último nodo de la lista enlazada.
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> |
>
>
Actualizar el nodo de una lista vinculada
Este código define un método llamado updateNode en una clase de lista vinculada. Se utiliza para actualizar el valor de un nodo en una posición determinada en la lista vinculada.
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'>)> |
>
>
Eliminar nodo en una lista vinculada
Eliminar el primer nodo de la lista vinculada
Este método elimina el primer nodo de la lista enlazada simplemente haciendo que el segundo nodo cabeza de la lista enlazada.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Eliminar el último nodo de la lista vinculada
En este método, eliminaremos el último nodo. Primero, recorremos hasta el penúltimo nodo usando el bucle while y luego hacemos el siguiente de ese nodo. Ninguno y se eliminará el último nodo.
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> |
>
>
Eliminar un nodo de lista vinculada en una posición determinada
En este método, eliminaremos el nodo en el índice dado, este método es similar a el insertar_en_inded() método. En este método, si el cabeza es Ninguno nosotros simplemente devolver de lo contrario inicializamos un nodo_actual con auto.cabeza y posición con 0. Si la posición es igual al índice lo llamamos eliminar_primer_nodo() De lo contrario, atravesaremos el nodo anterior que queremos eliminar usando el bucle while. Después de eso, cuando salgamos del bucle while, verificamos ese nodo_actual es igual a Ninguno si no, hacemos que el siguiente del nodo_actual sea igual al siguiente del nodo que queremos eliminar; de lo contrario, imprimimos el mensaje. Índice no presente porque nodo_actual es igual a Ninguno.
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'>)> |
>
>
Eliminar un nodo de lista vinculada de unos datos determinados
Este método elimina el nodo con los datos proporcionados de la lista vinculada. En este método, primero hicimos un nodo_actual igual a la cabeza y ejecutar un mientras bucle para recorrer la lista enlazada. Este bucle while se rompe cuando nodo_actual se convierte Ninguno o los datos al lado del nodo actual son iguales a los datos proporcionados en el argumento. Ahora, después de salir del bucle si el nodo_actual es igual a Ninguno significa que el nodo no está presente en los datos y simplemente regresamos, y si los datos al lado del nodo_actual es igual a los datos proporcionados, entonces eliminamos ese nodo haciendo que el siguiente nodo_eliminado sea el siguiente del nodo_actual. Y esto se implementa usando la condición 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> |
>
>
Recorrido de lista enlazada en Python
Este método atraviesa la lista vinculada e imprime los datos de cada nodo. En este método, hicimos un nodo_actual igual a la cabeza e iterar a través de la lista enlazada usando un mientras bucle hasta el nodo_actual se convierte en Ninguno e imprime los datos de nodo_actual en cada iteración y hacer el nodo_actual junto a él.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Obtener la longitud de una lista vinculada en Python
Este método devuelve el tamaño de la lista vinculada. En este método, hemos inicializado un contador. 'tamaño' con 0, y luego, si el encabezado no es igual a Ninguno, recorremos la lista vinculada usando un mientras bucle e incrementar el tamaño con 1 en cada iteración y devolver el tamaño cuando nodo_actual se convierte Nadie más devolvemos 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> |
>
>
java si no
Ejemplo de lista enlazada en Python
En este ejemplo, después de definir la clase Node y LinkedList, hemos creado una lista vinculada llamada lista usando la clase de lista vinculada y luego inserte cuatro nodos con datos de caracteres 'a B C D' y 'gramo' en la lista enlazada luego imprimimos la lista enlazada usando imprimirLL() clase de lista vinculada de método después de eso, hemos eliminado algunos nodos usando métodos de eliminación y luego imprima la lista vinculada nuevamente y podremos ver en el resultado que el nodo se eliminó exitosamente. Después de eso, también imprimimos el tamaño de la lista vinculada.
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())> |
>
>Producción
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>