This is a list of data structures. For a wider list of terms, see list of terms relating to algorithms and data structures. A binary tree, a simple type of branching linked data structure. ... The NIST Dictionary of Algorithms and Data Structures is a reference work maintained by the U.S. National Institute of Standards and Technology. ...

Linear data structures

Look up list in Wiktionary, the free dictionary. ... In computer programming, a group of homogeneous elements of a specific data type is known as an array, one of the simplest data structures. ... 1. ... A digital image is a representation of a two-dimensional image as a finite set of digital values, called picture elements or pixels. ... A heightfield (also known as a Digital Elevation Model, or DEM) is a bitmap whose component pixels are meant to be interpreted as elevations. ... A dynamic array, growable array, resizable array, dynamic table, or array list is a data structure, an array which is automatically expanded to accommodate new objects if filled beyond its current size. ... A parallel array is a simple data structure for representing arrays of records. ... A sparse array in computing is an array where most of the elements have the same value (called the default value -- usually 0) and only a few elements have a non-default value. ... Look up matrix in Wiktionary, the free dictionary. ... In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... An unrolled linked list is a variation on the linked list which stores multiple elements in each node. ... XOR linked lists are a curious use of the bitwise exclusive disjunction (XOR) operation to decrease storage requirements for doubly-linked lists. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... If you are seeking the town in the Netherlands, see Vlist. ... The word line derives from the Latin lingui, meaning flax plant from which linen is produced; at one time, a stretched linen thread was the most reliable way to determine a straight line. ... Look up Stack in Wiktionary, the free dictionary. ... In providing services in computer science, transport, and operations research a queue (pronounced kyew) is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. ... A priority queue is an ADT (abstract data type) supporting the following two operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it The simplest way to implement a priority queue data type is to... In computer science, a deque (short for double-ended queue) is a data structure for which elements can be added to or removed from the front or back. ... An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... A skip list is a probabilistic data structure, based on parallel linked lists, with efficiency comparable to a binary search tree (order O(log n) average time for most operations). ...

Non linear data structures

In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ... Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping groups. ... In computer science, a graph-structured stack is a directed acyclic graph where each directed path is a stack. ... // Introduction A scene-graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games. ... Look up Frame in Wiktionary, the free dictionary. ... The term database originated within the computer industry. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ... A 2-3-4 tree in computer science is a B-tree of order 4. ... In computer science a B+ tree is a type of tree data structure. ... A B*-tree is a tree data structure, a variety of B-tree that is efficient for searching at the cost of a more expensive insertion. ... This article is about an R-tree data structure. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... R* tree is a variant of R tree for indexing spatial information. ... In computer science, a binary tree is a tree data structure in which each node has at most two children. ... A binary search tree of size 9 and depth 3, with root 7 and leaves 1, 4, 7 and 13. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ... An example of a non-AVL tree In computer science, an AVL tree is a self-balancing binary search tree, and the first such data structure to be invented. ... A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. ... In computing, a scapegoat tree is a self-balancing binary search tree which performs insertions and deletions in O(log n) amortized time by rebuilding the tree (or subtrees thereof) whenever it becomes too unbalanced. ... A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. ... In computer science, the interval tree is an ordered tree data structure to hold intervals. ... In computer science, a treap is a binary search tree that orders the nodes by adding a random number priority attribute to a node, as well as a key. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are strings. ... A radix tree, Patricia trie/tree, or crit bit tree is a specialized set data structure based on the trie that is used to store a set of strings. ... A van Emde Boas tree (or van Emde Boas priority queue), also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. ... Suffix tree for the string BANANA padded with $. Suffix links drawn dashed. ... A directed acyclic word graph (DAWG) is a data structure in computer science similar to a trie but much more space efficient. ... In computer science, a heap is a specialized tree-based data structure that satisfies the heap property. ... Example of a complete binary max heap. ... In computer science, a binomial heap is a data structure similar to binary heap but also supporting the operation of merging two heaps quickly. ... In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ... A 2-3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. ... In computer science, the soft heap is a variant on the simple heap data structure designed by Bernard Chazelle in 2000. ... Pairing heaps are a type of heap data structure with relatively simple implementation, excellent practical amortized performance (particularly for applications where heaps must be merged). ... A leftist tree is a priority queue implemented with a variant of a binary tree. ... In computer science, a treap is a binary search tree that orders the nodes by adding a random number priority attribute to a node, as well as a key. ... Beap, short for bi-parental heap, introduced by Ian Munro and Hendra Suwanda. ... A skew heap is a variant of a binary heap. ... A parse tree is a tree that represents the syntactic structure of a string according to some formal grammar. ... In mathematics, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). ... Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. ... A 3-dimensional kd-tree. ... The Quadtree is a tree data structure in which each internal node has up to four children. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

Base data structures

On computer science, a datatype (often simply type) is a name or label for a set of values and some operations which can be performed on that set of values. ... In computer science, the term integer is used to refer to any data type which can represent some subset of the mathematical integers. ... In computer and machine-based telecommunications terminology, a character is a unit of information that roughly corresponds to a grapheme or a grapheme-like unit or symbol, such as in an alphabet or syllabary in the written form of a natural language. ... A struct is the C programming languages notion of a record, a datatype that aggregates a fixed set of labelled objects, possibly of different types, into a single object. ... In computer science, the term integer is used to refer to any data type which can represent some subset of the mathematical integers. ... In computer programming and some branches of mathematics, strings are sequences of various simple objects. ... In computer science, a union is a data structure that stores one of several types of data at a single location. ... In computer science, a tagged union, also called a variant, variant record, discriminated union, or disjoint union, is a data structure used to hold a value that could take on several different, but fixed types. ... A gap buffer is a data structure used to store long arrays compactly, while still allowing efficient insertion and deletion operations, provided that the operations are clustered near the same location. ...

Comparison

An attempt to classify data structures based on feature attributes:

"Ordered" does not mean sorted, only that input order is "retained". Other structures such as "linked list" and "stack" cannot easily be defined this way because there are specific operations associated with them. In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ... In computer science, the set is a collection of certain values without any particular order. ... Look up list in Wiktionary, the free dictionary This article is about the word list as used in computer science. ... For other uses, see Map (disambiguation). ...