Estruturas de Dados

1 de outubro de 2026 · 19 min para ler

Leandro Andrade

Software Developer

Escolher a estrutura de dados certa é, muitas vezes, a diferença entre uma operação instantânea e uma que leva minutos. Este post reúne as principais estruturas, como cada uma se comporta e quando usá-las, com exemplos passo a passo.

Antes de começar: notação Big O

A notação Big O descreve como o custo de uma operação cresce à medida que a quantidade de dados (n) aumenta. Ela será usada ao longo de todo o texto.

Notação	Nome	Passos para `n = 1.000.000`	Exemplo
`O(1)`	constante	1	acessar um índice do array
`O(log n)`	logarítmica	~20	buscar em uma BST balanceada
`O(n)`	linear	1.000.000	percorrer uma linked list

informação

O(log n) significa que, a cada passo, o problema é dividido pela metade. Por isso, mesmo com 1 bilhão de itens, bastam cerca de 30 passos.

Estruturas lineares

Os elementos são organizados em sequência, um após o outro.

Array

Lista de valores armazenados em posições contíguas de memória, cada um identificado por um índice numérico.

Acesso direto em O(1). Como os elementos estão lado a lado e têm o mesmo tamanho, o endereço de qualquer posição é calculado com uma única conta:

endereço = endereço_base + (índice × tamanho_do_elemento)

base = 1000, elementos de 4 bytes
arr[3] → 1000 + (3 × 4) = 1012

Por isso, acessar arr[50] custa o mesmo que acessar arr[5].

Modificar é caro. Inserir um elemento no meio exige deslocar todos os elementos à direita:

Inserir 15 no índice 1:

[10][20][30][40]
[10][  ][20][30][40]   ← 20, 30 e 40 deslocados uma posição
[10][15][20][30][40]   ← O(n)

Em linguagens como C e Java, o tamanho é definido na criação. Para crescer, é preciso alocar um novo bloco de memória e copiar todos os valores. Em JavaScript e Python, os arrays são dinâmicos: a linguagem faz essa realocação automaticamente (geralmente dobrando a capacidade), por isso o push no final é O(1) amortizado.

Características:

leitura por índice rápida: O(1);
busca por valor lenta: O(n);
inserção e remoção no meio lentas: O(n).

Linked List

Criada para resolver o custo de modificação do array. É uma sequência de nodes em que cada node armazena um valor e um ponteiro para o próximo.

Os nodes não ficam lado a lado na memória: estão espalhados e conectados apenas pelos ponteiros.

Inserir X entre A e B exige atualizar apenas dois ponteiros, sem deslocar nada:

1. X.next = B        A → B → C
                     X ↗
2. A.next = X        A → X → B → C

Remover B é um bypass: basta fazer o anterior apontar para o seguinte.

A.next = B.next      A → C   (B fica sem referência)

O preço está na leitura: não existe índice. Para chegar ao quinto elemento, é preciso percorrer os quatro anteriores.

Atenção

A inserção e a remoção são O(1) somente se você já tiver a referência do node. Se for preciso procurar a posição antes, a operação passa a custar O(n).

Características:

leitura e busca lentas: O(n);
inserção e remoção rápidas: O(1), dada a referência do node.

Arquitetura

Na prática, arrays costumam ser mais rápidos do que o Big O sugere, pois elementos contíguos aproveitam melhor o cache da CPU. Nodes espalhados na memória causam mais cache misses.

Stack

Pilha. O último a entrar é o primeiro a sair (Last In, First Out — LIFO). Pense em uma pilha de pratos: o último prato colocado é o primeiro a ser retirado.

Toda operação acontece no topo:

push: adiciona no topo;
pop: remove do topo;
peek: consulta o topo sem remover.

Todas são O(1).

const stack = [];
stack.push('prato 1');
stack.push('prato 2');
stack.push('prato 3');

