List of data structures

This is a list of well-known data structures. For a wider list of terms, see list of terms relating to algorithms and 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 erroneously 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:

Structure	Ordered?	Uniqueness?
List	yes	no
Associative array	no	keys (indexes) only
Set	no	yes
Stack	yes	no
Multimap	no	no
Multiset (bag)	no	no
Queue	yes	no

"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
Minimax 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