What is "data-structure"

Data structures are ubiquitous in software. Hash tables, balanced trees and dynamic matrices are essential building blocks for large and complicated systems and almost all programmers have found them at some point. More complex structures such as binary Heaps can accelerate more complicated systems, while simpler concepts such as stacks and queues make coding of more elegant and concise algorithms possible.

Of course, that’s just the tip of the iceberg when it comes to data structures. Theorists have progressively developed better and better data structures over the past few years, many of which are used extensively in modern software, and many are only theoretically useful.

Data structures are closely related to algorithms. Often, a good choice of data structure can lead to a marked improvement in the execution of an algorithm. For example, Dijkstra’s algorithm with a simplistic implementation of a priority queue runs in quadratic time, but with a fast Fibonacci heap can be shown to run in O(m + n lg n).

Below is a (not very comprehensive) list of some of the most popular data structures and their variants:

  • 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