Como usar a lista encadeada utilizando Python?

[

Listas Encadeadas em Python: Uma Introdução

por Pedro Pregueiro data-structures intermediate

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 lista encadeada
Como implementar suas próprias listas encadeadas
Quais são os outros tipos de listas encadeadas e para que eles podem ser usados

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

Entendendo Listas Encadeadas

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

Conceitos Principais

Antes de aprofundar no que são as listas encadeadas e como você pode usá-las, primeiro você precisa entender 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:

Node

Linked List

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 servem para uma variedade de propósitos no mundo real. Elas podem ser usadas para implementar (spoiler alert) filas (queues) e pilhas (stacks), bem como resolver problemas como encontrar o último nó de uma lista ou o tamanho de uma lista.

Uma das principais vantagens das listas encadeadas é que elas permitem a inserção e remoção eficientes de elementos em qualquer posição da lista, mesmo quando a lista já está cheia de elementos. Isso ocorre porque, ao contrário das listas normais, que requerem realocação e cópia de todos os elementos em caso de inserção ou remoção em uma posição intermediária, as listas encadeadas simplesmente atualizam as referências dos nós adjacentes.

Outra aplicação comum é a implementação de uma estrutura de dados de lista circular, onde o último nó aponta para o primeiro nó, formando um ciclo.

Comparação de Desempenho: Listas vs Listas Encadeadas

Embora as listas encadeadas ofereçam flexibilidade e eficiência para inserção e remoção de elementos, elas nem sempre são a melhor opção em termos de desempenho para todas as operações. Listas encadeadas requerem acesso sequencial aos nós, o que pode ser menos eficiente para pesquisas e iterações.

Já as listas normais, feitas com arrays, oferecem acesso direto aos elementos pelo seu índice, permitindo pesquisas rápidas. Entretanto, a inserção ou remoção de elementos em uma posição intermediária de uma lista normal requer a realocação e cópia de todos os elementos subsequentes.

Portanto, ao decidir entre uma lista encadeada e uma lista normal, leve em consideração qual operação é mais frequente em seu caso de uso específico. Se você precisa de acesso rápido e frequente à posição dos elementos, ou se você não precisa de inserção/remoção de elementos em posições intermediárias, uma lista normal pode ser a melhor opção. Caso contrário, uma lista encadeada pode ser mais adequada.

Apresentando collections.deque

A biblioteca padrão do Python fornece a classe collections.deque. Essa classe implementa uma estrutura de dados de fila duplamente encadeada, que combina as características de uma lista encadeada com a eficiência de uma lista normal.

Como Usar collections.deque

Para usar collections.deque, primeiro você precisa importar a biblioteca collections. Em seguida, você pode criar uma instância de deque informando os elementos iniciais da fila, se necessário. Veja um exemplo:

from collections import deque

fila = deque([1, 2, 3, 4, 5])
print(fila)  # Saída: deque([1, 2, 3, 4, 5])

A partir daí, você pode usar métodos como append(), appendleft(), pop(), popleft(), extend(), extendleft(), entre outros, para inserir e remover elementos da fila. Por exemplo:

fila.append(6)  # Inserir elemento no final: [1, 2, 3, 4, 5, 6]
fila.appendleft(0)  # Inserir elemento no início: [0, 1, 2, 3, 4, 5, 6]
fila.pop()  # Remover elemento do final: [0, 1, 2, 3, 4, 5]
fila.popleft()  # Remover elemento do início: [1, 2, 3, 4, 5]

Como Implementar Filas e Pilhas

As listas encadeadas são frequentemente usadas para implementar filas (queues) e pilhas (stacks). Com collections.deque, você pode facilmente implementar essas estruturas de dados em Python.

Para implementar uma fila com collections.deque, você pode usar os métodos append() para a inserção de elementos e popleft() para a remoção do primeiro elemento inserido:

from collections import deque

fila = deque()
fila.append(1)
fila.append(2)
fila.append(3)
primeiro_elemento = fila.popleft()

print(primeiro_elemento)  # Saída: 1
print(fila)  # Saída: deque([2, 3])

Para implementar uma pilha com collections.deque, você pode usar os métodos append() para a inserção de elementos e pop() para a remoção do último elemento inserido:

from collections import deque

pilha = deque()
pilha.append(1)
pilha.append(2)
pilha.append(3)
ultimo_elemento = pilha.pop()

print(ultimo_elemento)  # Saída: 3
print(pilha)  # Saída: deque([1, 2])

Dessa forma, você pode aproveitar a flexibilidade das listas encadeadas implementadas como collections.deque para criar e manipular filas e pilhas em Python.

Implementando Sua Própria Lista Encadeada

Embora a classe collections.deque seja muito útil para a maioria dos casos onde você precisa de uma lista encadeada, pode haver situações em que você precise implementar sua própria versão personalizada. Nesses casos, você pode criar sua própria classe em Python para representar uma lista encadeada.

Como Criar uma Lista Encadeada

Para criar sua própria lista encadeada, você precisará definir uma classe que represente os nós da lista. Cada nó deve ter um campo de dados e um campo de referência para o próximo nó. Veja um exemplo de como você pode criar uma lista encadeada básica em Python:

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

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

Neste exemplo, a classe Node representa um nó da lista encadeada e armazena o valor do nó (data) e uma referência para o próximo nó (next). A classe LinkedList representa a lista encadeada em si e tem um campo de referência para o primeiro nó (head).

Como Percorrer uma Lista Encadeada

Uma operação comum em listas encadeadas é percorrer todos os nós da lista para acessar os dados ou executar alguma operação neles. Para fazer isso, você pode usar um laço while para percorrer os nós até chegar ao final da lista (quando a referência next do último nó for None).

Veja um exemplo de como percorrer uma lista encadeada e imprimir os valores dos nós:

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

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

# Exemplo de uso:
lista = LinkedList()
lista.head = Node(1)
segundo_no = Node(2)
terceiro_no = Node(3)
lista.head.next = segundo_no
segundo_no.next = terceiro_no

lista.traverse()

Neste exemplo, a função traverse() percorre os nós da lista encadeada a partir do nó head, imprimindo o valor de cada nó. A saída será:

1
2
3

Como Inserir um Novo Nó

Outra operação comum em listas encadeadas é a inserção de um novo nó em uma posição específica da lista. Para fazer isso, você precisará ajustar as referências dos nós adjacentes ao novo nó para manter a integridade da lista.

Veja um exemplo de como inserir um novo nó em uma lista encadeada existente:

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

    def insert(self, data, position):
        new_node = Node(data)
        if position == 0:
            new_node.next = self.head
            self.head = new_node
            return
        current = self.head
        for _ in range(position - 1):
            if current.next is None:
                break
            current = current.next
        new_node.next = current.next
        current.next = new_node

# Exemplo de uso:
lista = LinkedList()
lista.head = Node(1)
segundo_no = Node(3)
terceiro_no = Node(4)
lista.head.next = segundo_no
segundo_no.next = terceiro_no

lista.insert(2, 1)
lista.traverse()

Neste exemplo, a função insert() insere um novo nó com o valor 2 na posição 1 da lista encadeada. Para fazer isso, ela percorre os nós até a posição desejada e ajusta as referências dos nós adjacentes ao novo nó. A saída será:

Como Remover um Nó

A remoção de um nó em uma lista encadeada é semelhante à inserção. Você precisará ajustar as referências dos nós adjacentes ao nó que está sendo removido para manter a integridade da lista.

Veja um exemplo de como remover um nó de uma lista encadeada existente:

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

    def remove(self, position):
        if position == 0:
            self.head = self.head.next
            return
        current = self.head
        for _ in range(position - 1):
            if current.next is None:
                break
            current = current.next
        if current is None or current.next is None:
            return
        current.next = current.next.next

# Exemplo de uso:
lista = LinkedList()
lista.head = Node(1)
segundo_no = Node(2)
terceiro_no = Node(3)
lista.head.next = segundo_no
segundo_no.next = terceiro_no

lista.remove(1)
lista.traverse()

Neste exemplo, a função remove() remove o nó da posição 1 da lista encadeada, ajustando as referências dos nós adjacentes. A saída será:

1
3

Com essas operações básicas de inserção, remoção e percorrimento, você pode criar e manipular suas próprias listas encadeadas em Python.

Usando Listas Encadeadas Avançadas

Além das listas encadeadas básicas, existem outros tipos de listas encadeadas que oferecem recursos adicionais. Alguns exemplos incluem as listas encadeadas duplamente encadeadas e circulares.

Como Usar Listas Encadeadas Duplamente Encadeadas

As listas encadeadas duplamente encadeadas são semelhantes às listas encadeadas básicas, mas cada nó possui referências para o nó anterior e o nó seguinte. Isso permite percorrer a lista em qualquer direção, tornando mais fácil e eficiente a remoção de nós em uma posição específica.

Para usar listas encadeadas duplamente encadeadas em Python, você precisará ajustar a estrutura da classe Node para incluir uma referência para o nó anterior:

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

A partir daí, você precisará ajustar a implementação das operações de inserção, remoção e percorrimento para levar em consideração as referências para o nó anterior.

Como Usar Listas Encadeadas Circulares

As listas encadeadas circulares são semelhantes às listas encadeadas básicas, mas o último nó da lista aponta para o primeiro nó, formando um ciclo. Isso permite percorrer a lista indefinidamente, como em uma lista circular.

Para usar listas encadeadas circulares em Python, você precisará ajustar a estrutura da classe LinkedList para incluir um campo para o último nó da lista:

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

A partir daí, você precisará ajustar a implementação das operações de inserção, remoção e percorrimento para levar em consideração o último nó da lista.

Conclusão

As listas encadeadas podem ser uma estrutura de dados poderosa e eficiente para várias situações. Elas oferecem flexibilidade para a manipulação de elementos e permitem inserções e remoções eficientes. No entanto, as listas encadeadas não são a melhor opção em todos os casos e podem ser menos eficientes para certas operações, como pesquisas.

Ao usar listas encadeadas em Python, você pode aproveitar a biblioteca collections.deque para implementar facilmente listas encadeadas eficientes. Mas se você precisar de uma funcionalidade mais específica ou quiser criar sua própria versão personalizada, pode implementar uma lista encadeada do zero.

Espero que este artigo tenha dado a você uma boa introdução às listas encadeadas em Python e que você esteja pronto para explorar ainda mais esse tópico! Se você quiser aprofundar seus conhecimentos, confira também o curso em vídeo recomendado: Working With Linked Lists in Python.