stack.pop(); // 'prato 3' → o último a entrar sai primeiro
stack.pop(); // 'prato 2'

Exemplos de uso:

desfazer alterações (Ctrl + Z);
botão "voltar" do navegador;
call stack durante a execução de um programa.

A call stack é o exemplo mais presente no dia a dia de quem programa:

main() chama render(), que chama draw_pixel():

  [draw_pixel()]  ← topo: finaliza primeiro
  [render()    ]
  [main()      ]  ← base: finaliza por último

Queue

Fila. O primeiro a entrar é o primeiro a sair (First In, First Out — FIFO). Funciona como a fila do caixa do supermercado.

enqueue: adiciona no final;
dequeue: remove do início.

          dequeue ← [A][B][C][D] ← enqueue
                   FRONT       BACK

dequeue() → retorna A          [B][C][D]
enqueue(E)                     [B][C][D][E]

As duas operações são O(1).

Atenção ao JavaScript

Usar array.shift() como dequeue pode custar O(n), pois todos os elementos são reindexados. Para filas grandes, prefira uma implementação com linked list ou com dois índices (início e fim).

Exemplos de uso: filas de mensagens, processamento de tarefas em ordem de chegada, buffer de impressão.

Deque

Double-Ended Queue (pronuncia-se "deck"). Permite adicionar e remover nas duas pontas, combinando o comportamento de stack e queue.

adiciona/remove → [A][B][C][D] ← adiciona/remove
                FRONT       BACK

observação

Não confunda deque (a estrutura) com dequeue (a operação de remover da queue).

Exemplos de uso:

streams de dados com janela deslizante: novos valores entram no final e os mais antigos saem do início;
scheduling: tarefas comuns entram no final, tarefas prioritárias entram no início.

[T1][T2][T3]
pushFront(T*) → [T*][T1][T2][T3]        ← prioritária passa na frente
pushBack(T4)  → [T*][T1][T2][T3][T4]    ← comum vai para o final

Estruturas baseadas em hash

Trocam um pouco de memória por acesso praticamente instantâneo.

Map

Armazena dados no formato chave → valor. Também conhecido como hash map, hash table ou dicionário.

Uma função de hash converte a chave em um número; o resto da divisão desse número pela quantidade de posições (buckets) indica onde o valor será guardado:

"Mom"  →  hash("Mom")  →  4827  →  4827 % 8  →  bucket 3
chave     função          número   8 buckets    posição

Para ler, o mesmo cálculo é refeito e o valor é encontrado direto no bucket, sem percorrer nada. Com 10 ou 10 mil registros, o acesso é O(1) em média.

Sem um map, encontrar um item exigiria percorrer a lista inteira: O(n).

const ages = new Map();
ages.set('ana', 30);
ages.set('bruno', 25);

ages.get('ana');   // 30 → O(1)
ages.has('carla'); // false

Colisões acontecem quando chaves diferentes geram a mesma posição. Elas são tratadas guardando mais de um item no mesmo bucket (chaining) ou procurando a próxima posição livre (open addressing). Quando a tabela fica cheia demais, ela é redimensionada (rehash).

Pior caso

Com muitas colisões, o acesso degrada para O(n). Uma boa função de hash e o redimensionamento automático mantêm isso raro.

Exemplos nas linguagens:

Python: dict;
JavaScript: Map e Object (prefira Map para chaves dinâmicas);
bancos de dados: índices do tipo hash (como o HASH do PostgreSQL). O índice padrão da maioria dos bancos, porém, é a B-tree, uma árvore que também permite buscas por intervalo.

Set

Um map apenas com chaves, sem valores. Responde à pergunta: este item existe?

acesso, inserção e remoção em O(1) em média;
não aceita valores duplicados.

const usernames = new Set(['ana', 'bruno']);
usernames.has('ana');    // true → nome indisponível
usernames.has('carla');  // false → nome disponível

// removendo duplicados de um dataset
[...new Set([1, 2, 2, 3, 3, 3])]; // [1, 2, 3]

