This is a list of well-known

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

s. 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 True most commonly refers to truth, the state of being in congruence with fact or reality. True may also refer to: Places * True, West Virginia, an unincorporated community in the United States * True, Wisconsin, a town in the United States * ...

or false. * Character *

Floating-point In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a Sign (mathematics), signed sequence of a fixed number of digits in some Radix, base) multiplied by an integer power of that ba ...

representation of a finite subset of the rationals. ** Including single-precision and double-precision

IEEE 754 The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic originally established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard #Design rationale, add ...

floats, among others * Fixed-point representation of the rationals *

Integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

, a direct representation of either the

integers An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

or the non-negative integers *

Reference A reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a ''nam ...

, sometimes erroneously referred to as a pointer or handle, is a value that refers to another value, possibly including itself *

Symbol A symbol is a mark, Sign (semiotics), sign, or word that indicates, signifies, or is understood as representing an idea, physical object, object, or wikt:relationship, relationship. Symbols allow people to go beyond what is known or seen by cr ...

, a unique identifier *

Enumerated type In computer programming, an enumerated type (also called enumeration, enum, or factor in the R (programming language), R programming language, a status variable in the JOVIAL programming language, and a categorical variable in statistics) is a data ...

, a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

of symbols *

Complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...

, representation of

complex numbers In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...

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 In programming languages and type theory, a product of ''types'' is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the produ ...

(also called a tuple), a record in which the fields are not named *

String String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...

, a sequence of characters representing text * Union, a datum which may be one of a set of types *

Tagged union In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type, or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. ...

(also called a ''variant'', ''discriminated union'' or ''sum type''), a union with a tag specifying which type the data is

Abstract data types

Container A container is any receptacle or enclosure for holding a product used in storage, packaging, and transportation, including shipping. Things kept inside of a container are protected on several sides by being inside of its structure. The term ...

List A list is a Set (mathematics), set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of t ...

Tuple In mathematics, a tuple is a finite sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...

* Associative array, Map *

Multimap In computer science, a multimap (sometimes also multihash, multidict or multidictionary) is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key. Both ...

Set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

* Multiset (bag) *

