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 Single-precision floating-point format (sometimes called FP32 or float32) is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point. A floati ...

and

double-precision Double-precision floating-point format (sometimes called FP64 or float64) is a floating-point number format, usually occupying 64 bits in computer memory; it represents a wide range of numeric values by using a floating radix point. Double prec ...

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 An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...

, a sequence of elements of the same type stored contiguously in memory * Record (also called a structure or

struct In computer science, a record (also called a structure, struct, or compound data type) is a composite data structure a collection of fields, possibly of different data types, typically fixed in number and sequence. For example, a date could b ...

), 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 In computer science, a double-ended queue (abbreviated to deque, ) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-t ...

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

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 A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or d ...

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 Control tables are tables that control the control flow or play a major part in program control. There are no rigid rules about the structure or content of a control table—its qualifying attribute is its ability to direct control flow in some w ...

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 In computer programming, a dope vector is a data structure used to hold information about a data object, especially its memory layout. Purpose Dope vectors are most commonly used to describe arrays, which commonly store multiple instances of a part ...

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 In computer science, a hashed array tree (HAT) is a dynamic array data-structure published by Edward Sitarski in 1996, maintaining an array of separate memory fragments (or "leaves") to store the data elements, unlike simple dynamic arrays which mai ...

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 In computing, a group of parallel arrays (also known as structure of arrays or SoA) is a form of implicit data structure that uses multiple arrays to represent a singular array of records. It keeps a separate, homogeneous data array for each fi ...

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 In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the se ...

* 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 A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time. The aim of a self-organizing list is to improve efficiency of linear search by moving more frequently accessed item ...

Skip list In computer science, a skip list (or skiplist) is a Randomized algorithm, probabilistic data structure that allows O(\log n) Average-case complexity, average complexity for search as well as O(\log n) average complexity for insertion within an or ...

* 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 A free list (or freelist) is a data structure used in a scheme for dynamic memory allocation. It operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the ...

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 In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by m ...

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 A pagoda is a tiered tower with multiple eaves common to Thailand, Cambodia, Nepal, India, China, Japan, Korea, Myanmar, Vietnam, and other parts of Asia. Most pagodas were built to have a religious function, most often Buddhist, but some ...

* Randomized binary search tree *

Red–black tree In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, wh ...

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 A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal ...

* 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 In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of i ...

* WAVL tree * Weight-balanced tree *

Zip tree The zip tree was introduced as a variant of random binary search tree by Robert Tarjan, Caleb Levy, and Stephen Timmel. Zip trees are similar to max treaps except ranks are generated through a geometric distribution and maintain their max-heap pr ...

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 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 for ...

Dancing tree In computer science, a dancing tree is a tree data structure similar to B+ trees. It was invented by Hans Reiser, for use by the Reiser4 file system. As opposed to self-balancing binary search tree In computer science, a self-balancing binary ...

* 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 In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binar ...

* 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 A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are he ...

* Leftist heap *

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 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., - ...

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 In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particu ...

Suffix array In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field of bibliometrics. Suffix arrays were introduced by as ...

* Compressed suffix array *

FM-index In computer science, an FM-index is a compressed full-text substring index based on the Burrows–Wheeler transform, with some similarities to the suffix array. It was created by Paolo Ferragina and Giovanni Manzini,Paolo Ferragina and Giovanni Man ...

* 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 An and–or tree is a graphical representation of the reduction of problems (or goals) to conjunctions and disjunction In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a ...

* (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 In geometry, space partitioning is the process of dividing an entire space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regio ...

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 In computer science, a range tree is an ordered tree data structure, ordered tree data structure to hold a list of points. It allows all points within a given range to be Range query (computer science), reported efficiently, and is typically used ...

* Bin *

K-d tree In computer science, a ''k''-d tree (short for ''k-dimensional tree'') is a space-partitioning data structure for organizing points in a ''k''-dimensional space. K-dimensional is that which concerns exactly k orthogonal axes or a space of any ...

Implicit k-d tree An implicit ''k''-d tree is a ''k''-d tree defined implicitly above a rectilinear grid. Its split planes' positions and orientations are not given explicitly but implicitly by some recursive splitting-function defined on the hyperrectangles bel ...

* Min/max k-d tree * Relaxed k-d tree * Adaptive k-d tree *

Quadtree A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four ...

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 A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficient. Examples include the M-tree, vp-tr ...

* 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 A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, which form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within lar ...

* 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 An alternating decision tree (ADTree) is a machine learning method for classification. It generalizes decision trees and has connections to boosting. An ADTree consists of an alternation of decision nodes, which specify a predicate condition, and ...

* Minimax tree * Expectiminimax tree *

Finger tree In computer science, a finger tree is a purely functional data structure that can be used to efficiently implement other functional data structures. A finger tree gives amortized constant time access to the "fingers" (leaves) of the tree, which ...

Expression tree A binary expression tree is a specific kind of a binary tree used to represent Expression (mathematics), expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean algebra, boolean. These tre ...

* Log-structured merge-tree * PQ tree

Hash-based structures

* Approximate Membership Query Filter **

Bloom filter In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives ar ...

** 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 Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is ...

* Dynamic perfect hash table *

Hash array mapped trie A hash array mapped trie (HAMT, ) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie. It is a refined version of the more general notion of a hash tree. Operation A HAMT is ...

* 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 Hash, hashes, hash mark, or hashing may refer to: Substances * Hash (food), a coarse mixture of ingredients, often based on minced meat * Hash (stew), a pork and onion-based gravy found in South Carolina * Hash, a nickname for hashish, a cann ...

Koorde In peer-to-peer networks, Koorde is a distributed hash table (DHT) system based on the Chord (DHT), Chord DHT and the De Bruijn graph (De Bruijn sequence). Inheriting the simplicity of Chord, Koorde meets hops per Node (networking), node (where ...

* Prefix hash tree *

Rolling hash Rolling is a type of motion that combines rotation (commonly, of an axially symmetric object) and translation of that object with respect to a surface (either one or the other moves), such that, if ideal conditions exist, the two are in contact ...

MinHash In computer science and data mining, MinHash (or the min-wise independent permutations locality sensitive hashing scheme) is a technique for quickly estimating how similar two sets are. The scheme was published by Andrei Broder in a 1997 confer ...

Ctrie A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is ...

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 A scene graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games, which arranges the logical and often spatial representation of a graphical scene. It is a collection of nodes in a g ...

** 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 In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

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 In computer graphics, the winged edge data structure is a way to represent polygon meshes in computer memory. It is a type of boundary representation and describes both the geometry and topology of a model. Three types of records are used: verte ...

* 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 In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier, symbol, constant, procedure and function in a program's source code is associated with information ...

* Piece table *

E-graph In computer science, an e-graph is a data structure that stores an equivalence relation over terms of some language. Definition and operations Let \Sigma be a set of uninterpreted functions, where \Sigma_n is the subset of \Sigma consisting of ...

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 ...