Share This
table started by
pumpkin for the Computer Science Base
A way of storing data for efficient processing.
Add More Topics
Save this view to a base, or just for yourself.
121 Data Structure topics matching:
Filter this Collection| x name | x image | x Operations | x Space complexity | x article | |
|---|---|---|---|---|---|
| x Operation | x Time complexity | ||||
| x Binary search tree |
In computer science, a binary search tree (BST) is a node based binary tree data structure which has the following properties:
From the above properties it naturally follows that:
Generally, the information represented by each node is a record...
|
||||
| x Tree |
|
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.
Mathematically, it is not a tree, but an arborescence: an acyclic connected graph where each node has zero or more...
|
|||
| x B-tree |
|
O(n) |
In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, insertions, deletions, and sequential access in logarithmic amortized time. The B-tree is a generalization of a binary search tree in that more than...
|
||
| x B+ tree |
|
O(n) |
In computer science, a B+ tree (BplusTree) is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with...
|
||
| x B*-tree | O(n) |
A B*-tree is a tree data structure, a variety of B-tree used in the HFS and Reiser4 file systems, which requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full,...
|
|||
| x B# Tree | O(n) |
A B# tree is similar to a B+ tree with rotations allowed among brothers only (immediate siblings).
Insertion Procedure:
Find the node where the new key is to be inserted. If that node is full we must try to perform a rotation with one of our...
|
|||
| x Linked list |
|
Insertion | O(1) | O(n) |
In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.
Linked lists are among the...
|
| Deletion | O(1) | ||||
| Lookup | O(n) | ||||
| Append | O(1) | ||||
| x Skip list | O(n) |
A skip list is a data structure for storing a sorted list of items, using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary...
|
|||
| x Splay tree |
|
O(n) |
A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time. For many non...
|
||
| x Self-balancing binary search tree |
In computer science, a self-balancing (or height-balanced) binary search tree is any binary search tree data structure that automatically keeps its height (number of levels below the root) small in the face of arbitrary item insertions and deletions...
|
||||
| x Binary search tree | |||||
| x Binary tree |
In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the first node is known as the parent and the child nodes are called left and right. In type theory, a binary tree with nodes of type...
|
||||
| x Red-black tree | Lookup | O(log n) | O(n) |
A red-black tree is a type of self-balancing binary search tree, a data structure used in computing science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer : who called them "symmetric...
|
|
| In-order traversal | O(n) | ||||
| Insertion | O(log n) | ||||
| Deletion | O(log n) | ||||
| x AVL tree |
|
O(n) |
In computer science, an AVL tree is a self-balancing binary search tree, and it is the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to...
|
||
| x Trie | Insertion | O(m) | O(n) |
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 usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node;...
|
|
| Deletion | O(m) | ||||
| In-order traversal | O(n) | ||||
| Lookup | O(m) | ||||
| x 2-3 tree |
|
O(n) |
A 2-3 tree in computer science is a type of data structure, a B-tree where every node with children (internal node) has either two children and one data element (2-nodes) or three children and two data elements (3-nodes). Nodes on the outside of the...
|
||
| x 2-3-4 tree |
|
O(n) |
A 2-3-4 tree (also called a 2-4 tree), in computer science, is a self-balancing data structure that is commonly used to implement dictionaries. 2-3-4 trees are B-trees of order 4; like B-trees in general, they can search, insert and delete in O(log...
|
||
| x Array | O(n) |
In computer science, an array data structure or simply array is a data structure consisting of a collection of elements (values or variables), each identified by one or more integer indices, stored so that the address of each element can be computed...
|
|||
| x Dynamic array |
In computer science, a dynamic array, growable array, resizable array, dynamic table, 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 libraries in many...
|
||||
| x Bit array |
A bit array (also known as a bitmap, a bitset, or a bitstring) is an array data structure which compactly stores individual bits (boolean values). It implements a simple set data structure storing a subset of {1,2,...,n} and is effective at...
|
||||
| x Priority queue |
A priority queue is an abstract data type in computer programming that supports the following three operations:
For an analogy, see the Implementation section below.
One can imagine a priority queue as a modified queue, but when one would get the...
|
||||
| x Leftist tree |
|
A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In...
|
|||
| x Binary heap |
|
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
“Greater than” means according to whatever comparison function is chosen to sort the heap, not necessarily “greater...
|
|||
| x Heap |
|
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). Also the tree data structure must be a complete tree for satisfying the heap property. This...
|
|||
| x Binomial heap |
In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type ...
|
||||
| x D-ary heap |
The d-ary heap or d-heap is a generalization of the binary heap data structure whose non-leaf nodes have d children, instead of 2. Thus, a binary heap is a 2-heap.
According to Jensen et al., d-ary heaps were invented by Johnson in 1975.
Because the...
|
||||
| x Fibonacci heap |
|
In computer science, a Fibonacci heap is a heap data structure consisting of a forest of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first...
|
|||
| x Pairing heap |
Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps.
Pairing...
|
||||
| x Soft heap |
In computer science, the soft heap, designed by Bernard Chazelle in 2000, is a variant on the simple heap data structure. By carefully "corrupting" (increasing) the keys of at most a certain fixed percentage of values in the heap, it is able to...
|
||||
| x 2-3 heap | O(n) |
In computer science, a 2-3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2-3 tree.
Time costs for some common heap operations:
|
|||
| x Ternary heap | |||||
| x 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...
|
|||
| x Beap |
|
Beap, short for bi-parental heap, introduced by Ian Munro and Hendra Suwanda. In this data structure a node usually has two parents (unless it is the first or last on a level) and two children (unless it is on the last level). What separates the...
|
|||
| x Skew heap |
|
A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constraints, so there is no...
|
|||
| x Hash table |
In computer science, a hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g., person names) to associated values (e.g., their telephone numbers). The hash function is used to...
|
||||
| x Bloom filter |
|
The Bloom filter, conceived by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be...
|
|||
| x Hash tree |
|
In cryptography and computer science Hash trees or Merkle trees are a type of data structure which contains a tree of summary information about a larger piece of data – for instance a file – used to verify its contents. Hash trees are an extension...
|
|||
| x Associative array |
An associative array (also associative container, map, mapping, dictionary, finite map, and in query-processing an index or index file) is an abstract data type composed of a collection of unique keys and a collection of values, where each key is...
|
||||
| x Bidirectional map |
In computer science, a bidirectional map is an associative data structure in which both types can be used as key.
|
||||
| x Multimap |
A multimap (sometimes also multihash) 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 map and multimap are particular cases of containers ...
|
||||
| x Graph |
In computer science, a graph is an abstract data structure that is meant to implement the graph concept from mathematics.
A graph data structure consists mainly of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of...
|
||||
| x Propositional directed acyclic graph |
|
A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:
Leaves labeled with () represent the...
|
|||
| x Binary decision diagram |
|
In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a more...
|
|||
| x Binary moment diagram |
A binary moment diagram (BMD) is a generalization of the binary decision diagram (BDD) to linear functions over domains such as booleans (like BDDs), but also to integers or to real numbers.
They can deal with boolean functions with complexity...
|
||||
| x Doubly-connected edge list |
The doubly-connected edge list (DCEL) is a data structure to represent an embedding of a planar graph in the plane and polytopes in 3D. This data structure provide efficient manipulation of the topological information associated with the objects in...
|
||||
| x Zipper |
A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages. The zipper was...
|
||||
| x Pile |
A pile is an abstract data structure for storing data in a loosely ordered way. There are two different usages of the term; one refers to an ordered deque, the other to an improved heap.
The first version combines the properties of the deque and a...
|
||||
| x Disjoint-set |
Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an...
|
||||
| x Difference list |
In computer science, the term difference list may refer to one of two data structures for representing lists. One of these data structures contains two lists, and represents the difference of those two lists. The second data structure is a...
|
||||
| x Stack | Push | O(1) |
In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds...
|
||
| Pop | O(1) | ||||
| x Spaghetti stack |
A spaghetti stack (also called a cactus stack or saguaro stack) in computer science is an N-ary tree data structure in which child nodes have pointers to the parent nodes (but not vice-versa). When a list of nodes is traversed from a leaf node to...
|
||||
| x Range tree | O(n log n) |
In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be efficiently retrieved, and is typically used in two or higher dimensions.
It is similar to a kd-tree except...
|
|||
| x Rope | |||||
| x Priority R-tree | |||||
| x R-tree |
|
R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R...
|
|||
| x Radix tree |
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. In contrast with a regular trie, the edges of a Patricia trie are labelled with sequences of characters...
|
||||
| x Suffix tree |
|
In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string...
|
|||
| x String | |||||
| x Adjacency matrix | O(n^2) |
In mathematics and computer science, an adjacency matrix (or one-hop connectivity matrix) is a means of representing which vertices of a graph are adjacent to which other vertices. Another matrix representation for a graph is the incidence matrix....
|
|||
| x Kd-tree |
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a...
|
||||