Exemplos de uso:

verificar se um usuário já viu uma notificação;
remover duplicados de um dataset;
verificar se um username já está em uso.

Árvores

Estruturas hierárquicas. Cada variação adiciona regras que tornam algum tipo de operação mais eficiente.

Tree

Estrutura hierárquica formada por nodes com relação de pai e filho (parent e child). Exemplos: o sistema de arquivos do computador e o DOM do HTML.

Termos importantes:

root: o node inicial, sem pai;
parent / child: a relação entre um node e os nodes abaixo dele;
leaf: node sem filhos (documentos, fotos, nginx);
altura: o número de níveis entre a root e a leaf mais distante.

Em uma tree genérica, não há regra sobre onde cada valor fica. Para encontrar um item, pode ser necessário visitar todos os nodes: O(n).

Binary Search Tree (BST)

A BST é uma especialização da tree:

Tree
 └── Binary Tree          → no máximo 2 filhos por node
      └── Binary Search Tree → no máximo 2 filhos + regra de ordenação

A regra de ordenação vale para todos os nodes:

valores menores  ←  NODE  →  valores maiores

Por exemplo, para buscar o valor 37:

37 < 50 → esquerda
37 > 30 → direita
37 < 40 → esquerda
37 = 37 → encontrado em 4 passos

A cada comparação, metade da árvore restante é descartada. Por isso a busca é O(log n):

Quantidade de nodes	Tree genérica	BST balanceada
1.000	até 1.000 passos	~10 passos
1.000.000	até 1.000.000 passos	~20 passos
1.000.000.000	até 1.000.000.000 passos	~30 passos

Além da busca, a BST mantém os dados ordenados: percorrê-la em ordem (esquerda → node → direita) devolve os valores já ordenados, e buscas por intervalo (entre 30 e 45) são eficientes.

Árvore degenerada

Inserir valores já ordenados (1 → 2 → 3 → 4) gera uma árvore sem ramificações, que se comporta como uma linked list. A busca volta a ser O(n).

Para evitar isso existem as Self-Balancing BSTs, como AVL e Red-Black Tree. Após cada inserção ou remoção, elas fazem rotações nos nodes para manter a altura próxima de log n, garantindo O(log n) em qualquer cenário.

Binary Tree ≠ Binary Search Tree

A binary tree só limita cada node a dois filhos. A BST adiciona a regra de ordenação. Toda BST é uma binary tree, mas nem toda binary tree é uma BST.

Heap

Árvore binária em que o item de maior prioridade fica sempre no topo, disponível para acesso imediato. Existem dois tipos:

min-heap: o menor valor fica no topo (todo pai é menor ou igual aos filhos);
max-heap: o maior valor fica no topo (todo pai é maior ou igual aos filhos).

Diferente da BST, não há ordem entre irmãos: a única garantia é a relação entre pai e filhos. Na prática, a heap é armazenada em um array, onde os filhos do índice i estão em 2i + 1 e 2i + 2.

A estrutura se reorganiza sozinha a cada inserção ou remoção. Exemplo com uma min-heap [1, 3, 5, 7, 9, 8], inserindo 2:

Adiciona no final:            [1, 3, 5, 7, 9, 8, 2]
Compara com o pai (5): 2 < 5 → troca  [1, 3, 2, 7, 9, 8, 5]
Compara com o pai (1): 2 > 1 → para

Ao remover o topo, o último elemento ocupa o lugar dele e "desce" trocando com o menor filho até a regra voltar a valer.

Operação	Custo
consultar o topo	`O(1)`
inserir	`O(log n)`
remover o topo	`O(log n)`

Sem a heap, encontrar o maior item exigiria percorrer a lista (O(n)) ou reordená-la a cada inserção (O(n log n)).

Exemplos de uso:

