Arrays e listas ligadas

Uma rua de casas numeradas vs uma caça ao tesouro

Um array é uma rua onde as casas são numeradas em sequência e todas têm o mesmo tamanho. Você quer a casa 47? Não precisa perguntar a ninguém: multiplica e vai direto. Mas se quiser inserir uma casa nova entre a 10 e a 11, todo mundo da 11 em diante precisa se mudar uma casa para a frente.

Uma lista ligada é uma caça ao tesouro: cada pista diz onde está a próxima. Para inserir uma pista nova no meio, basta reescrever duas pistas — ninguém se muda. Mas para chegar à 47ª pista você tem que seguir as 46 anteriores, uma por uma.

Veja o custo real de cada operação

Insira e remova nas duas estruturas e observe quantos elementos precisam se mover. Repare nos endereços de memória: no array eles são consecutivos; na lista ligada são aleatórios.

Array: aritmética de endereços

# Um array é um bloco contíguo de memória.
# Endereço do elemento i = base + i * tamanho_do_elemento
#
#   base = 0x1000, cada int ocupa 8 bytes
#   lista[0] → 0x1000
#   lista[3] → 0x1000 + 3*8 = 0x1018
#
# A CPU calcula isso com uma multiplicação e uma soma: O(1).
# Não importa se o array tem 10 ou 10 bilhões de elementos.

lista = [12, 45, 7, 83]

lista[2]                # O(1)  — aritmética de endereço
lista.append(99)        # O(1)* — só escreve no fim
lista.insert(0, 99)     # O(n)  — desloca TODOS os elementos
lista.pop()             # O(1)  — remove do fim
lista.pop(0)            # O(n)  — desloca todos para a esquerda
99 in lista            # O(n)  — precisa comparar um a um

# * amortizado. Veja "array dinâmico" mais abaixo.

Array dinâmico: por que append é O(1) amortizado

A list do Python, o ArrayList do Java e o Vec do Rust não são arrays de tamanho fixo: são arrays dinâmicos. Eles guardam mais capacidade do que o necessário e dobram quando enchem.

# Por que append é O(1) AMORTIZADO e não O(1) puro?
#
# Um array tem tamanho fixo na memória. Quando enche, a linguagem:
#   1. aloca um array novo com o DOBRO da capacidade
#   2. copia todos os n elementos                    ← O(n)
#   3. libera o array antigo
#
# Capacidade: 4 → 8 → 16 → 32 → 64 ...
# Inserindo 64 elementos, as cópias custam 4+8+16+32 = 60 operações.
# Somando: ~2n operações para n inserções → 2 por inserção, em média.
#
# É por isso que dobrar (e não somar +1) é essencial:
# crescer de 1 em 1 daria O(n) por inserção — O(n²) no total.

import sys
lista = []
for i in range(20):
    lista.append(i)
    print(len(lista), sys.getsizeof(lista))  # veja os saltos de capacidade

Lista ligada: nós e ponteiros

# Uma lista ligada: nós espalhados pela memória, conectados por ponteiros.
class No:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None      # ponteiro para o próximo nó

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

    def inserir_inicio(self, valor):   # O(1) — sem deslocar nada
        no = No(valor)
        no.proximo = self.head
        self.head = no

    def buscar(self, valor):           # O(n) — caminha nó a nó
        atual = self.head
        while atual:
            if atual.valor == valor:
                return atual
            atual = atual.proximo
        return None

    def remover_depois(self, no):      # O(1) — só religa um ponteiro
        if no.proximo:
            no.proximo = no.proximo.proximo

# Não existe "lista[500]". Para chegar no 500º nó,
# é preciso seguir 500 ponteiros — um de cada vez.

O fator que o Big O esconde: cache

# O detalhe que os livros de complexidade não contam:
# a CPU não lê 1 byte da RAM — ela lê uma LINHA DE CACHE (64 bytes).
#
# Array: os elementos são vizinhos na memória.
#   Ler lista[0] já traz lista[1..7] para o cache L1 de graça.
#   Percorrer 1 milhão de ints = ~125 mil buscas na RAM.
#
# Lista ligada: cada nó está num lugar aleatório.
#   Cada "atual = atual.proximo" pode ser um cache miss.
#   Percorrer 1 milhão de nós = ~1 milhão de buscas na RAM.
#
# Um cache miss custa ~100x mais que um acerto no L1.
# Na prática, percorrer um array pode ser 10-50x mais rápido que
# percorrer uma lista ligada — mesmo os dois sendo O(n).
#
# Por isso listas ligadas puras são raras em código moderno:
# o Python usa array dinâmico para list, o Java prefere ArrayList
# a LinkedList, e o C++ recomenda vector como padrão.

Construindo do zero

Mini projeto: implemente seu próprio array dinâmico. Comece com um array de capacidade 2 (em Python, use uma list de tamanho fixo preenchida com None, ou o módulo array). Implemente append, get(i) e __len__, dobrando a capacidade quando encher. Imprima o número total de cópias após 1000 inserções e compare com a previsão teórica de ~2n.

Projeto principal: implemente uma lista duplamente ligada completa com inserir_inicio, inserir_fim, remover(no) e iteração nos dois sentidos. Depois use-a para escrever um histórico de navegador: botões "voltar" e "avançar" que andam pela lista sem recriar nada. Compare com fazer o mesmo usando duas pilhas — qual fica mais simples?

Desafio extra: detecte se uma lista ligada tem um ciclo (o último nó aponta de volta para algum nó anterior) usando apenas O(1) de memória extra. A resposta é o algoritmo da lebre e da tartaruga de Floyd: dois ponteiros, um andando 1 nó por vez e outro 2. Se houver ciclo, eles se encontram. Prove por que isso sempre funciona.

Teste sua intuição

Onde você encontra isso