Estruturas de dados essenciais: escolher a estrutura certa é escolher o desempenho

A decisão que a maioria toma no automático#

Boa parte do código que escrevemos toma uma decisão silenciosa e enorme sem nenhum pensamento consciente: qual estrutura de dados usar para guardar uma coleção de coisas. Na maioria das linguagens, o reflexo é pegar a lista ou o array padrão e seguir em frente. Funciona — até que não funciona, e o programa que era instantâneo com cem itens engasga com cem mil. Nesse momento fica evidente que a escolha da estrutura de dados não é um detalhe de implementação; é uma das decisões de maior impacto no desempenho de um programa, e ela costuma ser tomada no piloto automático.

O que torna essa escolha tão consequente é que cada estrutura de dados oferece um conjunto diferente de trade-offs. Nenhuma é a melhor em tudo; cada uma é excelente em certas operações e péssima em outras. Escolher bem significa conhecer o padrão de acesso do seu problema — o que você vai fazer com os dados com mais frequência: buscar? inserir? percorrer em ordem? — e casar esse padrão com a estrutura cujos pontos fortes coincidem com ele. Este artigo percorre as estruturas fundamentais não como um catálogo a decorar, mas como um repertório de trade-offs para reconhecer.

Notação Big-O: a linguagem para falar de custo#

Antes das estruturas, precisamos da língua para comparar seus custos, e essa língua é a notação Big-O. Ela descreve como o custo de uma operação cresce conforme o tamanho da entrada aumenta, ignorando constantes e detalhes de máquina para focar no que importa em escala: o formato da curva.

As classes que você mais vai encontrar, da melhor para a pior:

• O(1) — constante. O custo não depende do tamanho. Acessar um elemento de array por índice, ou buscar numa hash table, custa o mesmo com dez ou dez milhões de itens. É o ideal.
• O(log n) — logarítmico. O custo cresce devagar; dobrar a entrada adiciona apenas um passo. Busca binária e busca em árvores balanceadas vivem aqui. Excelente.
• O(n) — linear. O custo cresce na mesma proporção da entrada. Percorrer uma coleção inteira. Aceitável, muitas vezes inevitável.
• O(n log n). O melhor que algoritmos de ordenação de propósito geral conseguem. Bom.
• O(n²) — quadrático. O custo cresce com o quadrado. Dois laços aninhados sobre a mesma coleção. Fica perigoso rápido: dobrar a entrada quadruplica o tempo.

A intuição central é que a diferença entre essas classes não é de grau, é de categoria. Um algoritmo O(n²) e um O(n log n) podem ter desempenho parecido com cem itens; com um milhão, o primeiro pode levar horas enquanto o segundo leva segundos. É por isso que a análise assintótica importa: ela prevê onde seu código vai bater no muro muito antes de o muro aparecer. E o mesmo raciocínio se aplica ao espaço, não só ao tempo — algumas estruturas trocam memória por velocidade, e essa troca precisa ser consciente.

Array e lista ligada: o trade-off fundador#

O par mais didático de estruturas — array e lista ligada — ilustra o princípio do trade-off na sua forma mais pura, porque as duas guardam uma sequência de elementos e ainda assim têm perfis de desempenho quase opostos.

Um array guarda os elementos em posições contíguas de memória. Isso dá a ele um superpoder: acesso por índice em O(1). Quer o milésimo elemento? O computador calcula seu endereço diretamente e vai lá, sem percorrer nada. A contiguidade também traz um benefício que a notação Big-O esconde mas que é enorme na prática: localidade de cache. Como os elementos estão lado a lado na memória, percorrer um array é extremamente rápido no hardware real, porque o processador carrega blocos inteiros de uma vez. O preço do array é a inserção e remoção no meio: para abrir espaço, é preciso deslocar todos os elementos seguintes — O(n).

