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.
Contents |
Data types
Primitive types
Composite types
- Record (also called tuple or struct)
- Union
- Tagged union (also called a variant, variant record, discriminated union, or disjoint union)
Abstract data types
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
- Bit field
- Bit array
- Bitboard
- Bitmaps
- Images
- Dynamic array
- Circular buffer
- Control table
- Gap Buffer
- Hashed array tree
- Heightfields
- Lookup table
- Matrix
- Parallel array
- Sparse array
- Sparse matrix
Lists
- Linked list
- Doubly linked list
- Xor linked list
- Unrolled linked list
- Zipper
- VList
- Skip list
- Jump list
- Self-organizing list
Trees
Binary trees
- Binary tree
- Binary search tree
- Self-balancing binary search tree
- Randomized binary search tree
- Weight-balanced tree
- Threaded binary tree
- AVL tree
- Red-black tree
- AA tree
- Scapegoat tree
- Splay tree
- T-tree
- Rope
- Top Trees
- Tango Trees
- Cartesian tree
- Treap
B-trees
Heaps
- Heap
- Binary heap
- Binomial heap
- Fibonacci heap
- 2-3 heap
- Soft heap
- Pairing heap
- Leftist heap
- Treap
- Beap
- Skew heap
- Ternary heap
- D-ary heap
- Van Emde Boas tree
Tries
In these data structures each tree node compares a bit slice of key values.
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
Space-partitioning trees
This is 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 octrees
- 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
Application-specific trees
- Syntax tree
- Abstract syntax tree
- Parse tree
- Decision tree
- Alternating decision tree
- Minimax tree
- Expectiminimax tree
- Finger tree
Hashes
- Hash table
- Bloom filter
- Hash list
- Hash tree
- Prefix hash tree
- Hash trie
- Hash array mapped trie
- Distributed hash table
- Koorde
Graphs
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
