icardb
Estruturas de Dados Essenciais: Guia Prático para Entrevistas e Projetos Reais
Voltar para artigosPROGRAMAÇÃO

Estruturas de Dados Essenciais: Guia Prático para Entrevistas e Projetos Reais

Por Redação icardb Publicado em Atualizado em 7 min de leitura

Todo programa manipula dados. A forma como organizamos esses dados — a estrutura escolhida — determina a eficiência das operações de busca, inserção, remoção e travessia. Estruturas de dados bem escolhidas reduzem complexidade de O(n²) para O(log n) ou até O(1). Este guia cobre as estruturas essenciais que aparecem em projetos reais e entrevistas técnicas.

Arrays e listas encadeadas

Arrays armazenam elementos em blocos contíguos de memória. O acesso por índice é O(1), mas inserções e remoções no meio exigem deslocamento de elementos — O(n). Listas encadeadas (linked lists) usam nós com ponteiros para o próximo elemento. Inserção e remoção são O(1) se o ponteiro for conhecido, mas acesso aleatório requer travessia O(n).

typescript
// Lista encadeada simples
class ListNode<T> {
  value: T;
  next: ListNode<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

// Inserção no início — O(1)
function prepend<T>(head: ListNode<T> | null, value: T): ListNode<T> {
  const node = new ListNode(value);
  node.next = head;
  return node;
}

Pilhas (Stacks) e Filas (Queues)

Pilhas seguem o princípio LIFO (Last In, First Out): o último elemento inserido é o primeiro removido. Úteis para desfazer operações, navegação de histórico e avaliação de expressões. Filas seguem FIFO (First In, First Out): o primeiro a entrar é o primeiro a sair. Essenciais para processamento de tarefas, buffers e algoritmos de busca em largura (BFS).

EstruturaInserçãoRemoçãoAcessoBusca
ArrayO(n) no meioO(n) no meioO(1)O(n)
Linked ListO(1) se pont. conhecidoO(1) se pont. conhecidoO(n)O(n)
StackO(1) pushO(1) popO(n)O(n)
QueueO(1) enqueueO(1) dequeueO(n)O(n)
Hash TableO(1) médioO(1) médio—O(1) médio
Árvore Binária BalanceadaO(log n)O(log n)—O(log n)

Hash Tables: busca em O(1)

Hash tables (tabelas de espalhamento) mapeiam chaves para valores via função hash. Em JavaScript, objetos e Maps são implementações de hash table. A função hash converte a chave em um índice de array; colisões são tratadas por encadeamento ou endereçamento aberto. Com boa função hash e fator de carga controlado, inserção, remoção e busca são O(1) no caso médio.

typescript
// Contagem de frequência com Map
function frequency(nums: number[]): Map<number, number> {
  const map = new Map<number, number>();
  for (const n of nums) {
    map.set(n, (map.get(n) || 0) + 1);
  }
  return map;
}

Árvores: hierarquia e busca eficiente

Árvores organizam dados hierarquicamente. A árvore binária de busca (BST) mantém a propriedade: valores menores à esquerda, maiores à direita. Em árvores balanceadas (AVL, Red-Black), operações são garantidamente O(log n). Árvores são usadas em índices de banco de dados, parsers de linguagens, DOM do browser e sistemas de arquivos.

typescript
// Travessia em ordem (in-order) de BST — valores em ordem crescente
function inOrder<T>(node: TreeNode<T> | null, result: T[] = []): T[] {
  if (node) {
    inOrder(node.left, result);
    result.push(node.value);
    inOrder(node.right, result);
  }
  return result;
}

Heaps e filas de prioridade

Heaps são árvores binárias completas onde cada pai mantém relação de ordem com os filhos (min-heap ou max-heap). A raiz contém sempre o elemento de maior prioridade. Inserção e remoção do topo são O(log n). Heaps são a base de filas de prioridade, usadas em algoritmos como Dijkstra, A* e scheduling de processos.

Grafos: a generalização

Grafos modelam relações entre entidades. Representados por listas de adjacência ou matrizes, grafos permitem algoritmos de caminho mínimo (Dijkstra, Bellman-Ford), busca (BFS, DFS) e detecção de ciclos. Redes sociais, rotas de entrega e análise de dependências de pacotes são grafos na prática.

Como escolher a estrutura certa

