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.
últimas postagens
#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.
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
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.
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 🙂