filas de prioridade: o scheduler do sistema operacional decide qual processo usa a CPU;
recálculo de rotas no GPS: o algoritmo de Dijkstra usa uma min-heap para escolher o próximo caminho mais curto;
top-K: os 10 produtos mais vendidos entre milhões.

Trie

Também chamada de árvore de prefixos. Cada nível armazena uma letra, e cada caminho a partir da root forma uma palavra ou um prefixo.

Exemplo: buscar contatos na agenda do celular ao digitar jo:

j → desce para o node "j"
o → desce para o node "o"
retorna todas as palavras abaixo de "o": john, jordan, joseph

O custo da busca depende apenas do tamanho do prefixo (O(L)), e não da quantidade de palavras armazenadas. Duas letras digitadas, dois passos, seja a agenda de 100 ou de 1 milhão de contatos.

class Trie {
  constructor() {
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      node[char] ??= {};
      node = node[char];
    }
    node.isEnd = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node[char]) return false;
      node = node[char];
    }
    return true;
  }
}

Exemplos de uso: autocomplete, corretores ortográficos (spell checkers) e buscas em dicionários.

Grafos

Modelam relações arbitrárias entre elementos, sem a hierarquia das árvores.

Graph

Conjunto de vértices (nodes) conectados por arestas (edges). Dois vértices ligados por uma aresta são adjacentes, ou seja, vizinhos (neighbours).

Existem dois tipos principais:

não direcionado (undirected): a conexão vale nos dois sentidos. Exemplo: amizades no Facebook;
direcionado (directed): a aresta tem sentido. Exemplo: seguir alguém no X/Twitter não significa ser seguido de volta.

As arestas também podem ter peso, como a distância entre duas cidades em um mapa.

Considere o grafo não direcionado abaixo:

Há duas formas de armazená-lo:

Matriz de adjacência

Linhas e colunas representam os vértices; 1 indica uma aresta entre eles.

	1	2	3	4
1	0	1	1	0
2	1	0	0	1
3	1	0	0	1
4	0	1	1	0

Lista de adjacência

Cada vértice mantém uma lista com seus vizinhos.

→ [2, 3]
→ [1, 4]
→ [1, 4]
→ [2, 3]

Critério	Matriz de adjacência	Lista de adjacência
Memória	`O(V²)`	`O(V + E)`
Verificar se existe a aresta A–B	`O(1)`	`O(vizinhos de A)`
Melhor para	grafos densos	grafos esparsos (a maioria dos casos reais)

V = quantidade de vértices; E = quantidade de arestas.

Percorrendo um grafo

Existem duas estratégias clássicas, e cada uma usa uma estrutura vista anteriormente:

Depth-First Search (DFS): busca em profundidade. Segue um caminho até o fim antes de voltar. Usa uma stack (ou recursão);
Breadth-First Search (BFS): busca em largura. Visita todos os vizinhos antes de avançar um nível. Usa uma queue.

Partindo de A:
DFS → A, B, D, E, C, F   (desce até o fim de cada ramo)
BFS → A, B, C, D, E, F   (visita nível por nível)

dica

Em grafos sem peso, a BFS encontra o menor caminho entre dois vértices, pois visita primeiro tudo o que está a 1 aresta, depois a 2, e assim por diante.

Exemplos de uso:

conexões em redes sociais ("amigos de amigos");
mapas e navegação;
links entre páginas web;
dependências entre pacotes (npm).

Disjoint Set (Union-Find)

Rastreia quais elementos pertencem ao mesmo grupo. Possui duas operações:

find(x): retorna o líder (representante) do grupo de x;
union(a, b): une os grupos de a e b em um só.

Cada elemento começa como seu próprio grupo e seu próprio líder. Dois elementos estão no mesmo grupo se, e somente se, têm o mesmo líder.

Início:        [0] [1] [2] [3] [4] [5]

union(0, 1)    [0 1] [2] [3] [4] [5]
union(2, 3)    [0 1] [2 3] [4] [5]
union(4, 5)    [0 1] [2 3] [4 5]
union(1, 3)    [0 1 2 3] [4 5]

