Uma estrutura de dados é uma maneira de organizar os dados de uma forma que permite que as propriedades particulares dos dados a serem consultados e/ou atualizado de forma eficiente.
As estruturas de dados são onipresentes em software. As tabelas de hash, árvores balanceadas e matrizes dinâmicas são blocos de construção essenciais para sistemas grandes e complicados e quase todos os programadores encontraram-los em algum momento. Estruturas mais complexas, como heaps binários podem acelerar sistemas mais complicados, enquanto conceitos mais simples, como pilhas e filas tornam possível a codificação de algoritmos mais elegante e concisa.
Claro, isso é apenas a ponta do iceberg quando se trata de estruturas de dados. Os teóricos têm desenvolvido progressivamente melhores estruturas de dados e melhor ao longo dos últimos anos, muitos dos quais são usados extensivamente em software moderno, e muitos só são úteis do ponto de vista teórico.
As estruturas de dados estão intimamente relacionados com os algoritmos. Muitas vezes, uma boa escolha de estrutura de dados pode levar a uma acentuada melhoria na execução de um algoritmo. Por exemplo, o algoritmo de Dijkstra com uma implementação simplista de uma fila de prioridade é executado em tempo quadrático, mas com um heap Fibonacci rápido pode ser mostrado para ser executado em O(m + n lg n)
.
Abaixo está uma lista (não muito abrangente) de algumas das estruturas de dados mais populares e suas variantes:
- Dynamic arrays
- Dynamic table
- Tiered vector
- Hashed array tree
- Extendible array
- Linked lists
- Singly-linked lists
- Doubly-linked lists
- XOR-linked lists
- Hash tables
- Chained hash tables
- Linear probing hash tables
- Quadratic probing hash tables
- Double hash tables
- Cuckoo hash tables
- Perfect hash tables
- Dynamic perfect hash tables
- Binary trees
- Red/black trees
- AVL trees
- AA trees
- Splay trees
- Scapegoat trees
- Treap
- Priority queues
- Binary heap
- Binomial heap
- Fibonacci heap
- van Emde Boas tree
- Skew binomial heap
- Brodal queue
- Radix trees
- Trie
- Patricia tree
- Ternary search tree
- Multiway trees
- B tree
- B+ tree
- B* tree
- Geometric trees
- Quadtree
- Octree
- kd-Tree
- BSP-tree
- R-tree
- Geometric structures
- Winged-edge
- Quadedge
- Network connectivity structures
- Disjoint-set forest
- Link/cut tree
- Top tree
- Graphs
- DAG
- Directed graph
- Undirected graph
- Hypergraph