Uma lista ligada guarda cada elemento num nó separado que aponta para o próximo. Isso inverte o perfil: inserir ou remover é O(1) se você já está na posição, porque basta reajustar os ponteiros, sem deslocar nada. Mas acessar o milésimo elemento exige seguir mil ponteiros a partir do início — O(n). E, por os nós estarem espalhados pela memória, a lista ligada sofre com péssima localidade de cache, o que a torna, na prática, bem mais lenta do que a análise assintótica sugere para percursos.

A lição que esse par ensina vale para todas as outras estruturas: não existe estrutura universalmente melhor. O array vence quando você acessa por posição e percorre muito; a lista ligada vence em cenários de inserção e remoção frequentes em pontos que você já tem em mãos. Escolher é conhecer o seu padrão de uso. Vale um aviso prático: por causa da localidade de cache, o array (ou a lista dinâmica que a maioria das linguagens oferece por padrão) é a escolha certa com muito mais frequência do que a intuição de "listas ligadas são flexíveis" sugere.

Hash table: a estrutura que parece mágica#

Se uma estrutura merece o título de cavalo de batalha da programação moderna, é a hash table (tabela de dispersão), conhecida como dicionário, mapa ou objeto dependendo da linguagem. Sua promessa é notável: inserção, busca e remoção por chave, todas em O(1) no caso médio. Você guarda um valor associado a uma chave e recupera esse valor quase instantaneamente, não importa quantos milhões de entradas existam.

O mecanismo por trás é elegante. Uma função de hash transforma a chave num número, que é usado para calcular diretamente a posição onde o valor fica guardado — daí o acesso em tempo constante, sem busca. Quando duas chaves diferentes geram a mesma posição (uma colisão), a estrutura tem estratégias para resolver, tipicamente guardando os itens conflitantes juntos naquela posição. Enquanto as colisões são raras — o que uma boa função de hash e um dimensionamento adequado garantem — o desempenho permanece próximo de O(1).

O "caso médio" na promessa esconde a letra miúda que vale conhecer: no pior caso, com muitas colisões, uma hash table pode degradar para O(n). Isso raramente acontece com dados normais e boas implementações, mas é a razão pela qual hash tables não oferecem uma coisa que às vezes você precisa: ordem. Os elementos numa hash table não têm ordenação previsível; se você precisa percorrer as chaves em ordem crescente, ou encontrar "todos os valores entre X e Y", a hash table não ajuda — e é aí que entram as árvores.

Árvores: ordem e hierarquia#

As árvores resolvem o que a hash table não oferece: manter os dados ordenados enquanto ainda permitem busca eficiente. Uma árvore de busca binária balanceada guarda os elementos de forma que, a partir de qualquer nó, tudo à esquerda é menor e tudo à direita é maior. Isso permite buscar, inserir e remover em O(log n) — mais lento que o O(1) da hash table, mas com o benefício decisivo de manter a ordem.

Essa ordem habilita operações que a hash table não consegue fazer com eficiência: encontrar o menor ou o maior elemento, percorrer tudo em ordem crescente, e — talvez o mais importante — consultas por faixa, como "todos os registros entre estas duas datas". Não por acaso, é uma variante de árvore (a B-tree) que os bancos de dados usam para seus índices: ela oferece exatamente a combinação de busca rápida e suporte a faixas que consultas de banco exigem. Quando você entende árvores, entende por que um índice de banco acelera uma busca por igualdade e também uma por intervalo.

A palavra balanceada carrega um peso que vale destacar. Uma árvore de busca só garante O(log n) se permanecer equilibrada — com profundidade parecida em todos os ramos. Uma árvore que degenera (por exemplo, inserindo elementos já ordenados numa implementação ingênua) vira essencialmente uma lista ligada, com busca O(n). É por isso que as estruturas usadas na prática são árvores auto-balanceadas, que rearranjam-se automaticamente para manter a profundidade sob controle. O balanceamento é o que separa a promessa da árvore da sua degeneração.

Grafos, pilhas e filas: modelando o problema#

Além das estruturas de armazenamento, há estruturas que modelam relações e fluxos, e reconhecer quando um problema pede uma delas é metade da solução.

