Las estructuras de datos juegan un papel clave en el mundo de la programación. Nos ayudan a organizar nuestros datos de una manera que se puede utilizar de manera eficiente.
En este tutorial, vamos a aprender sobre la lista de enlaces simples y la lista de enlaces dobles.
Una lista enlazada es una estructura de datos lineal. No almacena los datos en ubicaciones de memoria contiguas como matrices. Y cada elemento vinculado se llama nodo y se conectan usando los punteros. El primer nodo en la lista enlazada se llama cabeza.
El tamaño de la lista enlazada es dinámico. Por lo tanto, podemos tener la cantidad de nodos que queramos a menos que el almacenamiento esté disponible en el dispositivo.
Hay dos tipos de listas enlazadas. Veamos el tutorial detallado sobre ellos uno por uno.
Tabla de contenido
#1. Lista de enlaces individuales
Una lista enlazada individualmente contiene un solo puntero conectado al siguiente nodo en la lista enlazada. Tenemos que almacenar los datos y el puntero para cada nodo en la lista enlazada.
El último nodo de la lista vinculada contiene nulo como el siguiente puntero para representar el final de la lista vinculada.
Puede ver la ilustración de un enlace a continuación.
Ahora, tenemos una comprensión completa de una lista de enlaces simples. Veamos los pasos para implementarlo en Python.
Implementación de listas enlazadas individuales
1. El primer paso es crear el nodo para la lista enlazada.
¿Cómo crearlo?
En Python, podemos crear fácilmente el nodo usando la clase. La clase contiene datos y un puntero para el siguiente nodo.
Mire el código para el nodo.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Podemos crear el nodo con cualquier tipo de datos utilizando la clase anterior. Lo veremos en un rato.
Ahora, tenemos el nodo con nosotros. A continuación, tenemos que crear una lista enlazada con varios nodos. Vamos a crear otra clase para una lista enlazada.
2. Cree una clase llamada LinkedList con el encabezado inicializado en Ninguno. Vea el código a continuación.
class LinkedList: def __init__(self): ## initializing the head with 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 simple podría ser usar un método en 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 cabecera está vacía, asigne el nuevo nodo a la cabecera.
- Si el encabezado no está vacío, obtenga el último nodo de la lista enlazada.
- Asigne el nuevo nodo al puntero siguiente del último nodo.
Veamos el código para insertar un nuevo nodo en la lista enlazada.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node != None: last_node = last_node.next ## assigning the new node to the next pointer of last node last_node.next = new_node else: ## head is empty ## assigning the node to head self.head = new_node
¡Viva! 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 lista enlazada usando el siguiente puntero como lo 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 en la lista enlazada.
4. Siga los pasos a continuación para imprimir todos los datos de los nodos en la lista vinculada.
- Inicializar una variable con cabeza.
- Escriba un bucle que itere hasta llegar al final de la lista enlazada.
- Imprime los datos del nodo.
- Mover el siguiente puntero
Veamos el código.
class LinkedList:
####
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
¡Uf! completamos la creación del enlace con los métodos necesarios. Probemos la lista enlazada creando una instancia 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 uso de muestra.
class Node:
def __init__(self, data):
## data of the node
self.data = data
## next pointer
self.next = None
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None
def insert(self, new_node):
## check whether the head is empty or not
if self.head:
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## assigning the new node to the next pointer of last node
last_node.next = new_node
else:
## head is empty
## assigning the node to head
self.head = new_node
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instantiating the linked list
linked_list = LinkedList()
## inserting the data into the linked list
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## printing the linked list
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 de enlaces simples. Puede implementar fácilmente la lista de enlaces dobles con el conocimiento de la lista de enlaces simples. Vamos a sumergirnos en la siguiente sección del tutorial.
#2. Lista doblemente enlazada
Una lista de doble enlace contiene dos punteros conectados al nodo anterior y al siguiente nodo en la lista enlazada. Tenemos que almacenar los datos y dos punteros para cada nodo en la lista enlazada.
El puntero anterior del primer nodo es nulo y el siguiente puntero del último nodo es nulo para representar el final de la lista enlazada en ambos lados.
Puede ver la ilustración de un enlace a continuación.
La lista de enlaces dobles también tiene pasos similares a los de la lista de enlaces simples en la implementación. Nuevamente, explicar las mismas cosas será aburrido para ti. Repase el código en cada paso y lo entenderá muy rápidamente. Vamos.
Implementación de listas doblemente enlazadas
1. Crear un nodo para la lista doblemente enlazada con el puntero de nodo anterior, los datos y el puntero de nodo siguiente.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Clase de lista doblemente enlazada.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Un método para insertar un nuevo nodo en la lista doblemente enlazada.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node.next != None: last_node = last_node.next ## assigning the last node to the previous pointer of the new node new_node.prev = last_node ## assigning the new node to the next pointer of last node last_node.next = new_node
4. Un método para mostrar los datos de la lista doblemente enlazada.
class LinkedList:
####
def display(self):
## printing the data in normal order
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## printing the data in reverse order using previous pointer
print("Reverse Order: ", end='')
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.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. Esto es para ti. Utilice la clase de lista de doble enlace similar a la lista de enlace simple. Diviértete 🙂
Conclusión
Puede encontrar muchos problemas basados en listas enlazadas. Pero, debe conocer la implementación básica del vinculado que ha aprendido en este tutorial. Espero que lo hayas pasado muy bien aprendiendo el nuevo concepto.
Codificación feliz 🙂