Como usar a estrutura de dados Linked List em Python?

Listas Encadeadas em Python: Uma Introdução

Por Pedro Pregueiro

Entendendo Listas Encadeadas

As listas encadeadas são como uma prima menos conhecida das listas. Elas não são tão populares ou tão legais, e você pode nem se lembrar delas da sua aula de algoritmos. Mas, no contexto certo, elas podem realmente se destacar.

Neste artigo, você aprenderá:

• O que são listas encadeadas e quando você deve usá-las
• Como usar collections.deque para todas as suas necessidades de listas encadeadas
• Como implementar suas próprias listas encadeadas
• Quais são os outros tipos de listas encadeadas e para que eles podem ser usados

Se você está procurando aprimorar suas habilidades de codificação para uma entrevista de emprego ou se deseja aprender mais sobre estruturas de dados em Python além dos dicionários e listas usuais, veio ao lugar certo!

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

Conceitos Principais

Antes de aprofundarmos no que são as listas encadeadas e como utilizá-las, você deve primeiro entender como elas são estruturadas. Cada elemento de uma lista encadeada é chamado de nó, e cada nó possui dois campos diferentes:

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

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

(NODE IMAGE)

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 pela lista. O último nó deve ter sua referência next apontando para None para determinar o final da lista. Aqui está como se parece:

(LINKED LIST IMAGE)

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

Aplicações Práticas

As listas encadeadas têm uma variedade de usos no mundo real. Elas podem ser usadas para implementar (spoiler alert) estruturas de dados como filas, pilhas e árvores. As vantagens das listas encadeadas incluem a capacidade de inserir e remover elementos de forma eficiente e a flexibilidade para manipular estruturas de dados dinâmicas.

Imagine que você esteja desenvolvendo um aplicativo de tarefas em que os usuários possam adicionar, remover e reorganizar tarefas. Usar uma lista encadeada para armazenar as tarefas pode ser uma escolha inteligente. Cada tarefa poderia ser representada por um nó na lista encadeada, com o campo next indicando a próxima tarefa. Isso permitiria aos usuários adicionar, remover e reorganizar facilmente as tarefas, pois basta manipular as referências nos nós da lista encadeada.

Agora que exploramos as aplicações práticas das listas encadeadas, vamos comparar o desempenho delas com o desempenho das listas tradicionais.

Comparação de Desempenho: Listas vs Listas Encadeadas

Embora as listas encadeadas ofereçam vantagens em termos de flexibilidade e eficiência na inserção e remoção de elementos, elas têm algumas desvantagens. Em particular, o acesso aleatório a um elemento em uma lista encadeada é mais lento do que em uma lista tradicional.

Quando você deseja obter um elemento em uma posição específica em uma lista, uma lista tradicional permite o acesso direto ao elemento pelo seu índice. Em contraste, em uma lista encadeada, você precisa iterar pelos nós até chegar ao nó desejado. Isso requer mais tempo e processamento.

No entanto, quando você precisa inserir ou remover elementos em uma lista, as listas encadeadas têm vantagem. Nessas operações, uma lista encadeada pode ser mais rápida e mais eficiente do que uma lista tradicional. Isso ocorre porque, ao inserir ou remover um elemento em uma lista tradicional, é necessário realocar os elementos seguintes na memória para abrir espaço. Em uma lista encadeada, por outro lado, basta ajustar as referências nos nós correspondentes para inserir ou remover um elemento.

Agora que você entende as principais diferenças de desempenho entre listas e listas encadeadas, vamos explorar algumas soluções prontas do Python para lidar com listas encadeadas.

Apresentando collections.deque

O módulo collections do Python oferece uma estrutura de dados chamada deque que é uma excelente opção para implementar listas encadeadas. deque significa “double-ended queue” (fila de duas pontas) e permite inserir e remover elementos tanto no início quanto no final da fila de forma eficiente.

Como Usar collections.deque

Para usar collections.deque, você precisa importar o módulo collections e criar uma instância de deque. Aqui está um exemplo de como fazer isso:

from collections import deque

my_list = deque()

Agora você pode adicionar elementos à sua lista encadeada usando os métodos append() ou appendleft() para inserir um elemento no final ou no início da lista, respectivamente. Veja um exemplo:

my_list.append(1)
my_list.appendleft(2)

Você também pode remover elementos da lista encadeada usando os métodos pop() ou popleft() para remover um elemento do final ou do início da lista, respectivamente. Aqui está um exemplo:

my_list.pop()
my_list.popleft()

Além disso, deque também fornece outros métodos úteis, como remove(), clear() e extend(), que podem ser usados para manipular a lista encadeada de forma flexível.

Agora que você sabe como usar collections.deque para criar e manipular listas encadeadas, vamos ver como implementar sua própria lista encadeada em Python.

Implementando Sua Própria Lista Encadeada

Embora collections.deque seja uma solução pronta e conveniente para a maioria das necessidades de listas encadeadas, você também pode implementar sua própria lista encadeada em Python. Isso pode ser útil se você estiver estudando estruturas de dados ou quiser aprender a criar suas próprias implementações.

