Las estructuras de datos desempeñan un papel fundamental en el mundo de la programación. Nos ayudan a organizar nuestros datos de forma que puedan utilizarse de manera eficiente.
En este tutorial, vamos a aprender sobre la lista simplemente enlazada y la lista doblemente enlazada.
Una lista enlazada es una estructura de datos lineal. No almacena los datos en ubicaciones de memoria contiguas como las matrices. Y cada elemento de la lista enlazada se denomina nodo y se conectan mediante punteros. El primer nodo de la lista enlazada se denomina cabeza.
El tamaño de la lista enlazada es dinámico. Por lo tanto, podemos tener el número de nodos que queramos a menos que el almacenamiento esté disponible en el dispositivo.
Existen dos tipos de listas enlazadas. Veamos el tutorial detallado sobre ellas una a una.
#1. Lista enlazada simple
Una lista enlazada simple contiene un único puntero conectado al siguiente nodo de la lista enlazada. Tenemos que almacenar los datos y el puntero para cada nodo de la lista enlazada.
El último nodo de la lista enlazada contiene null como siguiente puntero para representar el final de la lista enlazada.
Puede ver la ilustración de una lista enlazada a continuación.
Ahora, tenemos una comprensión completa de una lista enlazada simple. Veamos los pasos para implementarla en Python.
Implementación de una lista enlazada simple
1. El primer paso es crear el nodo para la lista enlazada.
¿Cómo crearlo?
En Python, podemos crear fácilmente el nodo utilizando la clase. La clase contiene datos y un puntero para el siguiente nodo.
Observe el código para el nodo.
clase Nodo:
def __init__(self, data):
## datos del nodo
self.datos = datos
## puntero siguiente
self.next = None
Podemos crear el nodo con cualquier tipo de datos utilizando la clase anterior. Lo veremos dentro de un rato.
Ahora, tenemos el nodo con nosotros. A continuación, tenemos que crear una lista enlazada con múltiples nodos. Vamos a crear otra clase para una lista enlazada.
2. Cree una clase llamada LinkedList con la cabeza inicializada a None. Vea el código siguiente.
clase LinkedList:
def __init__(self):
## inicializar la cabeza con None
self.head = None
3. Tenemos las clases Node y LinkedList con nosotros. ¿Cómo insertamos un nuevo nodo en la lista enlazada? Una respuesta sencilla podría ser utilizando un método de la clase LinkedList . Sí, eso estaría bien. Escribamos un método para insertar un nuevo nodo en la lista enlazada.
Para insertar un nuevo nodo en la lista enlazada, tenemos que seguir ciertos pasos.
Veámoslos.
- Compruebe si la cabeza está vacía o no.
- Si la cabeza está vacía, asigne el nuevo nodo a la cabeza.
- Si la cabeza no está vacía, obtenga el último nodo de la lista enlazada.
- Asigne el nuevo nodo al último nodo puntero siguiente.
Veamos el código para insertar un nuevo nodo en la lista enlazada.
clase LinkedList:
####
def insert(self, nuevo_nodo):
## comprueba si la cabeza está vacía o no
if self.head:
## obtener el último nodo
último_nodo = auto.cabeza
while último_nodo != Ninguno
último_nodo = último_nodo.siguiente
## asignar el nuevo nodo al puntero siguiente del último nodo
último_nodo.siguiente = nuevo_nodo
si no
## head está vacío
## asignar el nodo a cabeza
self.head = nuevo_nodo
Hurra! hemos completado el método para insertar un nuevo nodo en la lista enlazada. ¿Cómo podemos acceder a los datos de los nodos de la lista enlazada?
Para acceder a los datos de la lista enlazada, tenemos que iterar a través de la enlazada utilizando el puntero siguiente como hacemos para obtener el último nodo en el método de inserción. Escribamos un método dentro de la clase LinkedList para imprimir todos los datos de los nodos de la lista enlazada.
4. Siga los siguientes pasos para imprimir todos los datos de los nodos en la lista enlazada.
- Inicialice una variable con head.
- Escriba un bucle que itere hasta llegar al final de la lista enlazada.
- Imprima los datos de los nodos.
- Mueva el siguiente puntero
Veamos el código.
clase LinkedList:
####
def mostrar(self):
## variable para iteración
temp_node = self.head
## iterar hasta llegar al final de la lista enlazada
while temp_node != None:
## imprimiendo los datos del nodo
print(temp_node.data, end='->')
## pasar al siguiente nodo
temp_nodo = temp_nodo.siguiente
print('Nulo')
¡Uf! hemos completado la creación de la lista enlazada con los métodos necesarios. Probemos la lista enlazada instanciándola con algunos datos.
Podemos crear el nodo con el código Node(1) . Veamos el código completo de la implementación de la lista enlazada junto con el ejemplo de uso.
clase Nodo:
def __init__(self, data):
## datos del nodo
self.datos = datos
## puntero siguiente
self.next = None
clase LinkedList:
def __init__(self):
## inicializar la cabeza con None
self.head = None
def insertar(self, nuevo_nodo):
## comprobar si la cabeza está vacía o no
if self.head:
## obtener el último nodo
último_nodo = auto.cabeza
while último_nodo.siguiente != Ninguno
último_nodo = último_nodo.siguiente
## asignar el nuevo nodo al puntero siguiente del último nodo
último_nodo.siguiente = nuevo_nodo
si no
## head está vacío
## asignar el nodo a cabeza
self.head = nuevo_nodo
def mostrar(self):
## variable para la iteración
nodo_temporal = auto.cabeza
## iterar hasta llegar al final de la lista enlazada
while temp_node != None:
## imprimiendo los datos del nodo
print(temp_node.data, end='->')
## pasar al siguiente nodo
temp_nodo = temp_nodo.siguiente
print('Nulo')
if __name__ == '__main__':
## instanciar la lista enlazada
lista_vinculada = Lista_vinculada()
## insertar los datos en la lista enlazada
linked_list.insert(Nodo(1))
linked_list.insert(Nodo(2))
lista_vinculada.insert(Nodo(3))
lista_vinculada.insert(Nodo(4))
lista_vinculada.insert(Nodo(5))
lista_vinculada.insert(Nodo(6))
lista_vinculada.insertar(Nodo(7))
## imprimir la lista enlazada
linked_list.display()
Ejecute el programa anterior para obtener el siguiente resultado.
1->2->3->4->5->6->7->Null
Eso es todo para la lista enlazada. Ahora ya sabe cómo implementar una lista enlazada simple. Puede implementar fácilmente la lista doblemente enlazada con el conocimiento de la lista uni-enlazada. Sumerjámonos en la siguiente sección del tutorial.
#2. Lista doblemente enlazada
Una lista doblemente enlazada contiene dos punteros conectados al nodo anterior y al nodo siguiente de la lista enlazada. Tenemos que almacenar los datos y dos punteros para cada nodo de la lista enlazada.
El puntero anterior del primer nodo es nulo y el puntero siguiente del último nodo es nulo para representar el final de la lista enlazada a ambos lados.
Puede ver la ilustración de una lista enlazada a continuación.
La lista doblemente enlazada también tiene pasos similares a la lista uni-enlazada en la implementación. De nuevo explicar lo mismo le resultará aburrido. Repase el código en cada paso y lo entenderá muy rápidamente. Vamos allá.
Implementación de la lista doblemente enlazada
1. Creación de un nodo para la lista doblemente enlazada con el puntero del nodo anterior, los datos y el puntero del nodo siguiente.
clase Nodo:
def __init__(self, data):
## puntero anterior
self.prev = None
## datos del nodo
self.datos = datos
## puntero siguiente
self.next = None
2. Clase de lista doblemente enlazada.
clase LinkedList:
def __init__(self):
## inicializar la cabeza con None
self.head = None
3. Método para insertar un nuevo nodo en la lista doblemente enlazada.
clase LinkedList:
####
def insert(self, nuevo_nodo):
## comprueba si la cabeza está vacía o no
if self.head:
## obtener el último nodo
último_nodo = auto.cabeza
while último_nodo.siguiente != Ninguno
último_nodo = último_nodo.siguiente
## asignar el último nodo al puntero anterior del nuevo nodo
nuevo_nodo.prev = último_nodo
## asignar el nuevo nodo al puntero siguiente del último nodo
último_nodo.siguiente = nuevo_nodo
4. Un método para mostrar los datos de la lista doblemente enlazada.
clase LinkedList:
####
def mostrar(self):
## imprimir los datos en orden normal
print("Orden normal: ", end='')
temp_node = self.head
while temp_node != None
print(temp_node.data, end=' ')
temp_nodo = temp_nodo.siguiente
print()
## imprimir los datos en orden inverso utilizando el puntero anterior
print("Orden inverso: ", end='')
## obtener el último nodo
último_nodo = self.cabeza
while último_nodo.siguiente != Ninguno
último_nodo = último_nodo.siguiente
nodo_temporal = último_nodo
while temp_node != None
print(temp_nodo.datos, end=' ')
nodo_temp = nodo_temp.prev
print()
Hemos visto el código de la lista doblemente enlazada. Y no hay código para el uso de la clase de lista doblemente enlazada. Eso es para usted. Utilice la clase de lista doblemente enlazada de forma similar a la lista enlazada individualmente. Diviértase 🙂
Conclusión
Puede encontrar muchos problemas basados en listas enlazadas. Pero, tiene que conocer la implementación básica de las enlazadas que ha aprendido en este tutorial. Espero que se haya divertido aprendiendo este nuevo concepto.
Además, compruebe cómo utilizar el método index de python para encontrar el índice de un elemento en una lista.
Feliz Codificación 😀