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 😀