LIST OF DATA STRUCTURES

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

[edit] Linear data structures

General type	Specific types
List (or vector)	Array Bitmaps Images Heightfields Dynamic array Parallel array Sparse array
	Linked list Unrolled linked list Xor linked list Doubly linked list
	VList
Associative array (a.k.a. dictionary or map)	Hash table
Associative array (a.k.a. dictionary or map)	Skip list
Stack (a.k.a LIFO Last in, first out)
Queue (a.k.a FIFO First in, first out)	Priority queue
Deque
Gap Buffer

[edit] Graph data structures

General type	Specific types
Adjacency list
Disjoint-set data structure
Graph-structured stack
Scene graph
Tree data structures	M-Way Tree
	B-tree 2-3-4 tree B+ tree B-tree R-tree R+ tree R tree
	Binary tree Binary search trees (each tree node compares entire key values) Self-balancing binary search trees AVL tree Red-black tree Scapegoat tree Splay tree Interval tree Treap
	Trie family (each tree node compares a bitslice of key values) Radix tree van Emde Boas tree Suffix tree Directed Acyclic Word Graph (DAWG)
	Heap Binary heap Binomial heap Fibonacci heap 2-3 heap Soft heap Pairing heap Leftist heap Treap Beap Skew heap
	Parse tree
	Space partitioning BSP tree Kd-tree Kdb-tree Quadtree Octree

[edit] Other data structures

An attempt to classify some of these based on feature attributes:

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

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


	Original Article from WikiPedia: http://en.wikipedia.org/wiki/List_of_data_structures Encyclopedia Dictionary * More Info