Estruturas de dados essenciais: arrays, listas ligadas, pilhas e filas

Estruturas de dados são as formas organizadas de armazenar e acessar dados em memória. Algoritmos e estruturas de dados são inseparáveis: o algoritmo certo na estrutura de dados errada pode ser ineficiente; a estrutura certa torna algoritmos simples e eficientes. Em quase todas as entrevistas técnicas de nível pleno em diante, o candidato é avaliado tanto pelo algoritmo proposto quanto pela estrutura de dados escolhida. Este artigo cobre as quatro estruturas fundamentais que todo programador precisa dominar.

Array (lista/vetor)

Array é a estrutura mais básica: elementos armazenados em posições contíguas de memória, acessados por índice. O acesso por índice é O(1) — independente do tamanho, acessar o elemento na posição 5 ou na posição 5 milhões é igualmente rápido. Inserção/remoção no meio é O(n) — todos os elementos após o ponto de inserção precisam ser deslocados.

# Em Python, listas são arrays dinâmicos
frutas = ["maçã", "banana", "laranja"]

# O(1) — acesso por índice
print(frutas[1])  # banana

# O(1) amortizado — adicionar ao final
frutas.append("uva")

# O(n) — inserir no meio (desloca elementos)
frutas.insert(1, "manga")

# O(n) — remover elemento (desloca elementos)
frutas.remove("banana")

Use arrays quando: acesso aleatório por índice é frequente, os dados são de tamanho relativamente fixo, ou operações no final são mais comuns que no meio.

Lista Ligada (Linked List)

Na lista ligada, cada elemento (nó) armazena o dado e um ponteiro para o próximo nó. Não há índices — para chegar ao 5º elemento, você percorre do início. A vantagem: inserção e remoção em qualquer posição é O(1) quando você já tem o ponteiro para o nó anterior — sem deslocamento de memória.

class No:
    def __init__(self, dado):
        self.dado = dado
        self.proximo = None

class ListaLigada:
    def __init__(self):
        self.cabeca = None

    def inserir_inicio(self, dado):
        novo = No(dado)
        novo.proximo = self.cabeca
        self.cabeca = novo

    def imprimir(self):
        atual = self.cabeca
        while atual:
            print(atual.dado, end=" -> ")
            atual = atual.proximo
        print("None")

ll = ListaLigada()
ll.inserir_inicio(3)
ll.inserir_inicio(2)
ll.inserir_inicio(1)
ll.imprimir()  # 1 -> 2 -> 3 -> None

Use lista ligada quando: inserções/remoções frequentes no início ou em posições arbitrárias (dado o ponteiro), e acesso aleatório por índice não é necessário. Na prática, arrays dinâmicos modernos (como Python list) superam listas ligadas na maioria dos casos por melhor comportamento de cache.

Pilha (Stack) — LIFO

Pilha é uma estrutura LIFO (Last In, First Out — último a entrar, primeiro a sair). Operações: push (empilhar), pop (desempilhar), peek (ver o topo sem remover). Contextos reais: função de desfazer (Ctrl+Z), o call stack do próprio Python ao chamar funções, validação de parênteses balanceados, expressões matemáticas.

from collections import deque

pilha = deque()
pilha.append("ação 1")   # push
pilha.append("ação 2")   # push
pilha.append("ação 3")   # push

print(pilha.pop())  # "ação 3" — LIFO
print(pilha.pop())  # "ação 2"

# Verificar parênteses balanceados com pilha
def parenteses_balanceados(s):
    pilha = []
    pares = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            pilha.append(char)
        elif char in ')]}':
            if not pilha or pilha[-1] != pares[char]:
                return False
            pilha.pop()
    return len(pilha) == 0

print(parenteses_balanceados("({[]})"))  # True
print(parenteses_balanceados("({[})"))   # False

Fila (Queue) — FIFO

Fila é FIFO (First In, First Out — primeiro a entrar, primeiro a sair). Operações: enqueue (enfileirar), dequeue (desenfileirar). Contextos reais: processamento de pedidos em ordem de chegada, impressoras, BFS (Busca em Largura em grafos), sistemas de mensageria.

from collections import deque

fila = deque()
fila.append("pedido 1")   # enqueue
fila.append("pedido 2")   # enqueue
fila.append("pedido 3")   # enqueue

print(fila.popleft())  # "pedido 1" — FIFO
print(fila.popleft())  # "pedido 2"

Use collections.deque para filas em Python — não listas. list.pop(0) é O(n) (desloca todos os elementos); deque.popleft() é O(1).