Geekflare cuenta con el apoyo de nuestra audiencia. Podemos ganar comisiones de afiliados comprando enlaces en este sitio.
Comparte en:

Comprender la implementación de listas vinculadas en Python

alojamiento python
Escáner de seguridad de aplicaciones web Invicti – la única solución que ofrece verificación automática de vulnerabilidades con Proof-Based Scanning™.

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 = None

Podemos 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 = None

3. 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->Null

Eso 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 = 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 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_node

4. 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 🙂

Gracias a nuestros patrocinadores
Más lecturas interesantes sobre el desarrollo
Impulse su negocio
Algunas de las herramientas y servicios para ayudar a que su negocio crezca.
  • Invicti utiliza Proof-Based Scanning™ para verificar automáticamente las vulnerabilidades identificadas y generar resultados procesables en cuestión de horas.
    Prueba Invicti
  • Web scraping, proxy residencial, administrador de proxy, desbloqueador web, rastreador de motores de búsqueda y todo lo que necesita para recopilar datos web.
    Prueba Brightdata
  • Semrush es una solución de marketing digital todo en uno con más de 50 herramientas en SEO, redes sociales y marketing de contenido.
    Prueba Semrush
  • Intruder es un escáner de vulnerabilidades en línea que encuentra debilidades de ciberseguridad en su infraestructura, para evitar costosas filtraciones de datos.
    Intente Intruder