find(0) === find(2)  → true   (mesmo grupo)
find(0) === find(4)  → false  (grupos diferentes)

Compressão de caminho (path compression): ao executar find, cada elemento visitado passa a apontar diretamente para o líder. As próximas consultas ficam mais curtas, ou seja, quanto mais a estrutura é usada, mais eficiente ela se torna.

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) this.parent[rootB] = rootA;
  }
}

Combinada com a união por tamanho (union by size), que pendura o grupo menor no maior, as operações ficam praticamente O(1) amortizado.

Exemplos de uso:

redes: saber se dois computadores estão conectados;
processamento de imagem: identificar quais pixels formam a mesma região;
algoritmo de Kruskal: construir a árvore geradora mínima de um grafo.

Estruturas especializadas

Resolvem problemas específicos combinando ou adaptando as estruturas anteriores.

Bloom Filter

Estrutura de dados probabilística que verifica rapidamente se um elemento possivelmente pertence a um conjunto. Internamente, é apenas um array de bits, todos iniciados em 0, e algumas funções de hash.

Como funciona:

adicionar: o elemento passa por k funções de hash. Cada resultado, dividido pelo tamanho do array, gera um índice (o resto da divisão). Os bits desses índices viram 1;
consultar: o elemento passa pelas mesmas funções. Se algum bit for 0, o elemento com certeza não foi adicionado. Se todos forem 1, ele talvez tenha sido.

Na prática, as k funções costumam ser derivadas de uma só, variando uma seed concatenada ao input:

índice₁ = hash(input + "a1") % tamanho
índice₂ = hash(input + "a2") % tamanho
índice₃ = hash(input + "a3") % tamanho

Exemplo com 10 bits e 3 funções de hash (índices ilustrativos):

adiciona "maria" → índices 1, 4, 7
adiciona "joao"  → índices 3, 4, 8

índice:  0  1  2  3  4  5  6  7  8  9
bits:   [0][1][0][1][1][0][0][1][1][0]

consulta "pedro" → índices 2, 4, 7 → bit 2 é 0     → NÃO existe (certeza)
consulta "ana"   → índices 1, 3, 8 → todos são 1  → TALVEZ exista (falso positivo!)

"ana" nunca foi adicionada, mas seus índices foram marcados por outros elementos. Esse é o falso positivo.

As garantias são assimétricas:

garante que um elemento não existe;
não garante que um elemento existe.

informação

A taxa de falsos positivos é controlada pelo tamanho do array e pela quantidade de funções de hash. Na versão clássica, não é possível remover elementos, pois zerar um bit afetaria outros elementos que o compartilham.

Cenário de uso: conjuntos com milhões de registros em que a maioria das consultas é por elementos inexistentes e cada ida ao banco é cara. Bancos como Cassandra e RocksDB usam bloom filters para evitar leituras desnecessárias em disco.

LRU Cache

Least Recently Used (menos recentemente usado). É uma política que define o que descartar quando o cache fica cheio: sai o item que está há mais tempo sem ser acessado.

Item:            [A]   [B]   [C]    [D]   [E]
Último acesso:   5m    1m    10m    3m    8m

Cache cheio → remove C (está há mais tempo sem uso)

observação

O critério é recência, não frequência. Um item muito usado no passado, mas esquecido há horas, será removido. A política que considera frequência é a LFU (Least Frequently Used).

A implementação clássica combina duas estruturas:

Map: localiza qualquer item em O(1);
Doubly Linked List: mantém a ordem de uso. O item usado mais recentemente vai para o início e o menos usado fica no final. Mover ou remover um node é O(1).

Quando o cache está cheio, basta remover o último node da lista. Assim, tanto get quanto put são O(1).

Capacidade: 3 (mais recente à esquerda)

