This is a list of well-known data structures. For a comparison of running times for a subset of this list see comparison of data structures.
Data types
Primitive types
Boolean, true or false. Character Floating-point representation of a finite subset of the rationals. Including single-precision and double-precision IEEE 754 floats, among others Fixed-point representation of the rationals Integer, a direct representation of either the integers or the non-negative integers Reference, sometimes referred to as a pointer or handle, is a value that refers to another value, possibly including itself Symbol, a unique identifier Enumerated type, a set of symbols Complex, representation of complex numbers
Composite types or non-primitive type
Array, a sequence of elements of the same type stored contiguously in memory Record (also called a structure or struct), a collection of fields Product type (also called a tuple), a record in which the fields are not named String, a sequence of characters representing text Union, a datum which may be one of a set of types Tagged union (also called a variant, discriminated union or sum type), a union with a tag specifying which type the data is
Abstract data types
Container List Tuple Associative array, Map Multimap Set Multiset (bag) Stack Queue (example Priority queue) Double-ended queue Graph (example Tree, Heap) Some properties of abstract data types:
"Ordered" means that the elements of the data type have some kind of explicit order to them, where an element can be considered "before" or "after" another element. This order is usually determined by the order in which the elements are added to the structure, but the elements can be rearranged in some contexts, such as sorting a list. For a structure that isn't ordered, on the other hand, no assumptions can be made about the ordering of the elements (although a physical implementation of these data types will often apply some kind of arbitrary ordering). "Uniqueness" means that duplicate elements are not allowed. Depending on the implementation of the data type, attempting to add a duplicate element may either be ignored, overwrite the existing element, or raise an error. The detection for duplicates is based on some inbuilt (or alternatively, user-defined) rule for comparing elements.
Linear data structures A data structure is said to be linear if its elements form a sequence.
Arrays Array Associative array Bit array Bit field Bitboard Bitmap Circular buffer Control table Image Dope vector Dynamic array Gap buffer Hashed array tree Lookup table Matrix Parallel array Sorted array Sparse matrix Iliffe vector Variable-length array
Lists Doubly linked list Array list Linked list also known as a Singly linked list Association list Self-organizing list Skip list Unrolled linked list VList Conc-tree list Xor linked list Zipper Doubly connected edge list also known as half-edge Difference list Free list
Trees
Trees are a subset of directed acyclic graphs.
Binary trees AA tree AVL tree Binary search tree Binary tree Cartesian tree Conc-tree list Left-child right-sibling binary 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 WAVL tree Weight-balanced tree Zip tree
B-trees B-tree B+ tree B*-tree Dancing tree 2–3 tree 2–3–4 tree Queap Fusion tree Bx-tree
Heaps Heap Min-max heap Binary heap B-heap Weak heap Binomial heap Fibonacci heap AF-heap Leonardo heap 2–3 heap Soft heap Pairing heap Leftist heap Treap Beap Skew heap Ternary heap D-ary heap Brodal queue
Bit-slice trees In these data structures each tree node compares a bit slice of key values.
Radix tree Suffix tree Suffix array Compressed suffix array FM-index Generalised suffix tree B-tree Judy array Trie X-fast trie Y-fast trie Merkle tree
Multi-way trees Ternary search tree Ternary tree K-ary tree And–or tree (a,b)-tree Link/cut tree SPQR-tree Spaghetti stack Disjoint-set data structure (Union-find 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 K-d tree Implicit k-d tree Min/max k-d tree Relaxed k-d 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 Bounding volume hierarchy BSP tree Rapidly exploring random tree
Application-specific trees Abstract syntax tree Parse tree Decision tree Alternating decision tree Game tree Expectiminimax tree Finger tree Expression tree Log-structured merge-tree PQ tree
Hash-based structures Approximate Membership Query Filter Bloom filter Cuckoo filter Quotient 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 Ctrie
Graphs Many graph-based data structures are used in computer science and related fields:
Graph Adjacency list Adjacency matrix Graph-structured stack Scene graph Decision tree 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 Piece table E-graph
See also List of algorithms Purely functional data structure Blockchain, a hash-based chained data structure that can persist state history over time
External links Tommy Benchmarks Comparison of several data structures.
