List of data structures

This is a list of data structures. For a wider list of terms, see list of terms relating to algorithms and data structures. For a comparison of running time of subset of this list see comparison of data structures.

Data types

Primitive types

• Boolean (for boolean values True/False)
• Char (for character values)
• Float (for storing real number values)
• Double (a larger size of type float)
• int (for integral or fixed-precision values)
• String (for string of chars)
• Enumerated type

Composite types

• Array
• Record (also called tuple or struct)
• Union
• Tagged union (also called a variant, variant record, discriminated union, or disjoint union)
• Plain old data structure

Abstract data types

• Container
• Deque
• Map/Associative array/Dictionary
• Multimap
• Multiset
• Priority queue
• Queue
• Set
• Stack
• String
• Tree
• Graph
• Hash

Some properties of abstract data types:

Structure	Stable	Unique	Cells per Node
Bag (multiset)	no	no	1
Set	no	yes	1
List	yes	no	1
Map	no	yes	2

"Stable" means that input order is retained. Other structures such as "linked list" and "stack" cannot easily be defined this way because there are specific operations associated with them.

Linear data structures

Arrays

• Array
• Bidirectional map
• Bit array
• Bit field
• Bitboard
• Bitmap
• Circular buffer
• Control table
• Image
• Dynamic array
• Gap buffer
• Hashed array tree
• Heightmap
• Lookup table
• Matrix
• Parallel array
• Sorted array
• Sparse array
• Sparse matrix
• Iliffe vector
• Variable-length array

Lists

• Doubly linked list
• Linked list
• Self-organizing list
• Skip list
• Unrolled linked list
• VList
• Xor linked list
• Zipper
• Doubly connected edge list

Trees

Binary trees

• AA tree
• AVL tree
• Binary search tree
• Binary tree
• Cartesian tree
• Pagoda
• Randomized binary search tree
• Red-black tree
• Rope
• Scapegoat tree
• Self-balancing binary search tree
• Splay tree
• T-tree
• Tango tree
• Threaded binary tree
• Top tree
• Treap
• Weight-balanced tree

B-trees

• B-tree
• B+ tree
• B*-tree
• B sharp tree
• Dancing tree
• 2-3 tree
• 2-3-4 tree
• Queap
• Fusion tree
• Bx-tree

Heaps

• Heap
• Binary heap
• Binomial heap
• Fibonacci heap
  • AF-heap
• 2-3 heap
• Soft heap
• Pairing heap
• Leftist heap
• Treap
• Beap
• Skew heap
• Ternary heap
• D-ary heap

Tries

In these data structures each tree node compares a bit slice of key values.

• Trie
• Radix tree
• Suffix tree
• Suffix array
• Compressed suffix array
• FM-index
• Generalised suffix tree
• B-trie
• Judy array
• X-fast trie
• Y-fast trie
• Ctrie

Multiway trees

• Ternary search tree
• And–or tree
• (a,b)-tree
• Link/cut tree
• SPQR-tree
• Spaghetti stack
• Disjoint-set data structure
• Fusion tree
• Enfilade
• Exponential tree
• Fenwick tree
• Van Emde Boas tree

Space-partitioning trees

These are data structures used for space partitioning or binary space partitioning.

• Segment tree
• Interval tree
• Range tree
• Bin
• Kd-tree
• Implicit kd-tree
• Min/max kd-tree
• Adaptive k-d tree
• Kdb tree
• Quadtree
• Octree
• Linear octree
• Z-order
• UB-tree
• R-tree
• R+ tree
• R* tree
• Hilbert R-tree
• X-tree
• Metric tree
• Cover tree
• M-tree
• VP-tree
• BK-tree
• Bounding interval hierarchy
• BSP tree
• Rapidly-exploring random tree

Application-specific trees

• Syntax tree
• Abstract syntax tree
• Parse tree
• Decision tree
• Alternating decision tree
• Minimax tree
• Expectiminimax tree
• Finger tree

Hashes

• Bloom filter
• Distributed hash table
• Hash array mapped trie
• Hash list
• Hash table
• Hash tree
• Hash trie
• Koorde
• Prefix hash tree

Graphs

• Graph
• Adjacency list
• Adjacency matrix
• Graph-structured stack
• Scene graph
• Binary decision diagram
• Zero suppressed decision diagram
• And-inverter graph
• Directed graph
• Directed acyclic graph
• Propositional directed acyclic graph
• Multigraph
• Hypergraph

Other

• Lightmap
• Winged edge
• Quad-edge
• Routing table
• Symbol table