Skip to main content

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