Stack Stack may refer to: Places * Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group * Blue Stack Mountains, in Co. Donegal, Ireland People * Stack (surname) (including a list of people ...

* Queue (example

Priority queue In computer science, a priority queue is an abstract data type similar to a regular queue (abstract data type), queue or stack (abstract data type), stack abstract data type. In a priority queue, each element has an associated ''priority'', which ...

) * Double-ended queue *

Graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

(example

Tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

, 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 Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. # ordering: arranging items in a sequence ordered by some criterion; # categorizing: grouping items with similar p ...

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 In computer science, an associative array, key-value store, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In math ...

Bit array A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level par ...

Bit field A bit field is a data structure that maps to one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to repre ...

* Bitboard *

Bitmap In computing, a bitmap (also called raster) graphic is an image formed from rows of different colored pixels. A GIF is an example of a graphics image file that uses a bitmap. As a noun, the term "bitmap" is very often used to refer to a partic ...

Circular buffer In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. The ...

* Control table *

Image An image or picture is a visual representation. An image can be Two-dimensional space, two-dimensional, such as a drawing, painting, or photograph, or Three-dimensional space, three-dimensional, such as a carving or sculpture. Images may be di ...

* Dope vector *

Dynamic array In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard l ...

* Gap buffer * Hashed array tree *

Lookup table In computer science, a lookup table (LUT) is an array data structure, array that replaces runtime (program lifecycle phase), runtime computation of a mathematical function (mathematics), function with a simpler array indexing operation, in a proc ...

Matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...

* Parallel array *

Sorted array A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static l ...

Sparse matrix In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse ...

Iliffe vector In computer programming, an Iliffe vector, also known as a display, is a data structure used to implement multi-dimensional array data structure, arrays. Data structure An Iliffe vector for an ''n''-dimensional array (where ''n'' ≥ 2) ...

Variable-length array In computer programming, a variable-length array (VLA), also called variable-sized or runtime-sized, is an array data structure whose length is determined at runtime, instead of at compile time. In the language C, the VLA is said to have a variab ...

Lists

* Doubly linked list * Array list *

Linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...

also known as a Singly linked list *

Association list In computer programming and particularly in Lisp, an association list, often referred to as an alist, is a linked list in which each list element (or node) comprises a key and a value. The association list is said to ''associate'' the value wit ...

* Self-organizing list * Skip list * Unrolled linked list *VList * Conc-tree list * Xor linked list *

Zipper A zipper (N. America), zip, zip fastener (UK), formerly known as a clasp locker, is a commonly used device for binding together two edges of textile, fabric or other flexible material. Used in clothing (e.g. jackets and jeans), luggage and oth ...

* Doubly connected edge list also known as half-edge *

Difference list In computer science, the term difference list refers to a data structure representing a list with an efficient O(1) concatenation operation and conversion to a linked list in time proportional to its length. Difference lists can be implemented usi ...

* Free list

Trees

Trees are a subset of

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...

Binary trees

* AA tree * AVL tree *

Binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a Rooted tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...

Binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...

* Cartesian tree * Conc-tree list * Left-child right-sibling binary tree *

Order statistic tree In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operations beyond insertion, lookup and deletion: * Select(''i'') – find the ''i''-th smallest element ...

* Pagoda * Randomized binary search tree * Red–black tree *

Rope A rope is a group of yarns, Plying, plies, fibres, or strands that are plying, twisted or braided together into a larger and stronger form. Ropes have high tensile strength and can be used for dragging and lifting. Rope is thicker and stronger ...

* Scapegoat tree *

Self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

* Splay tree * T-tree * Tango tree *

Threaded binary tree In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order. An entire binary search tree can be easily traversed in order of the main key but given only a pointer to a node, finding the node ...

* Top tree * Treap * WAVL tree * Weight-balanced tree * Zip tree

B-trees

B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing fo ...

B+ tree A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. A B+ tree can be viewed as a B ...

* B*-tree * Dancing tree * 2–3 tree * 2–3–4 tree * Queap *

Fusion tree In computer science, a fusion tree is a type of tree data structure that implements an associative array on -bit integers on a finite universe, where each of the input integers has size less than 2w and is non-negative. When operating on a collect ...

* Bx-tree

Heaps

* Heap * Min-max heap *

Binary heap A binary heap is a heap (data structure), heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964 as a data structure fo ...

B-heap A B-heap is a binary heap implemented to keep subtrees in a single Page (computer memory) , page. This reduces the number of pages accessed by up to a factor of ten for big heaps when using virtual memory, compared with the traditional implementatio ...

* Weak heap *

Binomial heap In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a Heap (data st ...

* Fibonacci heap * AF-heap * Leonardo heap *

2–3 heap In computer science, a 2–3 heap is a data structure that implements a priority queue. It is a variation on the heap (data structure), heap, designed by Tadao Takaoka in 1999. The structure is similar to a Fibonacci heap, and borrows ideas from ...

* Soft heap * Pairing heap * Leftist heap * Treap *

Beap A beap, or bi-parental heap, is a data structure for a set (or map, or multiset or multimap) that enables elements (or mappings) to be located, inserted, or deleted in sublinear time. In a beap, each element is stored in a node with up to two par ...

* Skew heap *

Ternary heap The -ary heap or -heap is a priority queue data structure, a generalization of the binary heap in which the nodes have children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., - ...

* D-ary heap *

Brodal queue In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: O(1) for insertion, find-minimum, meld (merge two queues) and decrease-key and O(\mathrm(n)) for delete-minimum and general deletion. ...

Bit-slice trees

In these data structures each tree node compares a bit slice of key values. *

Radix tree In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent. The resu ...

* Suffix tree * Suffix array * Compressed suffix array * FM-index * Generalised suffix tree *

Judy array In computer science, a Judy array is an early-2000s Hewlett-Packard hand-optimized implementation of a 256-ary radix tree that uses many situational node types to reduce latency from CPU cache-line fills.Alan Silverstein,Judy IV Shop Manual, 2002 ...

Trie In computer science, a trie (, ), also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store t ...

* X-fast trie * Y-fast trie * Merkle tree

Multi-way trees

Ternary search tree In computer science, a ternary search tree is a type of trie (sometimes called a ''prefix tree'') where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Li ...

Ternary tree : In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes, and child nodes may contain reference ...

* K-ary tree * And–or tree * (a,b)-tree * Link/cut tree * SPQR-tree * Spaghetti stack * Disjoint-set data structure (Union-find data structure) *

Enfilade Enfilade and defilade are concepts in military tactics used to describe a military formation's exposure to enemy fire. A formation or position is "in enfilade" if weapon fire can be directed along its longest axis. A unit or position is "in de ...

Exponential tree An exponential tree is a type of search tree In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greate ...

* Fenwick tree * Van Emde Boas tree * Rose tree

Space-partitioning trees

These are data structures used for space partitioning or

binary space partitioning In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representa ...

. *

Segment tree In computer science, the segment tree is a data structure used for storing information about Interval (mathematics), intervals or segments. It allows querying which of the stored segments contain a given point. A similar data structure is the i ...

* 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 An octree is a tree data structure in which each internal node has exactly eight child node, children. Octrees are most often used to partition a three-dimensional space by recursive subdivision, recursively subdividing it into eight Octant (geo ...

* Linear octree * Z-order * UB-tree *

R-tree R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found s ...

R+ tree R-trees are tree data structures used for spatial index, spatial access methods, i.e., for indexing multi-dimensional information such as Geographic coordinate system, geographical coordinates, rectangles or polygons. The R-tree was proposed ...

* R* tree *

Hilbert R-tree Hilbert R-tree, an R-tree variant, is an index for multidimensional objects such as lines, regions, 3-D objects, or high-dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects. T ...

X-tree In computer science tree data structures, an X-tree (for ''eXtended node tree'') is an index tree structure based on the R-tree used for storing data in many dimensions. It appeared in 1996, and differs from R-trees (1984), R+-trees (1987) and ...

* Metric tree * Cover tree * M-tree * VP-tree * BK-tree *

Bounding interval hierarchy A bounding interval hierarchy (BIH) is a partitioning data structure similar to that of bounding volume hierarchy, bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance (or real-time) Ray tracing (gra ...

* Bounding volume hierarchy * BSP tree * Rapidly exploring random tree

Application-specific trees

Abstract syntax tree An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal ...

Parse tree A parse tree or parsing tree (also known as a derivation tree or concrete syntax tree) is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term ''parse tree'' itself is use ...

Decision tree A decision tree is a decision support system, decision support recursive partitioning structure that uses a Tree (graph theory), tree-like Causal model, model of decisions and their possible consequences, including probability, chance event ou ...

* 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 A distributed hash table (DHT) is a Distributed computing, distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node (networking), node can efficiently retrieve the ...

* Double hashing * Dynamic perfect hash table * Hash array mapped trie * Hash list *

Hash table In computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps Unique key, keys to Value (computer science), values. ...

* Hash tree * Hash trie * Koorde * Prefix hash tree * Rolling hash * MinHash * Ctrie

Graphs

Many

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

-based data structures are used in computer science and related fields: *

Adjacency list In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This ...

Adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

* Graph-structured stack * Scene graph *

** Binary decision diagram * Zero-suppressed decision diagram * And-inverter graph * Directed graph *

Directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...

* Propositional directed acyclic graph * Multigraph *

Hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...

Other

Lightmap A lightmap is a data structure used in lightmapping, a form of surface caching in which the brightness of surfaces in a virtual scene is pre-calculated and stored in texture maps for later use. Lightmaps are most commonly applied to static o ...

* Winged edge * Quad-edge *

Routing table In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated wi ...

* Symbol table * Piece table * E-graph

External links

Tommy Benchmarks
Comparison of several data structures. {{Data structures *

Data Structures In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functi ...