Pular para o conteúdo
CodeMDD.io | Coding Tutorials

Como usar a lista encadeada no Python?

[

Listas Encadeadas em Python: Uma Introdução

por Pedro Pregueiro data-structures intermediário

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 servem.

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 diferencia das listas normais? As listas encadeadas diferem das listas na forma como armazenam elementos na memória. Enquanto as listas usam um bloco de memória contíguo para armazenar referências aos seus dados, as listas encadeadas armazenam referências como parte dos seus próprios elementos.

Conceitos Principais

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

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

Veja como um nó típico se parece:

Node
┌─────────┬─────────┐
│  Dado   │ Próximo │
├─────────┼─────────┤
│ valor_1 │   ref   │
└─────────┴─────────┘
Linked List
┌─────────┬─────────┐     ┌─────────┬─────────┐     ┌─────────┬─────────┐
│  Dado   │ Próximo │     │  Dado   │ Próximo │     │  Dado   │ Próximo │
├─────────┼─────────┤     ├─────────┼─────────┤     ├─────────┼─────────┤
│ valor_1 │ ref_1   ├────>│ valor_2 │ ref_2   ├────>│ valor_3 │   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!) árvores binárias, grafos, pilhas, filas e muito mais. A principal vantagem das listas encadeadas em relação às listas tradicionais é a flexibilidade de adicionar ou remover elementos em qualquer local sem precisar realocar toda a lista.

Comparação de Performance: Listas vs. Listas Encadeadas

Embora as listas encadeadas possam ser mais flexíveis em termos de inserção e remoção de elementos, elas têm uma desvantagem em relação às listas tradicionais: o acesso aos elementos. Enquanto em uma lista tradicional é possível acessar qualquer elemento diretamente com uma complexidade de tempo O(1), nas listas encadeadas o acesso a um elemento requer percorrer toda a lista, resultando em uma complexidade de tempo O(n), onde n é igual ao tamanho da lista.

Introduzindo collections.deque

A biblioteca padrão do Python fornece uma implementação de listas encadeadas chamada collections.deque. Essa classe oferece todas as funcionalidades de uma lista encadeada e é eficiente para operações de inserção e remoção tanto no início quanto no final da lista.

Como Utilizar collections.deque

Para usar collections.deque, você precisa importar a biblioteca collections:

import collections

Em seguida, você pode criar uma lista encadeada vazia chamando o construtor deque():

linked_list = collections.deque()

A partir disso, você pode usar os métodos append() e appendleft() para inserir elementos no final e no início da lista, respectivamente:

linked_list.append(1)  # Insere 1 no final da lista
linked_list.appendleft(2)  # Insere 2 no início da lista

Você também pode usar pop() e popleft() para remover elementos do final e do início da lista, respectivamente:

last_element = linked_list.pop()  # Remove o último elemento da lista
first_element = linked_list.popleft()  # Remove o primeiro elemento da lista

Implementando sua Própria Lista Encadeada

Embora collections.deque seja uma ótima opção para a maioria dos casos de uso de listas encadeadas, em alguns casos pode ser necessário implementar sua própria lista encadeada personalizada. Felizmente, Python oferece uma estrutura de dados chamada namedtuple que pode facilitar a implementação.

Como Criar uma Lista Encadeada

Para criar uma lista encadeada personalizada, você pode usar namedtuple para definir a estrutura de cada nó da lista:

from collections import namedtuple


# Define a estrutura de um nó da lista encadeada
Node = namedtuple("Node", ["data", "next"])


# Cria os nós da lista encadeada
node1 = Node(1, None)
node2 = Node(2, None)
node3 = Node(3, None)

A partir disso, você pode criar uma lista encadeada atribuindo o nó inicial à cabeça da lista:

head = node1

E para fazer o encadeamento dos nós, basta atribuir a referência do próximo nó ao campo next de cada nó:

node1.next = node2
node2.next = node3

Dessa forma, você criou sua própria lista encadeada personalizada!

Como Percorrer uma Lista Encadeada

Para percorrer uma lista encadeada, você precisa começar do nó inicial e percorrer cada nó sucessor procurando pelo nó final, que possui a referência next igual a None. Você pode usar um loop while para realizar essa iteração:

current_node = head


while current_node is not None:
    print(current_node.data)
    current_node = current_node.next

Este código imprimirá o valor de cada nó da lista encadeada.

Como Inserir um Novo Nó

Para inserir um novo nó em uma lista encadeada, você precisa atribuir a referência do novo nó ao campo next do nó anterior e atualizar a referência do novo nó para o próximo nó da lista. Por exemplo, para inserir um novo nó entre o nó 1 e o nó 2:

new_node = Node(4, None)


new_node.next = node2
node1.next = new_node

Agora, o novo nó está inserido corretamente na lista.

Como Remover um Nó

Para remover um nó de uma lista encadeada, você precisa atualizar a referência do nó anterior para apontar para o próximo nó da lista, ignorando o nó que será removido. Por exemplo, para remover o nó 2:

node1.next = node3

Agora, o nó 2 não faz mais parte da lista encadeada.

Utilizando Listas Encadeadas Avançadas

Além da lista encadeada simples que vimos até agora, existem outros tipos de listas encadeadas mais avançadas que podem ser úteis em diferentes cenários.

Como Usar Listas Encadeadas Duplamente Ligadas

Uma lista encadeada duplamente ligada, ou doubly linked list em inglês, é uma lista em que cada nó possui tanto uma referência para o próximo nó quanto uma referência para o nó anterior. Isso permite percorrer a lista em ambas as direções.

Em Python, é possível implementar uma lista encadeada duplamente ligada criando uma classe Node com dois campos: data que armazena o valor do nó, prev que armazena a referência para o nó anterior, e next que armazena a referência para o próximo nó.

Veja um exemplo de implementação de uma lista encadeada duplamente ligada:

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


# Cria os nós da lista encadeada duplamente ligada
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)


# Encadeia os nós na lista
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2

Agora você pode percorrer essa lista tanto do início para o fim quanto do fim para o início.

Como Usar Listas Encadeadas Circulares

Uma lista encadeada circular, ou circular linked list em inglês, é uma lista em que o último nó possui uma referência para o primeiro nó, criando um loop circular. Isso permite percorrer a lista indefinidamente sem um fim claro.

Em Python, é possível implementar uma lista encadeada circular criando uma classe Node com dois campos: data que armazena o valor do nó, e next que armazena a referência para o próximo nó. Além disso, é necessário ajustar a referência do último nó para apontar para o primeiro nó.

Veja um exemplo de implementação de uma lista encadeada circular:

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


# Cria os nós da lista encadeada circular
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)


# Encadeia os nós na lista
node1.next = node2
node2.next = node3
node3.next = node1

Agora você pode percorrer essa lista indefinidamente.

Conclusão

Neste artigo, você aprendeu sobre listas encadeadas em Python. Você viu como listas encadeadas são estruturadas, suas aplicações práticas e a comparação de performance com as listas tradicionais. Além disso, você aprendeu como usar collections.deque para implementar listas encadeadas de forma eficiente, e como implementar sua própria lista encadeada personalizada usando namedtuple. Também foi apresentado o conceito de listas encadeadas duplamente ligadas e listas encadeadas circulares.

Agora você está pronto para explorar e utilizar as listas encadeadas em seus próprios projetos em Python. Divirta-se codificando!