No universo da programação, as estruturas de dados são ferramentas cruciais. Elas oferecem métodos para organizar informações, permitindo um uso mais eficiente e otimizado.
Este guia tem como objetivo explorar duas estruturas de dados lineares: a lista encadeada simples e a lista duplamente encadeada.
Uma lista encadeada, diferentemente de um array, não aloca os dados em espaços de memória contíguos. Cada elemento é denominado nó e a conexão entre eles é feita por meio de ponteiros. O primeiro nó da lista é chamado de cabeça.
O tamanho de uma lista encadeada é flexível, adaptando-se à necessidade de alocação de mais ou menos nós, sempre respeitando os limites de memória disponíveis no dispositivo.
Existem duas variações principais de listas encadeadas, que serão exploradas em detalhe a seguir.
#1. Lista Encadeada Simples
Uma lista encadeada simples se caracteriza por possuir um único ponteiro em cada nó, que aponta para o próximo nó na sequência. Cada nó armazena um dado e um ponteiro para o próximo elemento da lista.
O último nó da lista tem um ponteiro nulo (None), indicando o término da cadeia.
Veja uma representação gráfica de uma lista encadeada simples:
Após essa breve introdução, vamos aprender a implementar uma lista encadeada simples utilizando Python.
Implementação da Lista Encadeada Simples
1. O primeiro passo é definir a estrutura do nó.
Como fazer isso?
Em Python, a criação de um nó é simplificada pelo uso de classes. A classe nó terá dois atributos: um para armazenar os dados e outro para o ponteiro para o próximo nó.
Segue o código para criação do nó:
class Node:
def __init__(self, data):
self.data = data
self.next = None
Com a classe acima, podemos gerar nós de diferentes tipos. Veremos como fazer isso em breve.
Agora que temos o nó, podemos criar uma lista encadeada com múltiplos nós. Para isso, criaremos uma outra classe chamada `LinkedList`.
2. A classe `LinkedList` é inicializada com o atributo head configurado como None. Veja o código abaixo.
class LinkedList:
def __init__(self):
self.head = None
3. Já temos as classes `Node` e `LinkedList`. Mas como inserimos um novo nó na lista encadeada? Uma solução é criar um método na classe `LinkedList`. Vamos criar um método para essa finalidade.
Para inserir um nó, devemos seguir os seguintes passos:
- Verificar se a cabeça (
head) da lista está vazia. - Se estiver vazia, atribuir o novo nó à cabeça.
- Se a cabeça não estiver vazia, encontrar o último nó da lista.
- Atribuir o novo nó ao ponteiro
nextdo último nó.
A seguir, o código que implementa a inserção de um novo nó:
class LinkedList:
def insert(self, new_node):
if self.head:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
else:
self.head = new_node
Maravilha! Concluímos o método para inserir nós. Mas como podemos acessar os dados de cada nó da lista?
Para percorrer a lista, devemos usar o ponteiro next, da mesma forma como fizemos para encontrar o último nó. Vamos criar um método na classe `LinkedList` para exibir todos os dados dos nós.
4. Abaixo, os passos para exibir os dados:
- Iniciar uma variável com a cabeça da lista (
head). - Criar um loop para percorrer a lista até o final.
- Exibir os dados do nó.
- Avançar para o próximo nó usando o ponteiro
next.
Veja o código:
class LinkedList:
def display(self):
temp_node = self.head
while temp_node:
print(temp_node.data, end='->')
temp_node = temp_node.next
print('Null')
Concluimos a criação da lista com os métodos essenciais. Para testar, vamos instanciar a lista com alguns dados.
Podemos criar nós usando o construtor Node(valor). O código completo com exemplos de uso está abaixo:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self, new_node):
if self.head:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
else:
self.head = new_node
def display(self):
temp_node = self.head
while temp_node:
print(temp_node.data, end='->')
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
linked_list = LinkedList()
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))
linked_list.display()
Ao executar o código acima, o resultado será:
1->2->3->4->5->6->7->Null
Com isso, você aprendeu a criar e utilizar uma lista encadeada simples. Agora, o próximo passo é explorar a lista duplamente encadeada, que se baseia nos conceitos que acabamos de aprender.
#2. Lista Duplamente Encadeada
A lista duplamente encadeada, ao contrário da simples, usa dois ponteiros por nó: um que aponta para o nó anterior e outro para o próximo nó. Assim, cada nó armazena um dado e dois ponteiros.
O ponteiro para o nó anterior do primeiro nó da lista e o ponteiro para o próximo nó do último nó são nulos, indicando as extremidades da lista.
Veja abaixo uma representação de uma lista duplamente encadeada:
A implementação de uma lista duplamente encadeada é semelhante à da lista simples. Ao invés de explicar os mesmos passos novamente, o código será apresentado em etapas e você verá como é fácil de entender.
Implementação da Lista Duplamente Encadeada
1. Criação do nó para a lista duplamente encadeada, com ponteiros para o nó anterior, os dados e o ponteiro para o próximo nó.
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
2. Classe da lista duplamente encadeada.
class LinkedList:
def __init__(self):
self.head = None
3. Método para inserir um novo nó na lista duplamente encadeada.
class LinkedList:
def insert(self, new_node):
if self.head:
last_node = self.head
while last_node.next:
last_node = last_node.next
new_node.prev = last_node
last_node.next = new_node
4. Método para exibir os dados da lista duplamente encadeada.
class LinkedList:
def display(self):
print("Ordem Normal: ", end='')
temp_node = self.head
while temp_node:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
print("Ordem Inversa: ", end='')
last_node = self.head
while last_node.next:
last_node = last_node.next
temp_node = last_node
while temp_node:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
O código para a lista duplamente encadeada foi apresentado. Para testar, crie a lista com alguns dados, de forma similar ao que fizemos para a lista simples. Use sua criatividade para experimentar 🙂
Conclusão
Existem inúmeros problemas que podem ser resolvidos com o uso de listas encadeadas. O conhecimento básico da implementação dessas estruturas, como apresentado neste tutorial, é fundamental para que você possa aprofundar seus estudos. Esperamos que este conteúdo tenha sido útil e agradável.
Bons estudos e boa codificação! 🙂