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 acerca de la lista de enlaces simples y lista doblemente enlazada.
Una lista enlazada es una estructura de datos lineal. No almacena los datos en ubicaciones de memoria contiguas como matrices. Y cada elemento en vinculado se llama un nodo y se conectan mediante el punteros. La primera 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.
#1. Lista de enlaces individuales
Una lista enlazada simple contiene un puntero único 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 enlazada contiene nulo como el siguiente puntero para representar el final de la lista enlazada.
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 el lista enlazada.
¿Cómo crearlo?
En Python, podemos crear fácilmente el nodo utilizando el 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 = NonePodemos 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 múltiples nodos. Vamos a crear otra clase para una lista enlazada.
2. Crea una clase llamada Lista enlazada con la cabeza inicializada a Ninguno. Vea el código a continuación.
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None3. Tenemos Nodo y Lista enlazada clases con nosotros. ¿Cómo insertamos un nuevo nodo en la lista enlazada? Una respuesta simple podría ser usar un método en el Lista enlazada clase. 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 del Lista enlazada class 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 Nodo(1) código. 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->NullEso 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 Conectado al nodo anterior y el 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 del nodo anterior, los datos y el puntero del siguiente nodo.
class Node:
def __init__(self, data):
## previous pointer
self.prev = None
## data of the node
self.data = data
## next pointer
self.next = None2. Clase de lista doblemente enlazada.
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None3. 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_node4. 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 🙂
Relacionado:
Listas de verificación de diligencia debida: para transacciones de bienes raíces comerciales
