algo algorithm algorithms coding compsci computer computerscience cs data data-structure data-structures data.structures data_structure data_structures datastructure datastructures dev development interview list programming science software structure structures taxonomy theory

My tags:

From Wikipedia, the free encyclopedia

This is a list of data structures. For a wider list of terms, see list of terms relating to algorithms and data structures.

Contents 1 Base Data Structures 2 Linear Data Structures 3 Non Linear Data Structures 4 Comparison

[edit] Base Data Structures

General type	Specific types
Primitive types	Boolean Character Integer String Double Float
Composite types	Struct Bit field Union Tagged union Gap Buffer

[edit] Linear Data Structures

General type	Specific types
List (or vector or sequence)	Array Bitmaps Images Heightfields Dynamic array Parallel array Sparse array Matrix Sparse matrix Bitboard
	Linked list Unrolled linked list Xor linked list Doubly linked list Zipper
	VList
	Buffer Stack Queue Priority queue Double-ended priority queue Deque Circular buffer
Associative array (a.k.a. dictionary or map)	Hash table
	Self-balancing binary search tree
	Skip list

[edit] Non Linear Data Structures

General type	Specific types
Graph data structures	Adjacency list Adjacency matrix Disjoint-set data structure Graph-structured stack Scene graph
Tree data structures	M-Way Tree B-tree 2-3 tree 2-3-4 tree B+ tree Generalized search tree B* tree B# tree UB tree R tree Hilbert R-tree R+ tree R* tree Enfilade
	K-ary tree Binary tree Binary heap Binary search trees (each tree node compares entire key values) Self-balancing binary search trees AVL tree Dancing tree Red-black tree AA tree Scapegoat tree Splay tree Top Trees Interval tree Treap Exponential tree
	Trie family (each tree node compares a bitslice of key values) Kd trie Radix tree Sparse tree Hash tree Suffix tree Directed Acyclic Word Graph (DAWG) Generalised suffix tree van Emde Boas tree
	Heap Binary heap Binomial heap Fibonacci heap 2-3 heap Soft heap Pairing heap Leftist heap Treap Beap Skew heap
	Other Search Trees (a,b) tree Fusion tree
	Syntax tree Abstract syntax tree Parse tree
	Space partitioning Bounding interval hierarchy Bounding volume hierarchy BSP tree Kd tree Adaptive kd tree Implicit kd tree Kdb tree Octree Quadtree
	Other trees And-or tree Hash tree Metric tree BK tree Cover tree M tree VP tree Finger tree 2-3 finger tree AVL finger tree Non-lazy finger tree Rope
	Decision theory Binary decision diagram Decision tree Alternating decision tree Minimax tree Expectiminimax tree

[edit] Comparison

An attempt to classify data structures based on feature attributes:

Structure	Stable	Unique	Cells per Node
Bag (multiset)	no	no	1
Set	no	yes	1
List	yes	no	1
Map	no	yes	2

"Stable" means 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.