O grafo — nós conectados por arestas — é a estrutura para modelar relacionamentos: redes sociais (pessoas conectadas a pessoas), mapas (locais conectados por rotas), dependências entre tarefas, a própria web de páginas e links. Uma quantidade surpreendente de problemas que não parecem "sobre grafos" se resolve elegantemente ao serem enxergados como grafos — encontrar o caminho mais curto, detectar ciclos, ordenar tarefas respeitando dependências. Aprender a reconhecer a estrutura de grafo escondida num problema é uma das habilidades mais transferíveis da computação.

A pilha (LIFO — o último a entrar é o primeiro a sair) e a fila (FIFO — o primeiro a entrar é o primeiro a sair) são estruturas simples com aplicações onipresentes. A pilha modela o histórico de "desfazer", a pilha de chamadas de funções, a avaliação de expressões. A fila modela filas de tarefas, buffers, o processamento de mensagens na ordem de chegada. São estruturas de acesso restrito — você só mexe numa ponta — e essa restrição é justamente o que as torna a modelagem correta para esses problemas.

O caso amortizado: por que o array dinâmico funciona#

Um detalhe que confunde muita gente merece esclarecimento, porque ele revela uma sutileza importante da análise de custo. O array tem tamanho fixo, mas as listas dinâmicas que quase todas as linguagens oferecem por padrão crescem conforme você adiciona elementos. Como elas conciliam o acesso O(1) por índice do array com a capacidade de crescer indefinidamente?

A resposta é elegante: por baixo, a lista dinâmica é um array que, quando enche, aloca um novo array maior — tipicamente o dobro do tamanho — e copia os elementos para ele. A cópia é uma operação O(n), o que à primeira vista parece arruinar a promessa de inserção barata no fim. Mas aqui entra o conceito de custo amortizado: como o array dobra de tamanho, essas cópias caras acontecem cada vez mais raramente conforme a lista cresce. Distribuído ao longo de muitas inserções, o custo médio de adicionar um elemento no fim permanece O(1) amortizado, mesmo com as cópias ocasionais.

Essa ideia — analisar o custo médio ao longo de uma sequência de operações, em vez do pior caso de uma operação isolada — é o que torna a lista dinâmica a estrutura de propósito geral certa para a esmagadora maioria dos casos. Você ganha a flexibilidade de crescer, mantém o acesso rápido por índice e a excelente localidade de cache do array, e paga um custo amortizado desprezível pelas realocações. É por isso que a recomendação prática é começar sempre com a lista dinâmica padrão da linguagem e só trocar por outra estrutura quando um padrão de acesso específico provar que ela é inadequada — a intuição de que estruturas mais "sofisticadas" são melhores costuma custar desempenho em vez de ganhá-lo.

Do repertório à intuição#

O objetivo de conhecer estruturas de dados não é decorar tabelas de complexidade para uma entrevista; é desenvolver a intuição que faz você, diante de um problema, perguntar automaticamente: "qual é o padrão de acesso aqui, e qual estrutura tem esse padrão como ponto forte?". Preciso de acesso por chave instantâneo? Hash table. Preciso de ordem e faixas? Árvore. Preciso modelar relações? Grafo. Vou inserir e remover nas pontas, em ordem? Pilha ou fila. Essa pergunta, feita cedo, evita a maioria dos problemas de desempenho antes que eles apareçam.

E o repertório de estruturas se conecta diretamente com o próximo desafio de qualquer programa que cresce: fazer várias coisas ao mesmo tempo sem corromper os dados que essas estruturas guardam. Estruturas compartilhadas entre tarefas concorrentes exigem cuidados que uma estrutura de uso sequencial nunca precisa — um tema que exploramos em concorrência e paralelismo. Escolher a estrutura certa resolve o desempenho de um fluxo único; protegê-la corretamente é o que mantém esse desempenho quando muitos fluxos disputam os mesmos dados.