Estruturas de Dados — Arrays, Listas Ligadas, Árvores e Grafos

Estruturas de dados são formas de organizar dados para que tarefas comuns, como busca, inserção, remoção e percurso, fiquem mais fáceis. Se você quer entender arrays, listas ligadas, árvores e grafos, a forma mais rápida é fazer duas perguntas: que formato os dados têm e qual operação precisa parecer barata?

Se os dados formam uma sequência, um array costuma ser o ponto de partida. Se cada item aponta principalmente para o próximo, uma lista ligada pode servir. Se os dados têm níveis, use uma árvore. Se os itens podem se conectar em muitas direções, use um grafo.

Aqui está a regra útil mais curta:

• Array: melhor para ordem indexada.
• Lista ligada: melhor para ligações locais encadeadas.
• Árvore: melhor para hierarquia.
• Grafo: melhor para redes.

O que arrays, listas ligadas, árvores e grafos realmente fazem

Um array armazena itens em uma ordem fixa e permite referir-se diretamente a uma posição, como "item $7$". Na implementação contígua usual, essa indexação direta é $O(1)$.

Uma lista ligada armazena itens como nós, em que cada nó aponta para outro nó. Você pode ir de nó em nó, mas para chegar ao item de número $n$ normalmente precisa percorrer os nós anteriores, então o acesso por posição costuma ser $O(n)$.

Uma árvore armazena dados em níveis. Cada nó pode ter filhos, então a estrutura representa naturalmente aninhamentos, como pastas dentro de pastas. Os custos de busca e atualização dependem do tipo de árvore e de ela permanecer balanceada.

Um grafo armazena nós e arestas. Diferentemente de uma árvore, um nó pode se conectar a muitos outros de formas arbitrárias, e ciclos são permitidos. Isso faz dos grafos o modelo natural para estradas, redes sociais e mapas de dependência.

Comparação rápida: quando cada estrutura de dados se encaixa

Structure	Best mental model	Usually good at	Common limitation
Array	Uma linha numerada de itens	Acesso direto por índice	Inserções e remoções no meio geralmente exigem deslocar itens
Linked list	Uma cadeia de nós	Inserir ou remover perto de um nó conhecido	Acesso aleatório é lento
Tree	Uma hierarquia ramificada	Representar níveis e relações de pai e filho	O comportamento depende muito do tipo de árvore
Graph	Uma rede de conexões	Alcançabilidade, caminhos e relações	Os algoritmos costumam ser mais complexos

Exemplo resolvido: escolhendo estruturas em um app de campus

Suponha que você esteja criando um app de campus com uma tela de horários, um catálogo de disciplinas e um mapa de caminhada. A forma mais fácil de escolher uma estrutura de dados é relacionar cada recurso ao formato dos seus dados.

As abas dos dias da semana em uma tela de horários são naturalmente um array:

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

O recurso principal é o acesso direto por posição. "Mostre a aba $3$" faz sentido, e a ordem importa.

O catálogo de disciplinas é naturalmente uma árvore:

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

Cada nível contém o próximo nível. Isso é uma hierarquia, então uma árvore é o modelo mais limpo.

Os caminhos entre prédios são naturalmente um grafo. Um prédio pode se conectar a vários outros, e os caminhos podem formar ciclos. Se você quer a rota mais curta da biblioteca até o laboratório, está resolvendo um problema de grafo, não de árvore.

Uma lista ligada se encaixa em uma parte mais específica do mesmo app: uma cadeia de telas visitadas recentemente, se a operação principal for avançar ou voltar um passo por vez. Nesse caso, cada tela precisa principalmente de links para telas próximas, e não de acesso rápido à $20$ª tela.

A lição é que o "melhor" depende da tarefa. Um único produto pode usar várias estruturas de dados porque partes diferentes dos dados têm relações diferentes.

Como diferenciá-los rapidamente

Muitos estudantes aprendem isso primeiro como palavras de vocabulário. Isso faz o tema parecer abstrato, mas a pergunta prática é mais simples.

Pergunte: qual operação deve parecer barata?

Se você quer que "ir para a posição $i$" seja barato, arrays são fortes. Se você quer que "seguir a próxima conexão" seja barato, estruturas ligadas ajudam. Se você quer "descer por uma hierarquia", árvores se encaixam. Se você quer "descobrir se duas coisas estão conectadas", grafos se encaixam.

Erros comuns ao aprender estruturas de dados

Supor que uma estrutura é sempre a mais rápida

Não existe vencedora universal. O que é "rápido" depende do que você faz com mais frequência e da implementação.

Tratar árvores como automaticamente eficientes

Algumas árvores permitem buscas muito eficientes, mas isso depende do tipo de árvore e de condições estruturais, como balanceamento. Uma árvore mal formada pode ter desempenho muito pior do que uma balanceada.

Escolher uma lista ligada só porque inserção parece barata

A inserção pode ser barata quando você já tem o nó certo. Encontrar esse nó ainda pode custar tempo.

Usar uma árvore quando os dados na verdade formam um grafo

Se um item pode ter vários pais, ligações cruzadas ou ciclos, forçar os dados em uma árvore pode esconder a estrutura real e tornar operações futuras desajeitadas.

Confundir uma estrutura abstrata com um recurso da linguagem

"Array", "list", "map" ou "tree" em uma linguagem de programação podem vir com escolhas de implementação que afetam uso de memória e velocidade. A ideia abstrata e o contêiner concreto estão relacionados, mas não são idênticos.

Quando arrays, listas ligadas, árvores e grafos são usados

Arrays são usados para coleções ordenadas, tabelas, buffers e qualquer caso em que a posição importa.

Listas ligadas aparecem em implementações especializadas em que atualizações locais de ponteiros importam mais do que acesso aleatório.

Árvores são usadas para dados hierárquicos, como sistemas de arquivos, estrutura de documentos, árvores de expressão e muitos índices de busca.

Grafos são usados para rotas, análise de dependências, modelagem de redes, links de recomendação e problemas de conexão em geral.

Como escolher a estrutura de dados certa

Comece fazendo duas perguntas:

1. Que relação os dados têm: sequência, hierarquia ou rede?
2. Qual operação importa mais: indexação, atualização local, percurso hierárquico ou encontrar caminhos?

Essas duas respostas geralmente reduzem rapidamente as opções.

Se você ainda estiver em dúvida, desenhe uma versão pequena dos dados no papel. Muitas vezes, a imagem revela a estrutura antes do código.

Experimente sua própria versão

Escolha três exemplos familiares, como uma playlist, um sistema de pastas e um mapa de transporte. Identifique se cada um é principalmente uma sequência, uma hierarquia ou uma rede, e então escolha a estrutura que torna a operação principal fácil. Se quiser outro caso para se testar, o GPAI Solver pode gerar exemplos parecidos de classificação.