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
editPrimitive types
edit- 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
edit- 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
edit- 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:
This article needs attention from an expert in Computer science. The specific problem is: further features needed. (June 2022) |
| 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
editA data structure is said to be linear if its elements form a sequence.
Arrays
edit- 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
edit- 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
editTrees are a subset of directed acyclic graphs.
Binary trees
edit- 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
editHeaps
edit- 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
editIn 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
edit- 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
editThese 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
editHash-based structures
editGraphs
editMany graph-based data structures are used in computer science and related fields:
Other
editSee also
edit- List of algorithms
- Purely functional data structure
- Blockchain, a hash-based chained data structure that can persist state history over time
External links
edit- Tommy Benchmarks Comparison of several data structures.