  • Use arrays quando o tamanho é conhecido e acesso aleatório é frequente.
  • Use listas encadeadas quando inserções/remoções frequentes ocorrem nas extremidades.
  • Use hash tables para busca rápida por chave única (caches, índices, contadores).
  • Use árvores quando os dados possuem ordenação natural e busca range é necessária.
  • Use heaps para sempre acessar o elemento de maior ou menor prioridade.
  • Use grafos quando as relações entre entidades são mais importantes que os dados isolados.

Complexidade das operações lado a lado

A tabela resume o custo típico de cada operação. O(1) significa tempo constante, independentemente do tamanho; O(n) cresce junto com a quantidade de elementos; O(log n) cresce devagar — dobrar os dados acrescenta apenas um passo.

EstruturaAcesso por índiceBuscaInserçãoRemoção
Array dinâmicoO(1)O(n)O(1) amortizado no fim; O(n) no meioO(n)
Lista encadeadaO(n)O(n)O(1) com referência ao nóO(1) com referência ao nó
Tabela hash—O(1) em média; O(n) no pior casoO(1) em médiaO(1) em média
Árvore de busca balanceada—O(log n)O(log n)O(log n)
Heap binário—O(n); topo em O(1)O(log n)O(log n) para remover o topo

Notação assintótica descreve crescimento, não velocidade absoluta. Para poucos elementos, um array percorrido do início ao fim pode ser mais rápido que uma tabela hash, porque aproveita melhor o cache do processador.

Na prática em JavaScript e TypeScript

A linguagem já traz Array, Map e Set; pilha é só um array com push e pop. O cuidado está na fila: array.shift() reorganiza todos os elementos e custa O(n), o que pesa em filas grandes. Um ponteiro para o início resolve:

typescript
class Fila<T> {
  private itens: T[] = [];
  private inicio = 0;

  enfileirar(item: T) {
    this.itens.push(item);
  }

  desenfileirar(): T | undefined {
    if (this.inicio >= this.itens.length) return undefined;
    const item = this.itens[this.inicio++];
    // Compacta de vez em quando para não reter memória
    if (this.inicio > 1024 && this.inicio * 2 > this.itens.length) {
      this.itens = this.itens.slice(this.inicio);
      this.inicio = 0;
    }
    return item;
  }

  get tamanho() {
    return this.itens.length - this.inicio;
  }
}

// Set remove duplicatas em O(n)
const unicos = [...new Set(["a", "b", "a"])]; // ["a", "b"]

// Map aceita qualquer tipo como chave e preserva a ordem de inserção
const visitas = new Map<string, number>();
visitas.set("/home", (visitas.get("/home") ?? 0) + 1);

Prefira Map a objetos literais quando as chaves vêm de dados do usuário: objetos herdam propriedades como "constructor" e "__proto__", o que pode gerar bugs e falhas de segurança. JavaScript não tem heap nativo; para filas de prioridade, implemente um heap binário ou use uma biblioteca testada.

Conclusão

Estruturas de dados não são abstrações acadêmicas — são ferramentas práticas que definem limites de performance de qualquer sistema. Conhecer suas características de tempo e espaço permite tomar decisões informadas em projetos reais e responder com confiança em entrevistas técnicas. Pratique implementando-as do zero: a compreensão profunda vem da construção, não apenas do consumo de bibliotecas.

Perguntas frequentes

+Preciso implementar estruturas de dados do zero em projetos reais?

Geralmente não — linguagens modernas fornecem implementações otimizadas. Mas entender como funcionam internamente ajuda a diagnosticar bugs de performance e escolher corretamente.

+Qual estrutura é mais cobrada em entrevistas?

Hash tables e árvores binárias são as mais frequentes, seguidas de grafos e pilhas. Problemas de "two sum" e travessia de árvore aparecem em praticamente todas as big techs.

+Quando devo usar Map ao invés de objeto em JavaScript?

Use Map quando precisar de chaves de qualquer tipo (não apenas strings), quando a ordem de inserção importa, ou quando o tamanho da coleção será frequentemente modificado.

+O que é melhor: lista encadeada ou array?

Depende do padrão de acesso. Arrays para leitura aleatória frequente; listas encadeadas para inserções e remoções dinâmicas, especialmente em extremidades.

Fontes consultadas

Histórico: publicado em ; atualizado em . Conteúdo educativo, sem patrocínio das ferramentas citadas. Encontrou um erro? Envie uma correção.

Crédito da imagem: Ilustração gerada por IA para o icardb (uso editorial)

Leia também