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, true or false
- Character
- Floating-point, single-precision real number values
- Double, a wider floating-point size
- Integer, integral or fixed-precision values
- Enumerated type, a small set of uniquely named values
Composite types
(Sometimes also referred to as Plain old data structures.)
- Array
- Record (also called tuple or struct or class)
- Union
- Tagged union (also called a variant, variant record, discriminated union, or disjoint union)
Abstract data types
- Array
- Container
- Map/Associative array/Dictionary
- Multimap
- List
- Set
- Multiset/Bag
- Priority queue
- Queue
- Double-ended queue
- Stack
- String
- Tree
- Graph
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
- Array list
- Linked list
- Self-organizing list
- Skip list
- Unrolled linked list
- VList
- Xor linked list
- Zipper
- Doubly connected edge list
- Difference list
- Free list
Trees
Main article: Tree (data structure)
Binary trees
- AA tree
- AVL tree
- Binary search tree
- Binary tree
- Cartesian tree
- Order statistic 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
- Binary data structure
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
- AList
Heaps
- Heap
- Binary heap
- Weak heap
- Binomial heap
- Fibonacci heap
- Leonardo Heap
- 2-3 heap
- Soft heap
- Pairing heap
- Leftist heap
- Treap
- Beap
- Skew heap
- Ternary heap
- D-ary heap
- Brodal queue
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 tree
- K-ary 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
- Rose 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
- 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
- Abstract syntax tree
- Parse tree
- Decision tree
- Alternating decision tree
- Minimax tree
- Expectiminimax tree
- Finger tree
- Expression tree
- Log-structured merge-tree
Hashes
- Bloom filter
- Count-Min sketch
- Distributed hash table
- Double Hashing
- Dynamic perfect hash table
- Hash array mapped trie
- Hash list
- Hash table
- Hash tree
- Hash trie
- Koorde
- Prefix hash tree
- Rolling hash
- MinHash
- Quotient filter
- Ctrie
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
|
External links
- Tommy Benchmarks Comparison of several data structures.