Criando uma Lista Encadeada

Para criar sua própria lista encadeada, você precisa definir uma classe Node para representar cada nó e uma classe LinkedList para representar a lista encadeada em si. Aqui está um exemplo de implementação:

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

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

Nesta implementação, a classe Node possui um atributo data para armazenar o valor do nó e um atributo next para armazenar a referência para o próximo nó. A classe LinkedList possui um atributo head para representar o primeiro nó da lista.

Percorrendo uma Lista Encadeada

Depois de criar uma lista encadeada, você pode percorrê-la para acessar e manipular seus elementos. Para percorrer uma lista encadeada, você precisa iterar pelos nós começando pelo nó head até atingir o final da lista (quando a referência next de um nó for None). Aqui está um exemplo de como fazer isso:

def traverse(self):
    current = self.head
    while current:
        print(current.data)
        current = current.next

Neste exemplo, a função traverse() percorre a lista encadeada, imprimindo o valor de cada nó. Ela começa pelo nó head e avança para o próximo nó até atingir o final da lista.

Inserindo um Novo Nó

Além de percorrer uma lista encadeada, você também pode inserir novos nós nela. Para inserir um novo nó, você precisa criar uma instância de Node com o valor desejado e ajustar as referências dos nós adjacentes para incluir o novo nó. Aqui está um exemplo de como fazer isso:

def insert(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

Neste exemplo, a função insert() cria um novo nó com o valor fornecido e o insere no final da lista. Se a lista estiver vazia (ou seja, self.head for None), o novo nó se torna o nó head. Caso contrário, a função percorre a lista até o último nó e ajusta a referência next do último nó para o novo nó.

Removendo um Nó

Além de inserir nós, você também pode remover nós de uma lista encadeada. Para remover um nó, você precisa ajustar as referências dos nós adjacentes para ignorar o nó que será removido. Aqui está um exemplo de como fazer isso:

def remove(self, data):
    if not self.head:
        return
    if self.head.data == data:
        self.head = self.head.next
    else:
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

Neste exemplo, a função remove() procura o nó com o valor fornecido e o remove da lista. Se o nó a ser removido for o nó head, a função ajusta self.head para a referência do próximo nó. Caso contrário, a função percorre a lista até encontrar o nó anterior ao nó a ser removido e ajusta a referência next do nó anterior para o nó seguinte ao nó a ser removido.

Agora que você sabe como criar, percorrer, inserir e remover nós de uma lista encadeada, vamos dar uma olhada em alguns tipos avançados de listas encadeadas.

Usando Listas Encadeadas Avançadas

Além das listas encadeadas simples, existem duas variações avançadas de listas encadeadas que você pode usar, dependendo dos requisitos do seu programa: listas encadeadas duplamente encadeadas e listas circulares.

Como Usar Listas Encadeadas Duplamente Encadeadas

As listas encadeadas duplamente encadeadas são semelhantes às listas encadeadas simples, mas cada nó contém duas referências: uma para o próximo nó e outra para o nó anterior. Essa estrutura de dados permite percorrer a lista em ambas as direções: do início para o fim e do fim para o início.

Para implementar uma lista encadeada duplamente encadeada, você precisa adicionar um atributo previous à classe Node e ajustar as operações de inserção e remoção para lidar com as duas referências. Aqui está um exemplo de como fazer isso:

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

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

Nesta implementação, a classe Node possui um novo atributo previous para representar a referência ao nó anterior. A classe DoublyLinkedList é semelhante à LinkedList anterior, mas adiciona a capacidade de percorrer a lista em ambas as direções.

Como Usar Listas Encadeadas Circulares

As listas encadeadas circulares são semelhantes às listas encadeadas simples, mas o último nó tem sua referência next apontando para o primeiro nó, em vez de apontar para None. Com essa estrutura de dados, é possível percorrer a lista de forma contínua, repetindo os elementos indefinidamente.

Para implementar uma lista encadeada circular, você só precisa ajustar a referência next do último nó para o primeiro nó em vez de None. Aqui está um exemplo de como fazer isso:

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

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

Nesta implementação, a classe CircularLinkedList é semelhante à LinkedList anterior, mas a lista é considerada circular porque a referência next do último nó aponta para o primeiro nó.

Agora que você conhece os princípios básicos das listas encadeadas, é hora de concluir.

Conclusão

As listas encadeadas são uma estrutura de dados eficiente e flexível que pode ser usada para implementar várias soluções. Elas têm vantagens em operações de inserção e remoção e são úteis em situações em que você precisa manipular estruturas de dados dinâmicas.

Ao usar Python para trabalhar com listas encadeadas, você tem a opção de usar a estrutura deque do módulo collections ou de implementar suas próprias classes Node e LinkedList. Também é possível explorar variações avançadas, como listas encadeadas duplamente encadeadas e listas encadeadas circulares, dependendo das necessidades do seu programa.

Agora que você está familiarizado com as listas encadeadas e suas aplicações, você pode experimentar e aplicar esses conceitos em seus próprios projetos Python. Divirta-se codificando e explorando as possibilidades das listas encadeadas!