Las estructuras de datos juegan un papel clave en el mundo de la programación. Nos ayudan a organizar nuestros datos de manera que se puedan utilizar de manera eficiente.
En este tutorial, aprenderemos sobre el lista enlazada individualmente y lista doblemente enlazada.
Una lista vinculada es una estructura de datos lineal. No almacena los datos en ubicaciones de memoria contiguas como matrices. Y cada elemento en vinculado se llama nodo y están conectados usando el punteros. La primera nodo en la lista enlazada se llama cabeza.
El tamaño de la lista enlazada es dinámico. Entonces, podemos tener la cantidad de nodos que queramos a menos que el almacenamiento esté disponible en el dispositivo.
Hay dos tipos de listas vinculadas. Veamos el tutorial detallado sobre ellos uno por uno.
#1. Singly Linked List
Una lista enlazada individualmente contiene un puntero único conectado a la siguiente nodo en la lista vinculada. Tenemos que almacenar los datos y el puntero de cada nodo en la lista vinculada.
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 enlazada individualmente. Veamos los pasos para implementarlo en Python.
Implementación de listas vinculadas individualmente
1. El primer paso es crear el nodo para lista enlazada.
¿Cómo crearlo?
In Python, podemos crear fácilmente el nodo usando el clase. La clase contiene datos y puntero para siguiente nodo.
Mira el código del 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 usando la clase anterior. Lo veremos en un rato.
Ahora, tenemos el nodo con nosotros. A continuación, tenemos que crear una lista vinculada con múltiples nodos. Creemos otra clase para una lista vinculada.
2. Crea una clase llamada Lista enlazada con la cabeza inicializada a Ninguna. 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 vinculada? 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 vinculada.
Para insertar un nuevo nodo en la lista enlazada, tenemos que seguir ciertos pasos.
A verlos.
- Compruebe si la cabeza está vacía o no.
- Si la cabeza está vacía, asigne el nuevo nodo a la cabeza.
- Si el encabezado no está vacío, obtenga el último nodo de la lista vinculada.
- Asigne el nuevo nodo al puntero siguiente del último nodo.
Veamos el código para insertar un nuevo nodo en la lista vinculada.
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 vinculada. ¿Cómo podemos acceder a los datos de los nodos de la lista vinculada?
Para acceder a los datos de la lista enlazada, tenemos que iterar a través del enlazado usando el siguiente puntero como 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 vinculada.
4. Siga los pasos a continuación para imprimir todos los datos de los nodos en la lista vinculada.
- Inicializar una variable con cabeza.
- Escribe un ciclo que se repita 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 vinculada 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 vinculada 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 por la lista vinculada. Ahora, sabe cómo implementar una lista de enlaces individuales. Puede implementar fácilmente la lista de enlaces dobles con el conocimiento de la lista de enlaces individuales. Vamos a sumergirnos en la siguiente sección del tutorial.
#2. Doubly Linked List
Una lista de doble enlace contiene dos punteros conectado a la nodo anterior y del siguiente nodo en la lista vinculada. Tenemos que almacenar los datos y dos punteros para cada nodo en la lista vinculada.
La puntero anterior del primer nodo es nulo y del 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 individuales en la implementación. Una vez más, explicarte las mismas cosas te resultará aburrido. Repase el código en cada paso y lo entenderá muy rápidamente. Vamonos.
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 de enlaces dobles.
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 enlazados.
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 enlaces dobles similar a la lista de enlaces simples. Diviértete 🙂
Conclusión
Puede encontrar muchos problemas basados en listas enlazadas. Pero, tienes que conocer la implementación básica del link que has aprendido en este tutorial. Espero que lo hayas pasado genial aprendiendo el nuevo concepto.
Codificación feliz 🙂
