Compreendendo a implementação de listas vinculadas em Python

As estruturas de dados desempenham um papel fundamental no mundo da programação. Eles nos ajudam a organizar nossos dados de forma que possam ser usados ​​de forma eficiente.

Neste tutorial, aprenderemos sobre a lista de encadeamento simples e a lista de encadeamento duplo.

Uma lista encadeada é uma estrutura de dados linear. Ele não armazena os dados em locais de memória contíguos, como arrays. E cada elemento vinculado é chamado de nó e eles são conectados usando os ponteiros. O primeiro nó na lista encadeada é chamado de cabeça.

O tamanho da lista encadeada é dinâmico. Assim, podemos ter qualquer número de nós que quisermos, a menos que o armazenamento esteja disponível no dispositivo.

Existem dois tipos de listas encadeadas. Vamos ver o tutorial detalhado sobre eles, um por um.

#1. Lista encadeada individualmente

Uma lista vinculada individualmente contém um único ponteiro conectado ao próximo nó na lista vinculada. Temos que armazenar os dados e o ponteiro para cada nó na lista encadeada.

O último nó na lista encadeada contém nulo como o próximo ponteiro para representar o final da lista encadeada.

Você pode ver a ilustração de um link abaixo.

Agora, temos uma compreensão completa de uma lista encadeada individualmente. Vamos ver os passos para implementá-lo em Python.

Implementação de lista encadeada simples

1. A primeira etapa é criar o nó para a lista encadeada.

Como criá-lo?

Em Python, podemos criar facilmente o nó usando a classe. A classe contém dados e um ponteiro para o próximo nó.

Observe o código do nó.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

Podemos criar o nó com qualquer tipo de dados usando a classe acima. Veremos daqui a pouco.

  Aumente os ganhos do seu blog com essas ferramentas de marketing de afiliados

Agora, temos o nó conosco. Em seguida, temos que criar uma lista encadeada com vários nós. Vamos criar outra classe para uma lista encadeada.

2. Crie uma classe chamada LinkedList com head inicializado como None. Veja o código abaixo.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. Temos classes Node e LinkedList conosco. Como inserimos um novo nó na lista encadeada? Uma resposta simples pode estar usando um método na classe LinkedList. Sim, isso seria bom. Vamos escrever um método para inserir um novo nó na lista encadeada.

Para inserir um novo nó na lista vinculada, devemos seguir algumas etapas.

Vamos vê-los.

  • Verifique se a cabeça está vazia ou não.
  • Se a cabeça estiver vazia, atribua o novo nó à cabeça.
  • Se a cabeça não estiver vazia, obtenha o último nó da lista encadeada.
  • Atribua o novo nó ao ponteiro do próximo nó do último nó.

Vamos ver o código para inserir um novo nó na lista encadeada.

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! concluímos o método para inserir um novo nó na lista encadeada. Como podemos acessar os dados dos nós da lista encadeada?

Para acessar os dados da lista encadeada, temos que percorrer o encadeado usando o próximo ponteiro, como fazemos para obter o último nó no método de inserção. Vamos escrever um método dentro da classe LinkedList para imprimir todos os dados dos nós na lista encadeada.

4. Siga as etapas abaixo para imprimir todos os dados de nós na lista vinculada.

  • Inicializa uma variável com head.
  • Escreva um loop que itera até chegarmos ao final da lista encadeada.
    • Imprima os dados do nó.
    • Mover o próximo ponteiro
  8 melhores plataformas de hospedagem de revendedores para seu próximo negócio

Vamos ver o 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')

Ufa! concluímos a criação do link com os métodos necessários. Vamos testar a lista encadeada instanciando-a com alguns dados.

Podemos criar o nó com o código Node(1). Vamos ver o código completo da implementação da lista encadeada junto com o exemplo de uso.

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()

Execute o programa acima para obter o seguinte resultado.

1->2->3->4->5->6->7->Null

Isso é tudo para a lista encadeada. Agora, você sabe como implementar uma lista de encadeamento simples. Você pode implementar facilmente a lista de encadeamento duplo com o conhecimento da lista de encadeamento simples. Vamos mergulhar na próxima seção do tutorial.

#2. Lista Duplamente Ligada

Uma lista encadeada dupla contém dois ponteiros conectados ao nó anterior e ao próximo nó na lista encadeada. Temos que armazenar os dados e dois ponteiros para cada nó na lista encadeada.

O ponteiro anterior do primeiro nó é nulo e o próximo ponteiro do último nó é nulo por representar o final da lista encadeada em ambos os lados.

  5 Melhor plataforma de hospedagem em nuvem para o mercado do Oriente Médio

Você pode ver a ilustração de um link abaixo.

A lista duplamente encadeada também tem etapas semelhantes às da lista simples na implementação. Novamente, explicar as mesmas coisas será chato para você. Percorra o código em cada etapa e você o entenderá muito rapidamente. Vamos lá.

Implementação de lista duplamente encadeada

1. Criando um nó para a lista duplamente vinculada com o ponteiro do nó anterior, os dados e o próximo ponteiro do nó.

class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. Classe de lista duplamente encadeada.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. Um método para inserir um novo nó na lista duplamente encadeada.

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. Um método para exibir os dados da lista duplamente vinculada.

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()

Vimos o código da lista duplamente encadeada. E não há código para o uso da classe de lista duplamente vinculada. Isso é para você. Use a classe de lista de encadeamento duplo semelhante à lista de encadeamento simples. Divirta-se 🙂

Conclusão

Você pode encontrar muitos problemas com base em listas encadeadas. Porém, você precisa conhecer a implementação básica do linkado que aprendeu neste tutorial. Espero que você tenha se divertido aprendendo o novo conceito.

Codificação feliz 🙂