Editing List of data structures

{{Short description|none}}
This is a list of well-known [[data structure]]s. For a wider list of terms, see [[list of terms relating to algorithms and data structures]]. For a comparison of [[running time]]s for a subset of this list see [[comparison of data structures]].
 
== Data types ==

=== Primitive types ===
{{main|Primitive type}}
*[[Boolean data type|Boolean]], [[Truth value|true]] or [[false (logic)|false]].
*[[Character (computing)|Character]]
*[[Floating-point arithmetic|Floating-point]] representation of a finite subset of the [[rationals]].
** Including [[single-precision floating-point format|single-precision]] and [[double-precision floating-point format|double-precision]] [[IEEE 754]] floats, among [[:Category:Floating point types|others]]
*[[Fixed-point arithmetic|Fixed-point]] representation of the rationals
*[[Integer (computer science)|Integer]], a direct representation of either the [[Integer|integers]] or the [[non-negative integers]]
*[[Reference (computer science)|Reference]], sometimes erroneously referred to as a [[Pointer (computer programming)|pointer]] or handle, is a value that refers to another value, possibly including itself
*[[Symbol (programming)|Symbol]], a unique identifier
*[[Enumerated type]], a [[set (mathematics)|set]] of symbols
*[[Complex data type|Complex]], representation of [[complex numbers]]

=== Composite types or non-primitive type ===
{{main|Composite type}}
*[[Array (data type)|Array]], a sequence of elements of the same type stored contiguously in memory
*[[Record (computer science)|Record]] (also called a structure or [[struct (C programming language)|struct]]), a collection of fields
*[[Product type]] (also called a tuple), a record in which the fields are not named
*[[String (computing)|String]], a sequence of characters representing text
*[[Union type|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 ===
{{main|Abstract data type}}
*[[Container (data structure)|Container]]
*[[List (abstract data type)|List]]
*[[Tuple]]
*[[Associative array|Associative array, Map]]
*[[Multimap]]
*[[Set (abstract data type)|Set]]
*[[Multiset (abstract data type)|Multiset (bag)]]
*[[Stack (abstract data type)|Stack]]
*[[Queue (abstract data type)|Queue]] (example [[Priority queue]])
*[[Double-ended queue]]
*[[Graph (data structure)|Graph]] (example [[Tree (data structure)|Tree]], [[Heap (data structure)|Heap]])

Some properties of abstract data types:
{| class="wikitable"
!Structure
!Ordered?
!Uniqueness?
|-
| [[List (abstract data type)|List]]
| yes
| no
|-
| [[Associative array]]
| no
| keys (indexes) only
|-
| [[Set (abstract data type)|Set]]
| no
| yes
|-
| [[Stack (abstract data type)|Stack]]
| yes
| no
|-
| [[Multimap]]
| no
| no
|-
| [[Multiset (abstract data type)|Multiset (bag)]]
| no
| no
|-
| [[Queue (abstract data type)|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 algorithm|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 data structure|Array]]
*[[Associative array]]
*[[Bit array]]
*[[Bit field]]
*[[Bitboard]]
*[[Bitmap]]
*[[Circular buffer]]
*[[Control table]]
*[[System image|Image]]
*[[Dope vector]]
*[[Dynamic array]]
*[[Gap buffer]]
*[[Hashed array tree]]
*[[Lookup table]]
*[[Matrix (computer science)|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 (data structure)|Zipper]]
*[[Doubly connected edge list]] also known as half-edge
*[[Difference list]]
*[[Free list]]

== Trees ==
{{Main|Tree (data structure)}}
Trees are a subset of [[directed acyclic graph]]s.

=== 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 (data structure)|Pagoda]]
*[[Randomized binary search tree]]
*[[Red–black tree]]
*[[Rope (computer science)|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 Moving Object Index|Bx-tree]]

=== Heaps ===
*[[Heap (data structure)|Heap]]
*[[Min-max heap]]
*[[Binary heap]]
*[[B-heap]]
*[[Weak heap]]
*[[Binomial heap]]
*[[Fibonacci heap]]
*[[AF-heap]]
*[[Smoothsort|Leonardo heap]]
*[[2–3 heap]]
*[[Soft heap]]
*[[Pairing heap]]
*[[Leftist tree|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|Disjoint-set data structure (Union-find data structure)]]
*[[Fusion tree]]
*[[Enfilade (Xanadu)|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 (computational geometry)|Bin]]
*[[K-d tree]]
*[[Implicit k-d tree]]
*[[Min/max kd-tree|Min/max k-d tree]]
*[[Relaxed k-d tree]]
*[[Adaptive k-d tree]]
*[[Quadtree]]
*[[Octree]]
*[[Linear octree]]
*[[Z-order (curve)|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]]

== {{Anchor|Hashes}}Hash-based structures ==
* [[Approximate Membership Query Filter]]
**[[Bloom filter]]
**[[Cuckoo filter]]
**[[Quotient filter]]
*[[Count–min sketch]]
*[[Distributed hash table]]
*[[Double hashing]]
*[[Dynamic perfect hashing|Dynamic perfect hash table]]
*[[Hash array mapped trie]]
*[[Hash list]]
*[[Hash table]]
*[[Hash tree (disambiguation)|Hash tree]]
*[[Hash trie]]
*[[Koorde]]
*[[Prefix hash tree]]
*[[Rolling hash]]
*[[MinHash]]
*[[Ctrie]]

== Graphs ==
Many [[Graph (discrete mathematics)|graph]]-based data structures are used in computer science and related fields:

*[[Graph (data structure)|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==
*[http://tommyds.sourceforge.net/doc/benchmark.html Tommy Benchmarks] Comparison of several data structures.

{{Data structures}}

[[Category:Data structures|*]]
[[Category:Computing-related lists|Data Structures]]