put(A)   → [A]
put(B)   → [B][A]
put(C)   → [C][B][A]
get(A)   → [A][C][B]      ← A foi usado, volta para o início
put(D)   → [D][A][C]      ← cache cheio: B (final) é removido

Em JavaScript, o Map preserva a ordem de inserção, o que permite uma implementação enxuta. Aqui, a ordem é invertida: o primeiro item do Map é o menos recente.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value); // move para o final (mais recente)
    return value;
  }

  put(key, value) {
    this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const oldest = this.cache.keys().next().value;
      this.cache.delete(oldest); // remove o menos recente
    }
  }
}

A memória é limitada, e o sistema está o tempo todo decidindo o que manter. Descartar o que não é usado é o que mantém o acesso ao restante rápido. Exemplos: cache de páginas do sistema operacional, cache do navegador e políticas de eviction do Redis.

Resumo

Estrutura	Busca/Acesso	Inserção	Remoção	Use quando...
Array	`O(1)` por índice	`O(n)` no meio	`O(n)` no meio	a leitura por posição predomina
Linked List	`O(n)`	`O(1)`*	`O(1)`*	há muitas inserções e remoções
Stack	`O(1)` no topo	`O(1)`	`O(1)`	o mais recente deve sair primeiro
Queue	`O(1)` no início	`O(1)`	`O(1)`	a ordem de chegada importa
Deque	`O(1)` nas pontas	`O(1)`	`O(1)`	é preciso operar nas duas pontas
Map / Set	`O(1)` médio	`O(1)` médio	`O(1)` médio	é preciso busca por chave ou unicidade
BST balanceada	`O(log n)`	`O(log n)`	`O(log n)`	os dados devem ficar ordenados
Heap	`O(1)` no topo	`O(log n)`	`O(log n)`	a prioridade define a ordem
Trie	`O(L)`	`O(L)`	`O(L)`	há buscas por prefixo
Union-Find	~`O(1)`	—	—	é preciso saber se itens estão conectados
Bloom Filter	`O(k)`	`O(k)`	—	é preciso descartar inexistentes rapidamente
LRU Cache	`O(1)`	`O(1)`	`O(1)`	a memória é limitada e o acesso recente importa

* dada a referência do node. L = tamanho da palavra; k = quantidade de funções de hash.

Conclusão

Não existe estrutura de dados perfeita, existem trade-offs. O array é rápido para ler e lento para modificar; a linked list é o oposto. O map troca memória por acesso instantâneo. O bloom filter troca precisão por espaço. A BST só entrega O(log n) se estiver balanceada.

Muitas estruturas são, na verdade, combinações das mais simples: a BFS usa uma queue, a DFS usa uma stack e o LRU cache une um map a uma doubly linked list. Entender os blocos básicos é o que permite reconhecer qual deles resolve o problema à sua frente.

Antes de escolher, pergunte: qual operação o meu sistema executa com mais frequência? A resposta costuma apontar a estrutura certa.

Antes de começar: notação Big O​

Estruturas lineares​

Array​

Linked List​

Stack​

Queue​

Deque​

Estruturas baseadas em hash​

Map​

Set​

Árvores​

Tree​

Binary Search Tree (BST)​

Heap​

Trie​

Grafos​

Graph​

Matriz de adjacência​

Lista de adjacência​

Percorrendo um grafo​

Disjoint Set (Union-Find)​

Estruturas especializadas​

Bloom Filter​

LRU Cache​

Resumo​

Conclusão​

Referências​

Antes de começar: notação Big O

Estruturas lineares

Array

Linked List

Stack

Queue

Deque

Estruturas baseadas em hash

Map

Set

Árvores

Tree

Binary Search Tree (BST)

Heap

Trie

Grafos

Graph

Matriz de adjacência

Lista de adjacência

Percorrendo um grafo

Disjoint Set (Union-Find)

Estruturas especializadas

Bloom Filter

LRU Cache

Resumo

Conclusão

Referências