Estruturas de Dados

Uma estrutura de dados organiza o estado para tornar eficiente um conjunto de operações escolhido. Não existe uma estrutura universalmente melhor: a seleção depende das operações, invariantes, requisitos de ordenação, restrições de memória e modelo de concorrência.

Estrutura	Operações importantes	Uso típico
Array dinâmico	Acesso por índice, inserção ao final	Sequências ordenadas e iteração
Lista encadeada	Inserção/remoção local	Algoritmos orientados a nós
Pilha	Empilhar e desempilhar	Parsing, DFS, desfazer operações
Fila	Enfileirar e desenfileirar	Escalonamento, BFS
Tabela hash	Busca por chave	Índices, conjuntos, caches
Árvore de busca	Busca ordenada	Consultas por intervalo e mapas ordenados
Heap	Encontrar/remover o extremo de prioridade	Escalonadores e algoritmos de grafos
Conjunto disjunto	União e conectividade	Kruskal e componentes
Grafo	Relacionamentos	Redes, dependências, rotas

As complexidades das páginas seguintes presumem entradas válidas e implementações convencionais. Limites esperados para hashing dependem de uma função hash e de uma política de redimensionamento adequadas.

Uma tabela hash pode implementar a busca usada em memoização ou em um cache de aplicação, mas a estrutura de dados, por si só, não define tempo de vida, atualidade, remoção nem semântica de concorrência.