Como Usar Listas Encadeadas em Python?

Lista Encadeada em Python: Uma Introdução

Neste artigo, você aprenderá:

O que são listas encadeadas e quando usar
Como usar collections.deque para todas as suas necessidades de lista encadeada
Como implementar suas próprias listas encadeadas
Quais são os outros tipos de listas encadeadas e para que podem ser usadas

Você pode acompanhar os exemplos deste tutorial baixando o código-fonte disponível no link abaixo:

Entendendo as Listas Encadeadas

Listas encadeadas são uma coleção ordenada de objetos. Então o que as torna diferentes das listas normais? Listas encadeadas diferem de listas na forma como elas armazenam elementos na memória. Enquanto listas usam um bloco de memória contíguo para armazenar referências aos seus dados, listas encadeadas armazenam as referências como parte dos seus próprios elementos.

Conceitos Principais

Antes de aprofundar no que são listas encadeadas e como você pode usá-las, você deve primeiro aprender como elas são estruturadas. Cada elemento de uma lista encadeada é chamado de nó e cada nó tem dois campos diferentes:

Dados contêm o valor a ser armazenado no nó.
Próximo contém uma referência para o próximo nó da lista.

Aqui está como um nó típico se parece:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

Uma lista encadeada é uma coleção de nós. O primeiro nó é chamado de head e é usado como ponto de partida para qualquer iteração através da lista. O último nó deve ter sua referência next apontando para None para determinar o fim da lista.

Aqui está como fica:

class LinkedList:
    def __init__(self):
        self.head = None

Agora que você sabe como uma lista encadeada é estruturada, está pronto para ver alguns casos de uso práticos.

Aplicações Práticas

Listas encadeadas têm diversas aplicações no mundo real. Elas podem ser usadas para implementar (spoiler alert) estruturas de dados como pilhas e filas, e são particularmente eficientes em cenários onde a inserção e a remoção de elementos são frequentes.

Além disso, as listas encadeadas também são usadas em algoritmos de pesquisa e classificação. Elas oferecem um desempenho melhor do que as listas tradicionais em certas situações, pois a inserção e a remoção de elementos requerem apenas a atualização dos ponteiros, em vez de realocar todo o bloco de memória como acontece com as listas.

Outra aplicação comum das listas encadeadas é para representar estruturas de dados complexas, como árvores e grafos.

collections.deque: Uma alternativa prática

Em Python, a biblioteca collections fornece a classe deque, que pode ser usada para implementar listas encadeadas de forma mais fácil e eficiente. A classe deque faz parte do módulo de collections e é uma implementação em C para acelerar as operações de inserção e remoção em ambos os extremos da lista.

Para começar a usar collections.deque como uma lista encadeada, você precisa importá-lo:

from collections import deque

Agora você pode criar uma instância de deque e adicionar elementos a ela. Aqui está um exemplo:

my_linked_list = deque()
my_linked_list.append(10)
my_linked_list.append(20)
my_linked_list.append(30)

Após adicionar os elementos à lista encadeada, você pode percorrê-la usando um loop for ou acessar elementos específicos pelo seu índice:

for element in my_linked_list:
    print(element)

# Output:
# 10
# 20
# 30

print(my_linked_list[1])  # Output: 20

A classe deque também fornece métodos úteis para adicionar e remover elementos da lista encadeada:

my_linked_list.appendleft(5)  # adiciona no início da lista
my_linked_list.append(40)  # adiciona no final da lista

print(my_linked_list)

# Output:
# deque([5, 10, 20, 30, 40])

my_linked_list.pop()  # remove o último elemento
my_linked_list.popleft()  # remove o primeiro elemento

print(my_linked_list)

# Output:
# deque([10, 20, 30])

Como você pode ver, usar collections.deque como uma lista encadeada em Python é bastante simples e conveniente.

Implementando sua própria Lista Encadeada

Se você deseja uma implementação mais personalizada de uma lista encadeada em Python, pode criar sua própria classe para isso.

Aqui está um exemplo de como criar uma lista encadeada simples:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

linked_list = LinkedList()

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

linked_list.head = node1
node1.next = node2
node2.next = node3

Neste exemplo, criamos uma classe Node que representa um nó individual na lista encadeada. Cada nó tem um campo data para armazenar o valor e um campo next para armazenar a referência para o próximo nó.

A classe LinkedList é responsável por gerenciar os nós e fornece métodos para adicionar, remover e percorrer a lista encadeada.

Agora você pode usar os métodos da classe LinkedList para manipular a lista encadeada. Por exemplo:

def print_linked_list(linked_list):
    current_node = linked_list.head
    while current_node:
        print(current_node.data)
        current_node = current_node.next

print_linked_list(linked_list)

# Output:
# 10
# 20
# 30

Este exemplo mostra como percorrer a lista encadeada e imprimir os valores de cada nó.

Conclusão

As listas encadeadas são uma estrutura de dados interessante e útil em certos contextos. Elas podem ser usadas para implementar pilhas, filas e ajudam a melhorar o desempenho em cenários onde a inserção e a remoção de elementos são frequentes.

Você pode usar a classe collections.deque fornecida pela biblioteca collections para aproveitar os benefícios das listas encadeadas sem precisar implementar tudo do zero.

Espero que você tenha achado este artigo útil e que tenha adquirido uma compreensão melhor das listas encadeadas em Python. Agora você está pronto para começar a usar essa estrutura de dados em seus projetos!