List of data structures

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 Data types 1.1 Primitive types 1.2 Composite types 1.3 Abstract data types 2 Linear data structures 2.1 Arrays 2.2 Lists 3 Trees 3.1 Binary trees 3.2 B-trees 3.3 Heaps 3.4 Tries 3.5 Multiway trees 3.6 Space-partitioning trees 3.7 Application specific trees 4 Hashes 5 Graphs

[edit] Data types

[edit] Primitive types

• Boolean
• Character
• Integer
• String
• Double
• Float

[edit] Composite types

• Record (also called tuple or struct)
• Union
• Tagged union (also called a variant, variant record, discriminated union, or disjoint union)

[edit] Abstract data types

• Container
• Deque
• List
• Map
• Multimap
• Multiset
• Priority queue
• Queue
• Set
• Stack
• String
• Tree

Some properties of abstract data types:

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.

[edit] Linear data structures

[edit] Arrays

• Array
• Dynamic array
• Hashed array tree
• Parallel array
• Sparse array
• Matrix
• Sparse matrix
• Circular buffer
• Gap Buffer
• Bit field
• Bit array
• Bitboard
• Bitmaps
• Images
• Heightfields
• Lookup table

[edit] Lists

• Linked list
• Doubly linked list
• Xor linked list
• Unrolled linked list
• Zipper
• VList
• Skip list
• Jump list
• Self-organizing list

[edit] Trees

[edit] Binary trees

• Binary tree
• Binary search tree
• Self-balancing binary search tree
• Randomized binary search tree
• Weight-balanced tree
• Threaded binary tree
• AVL tree
• Red-black tree
• AA tree
• Scapegoat tree
• Splay tree
• T-tree
• Rope
• Top Trees
• Tango Trees
• Cartesian tree
• Treap

[edit] B-trees

• B-tree
• B+ tree
• B*-tree
• B sharp tree
• Dancing tree
• 2-3 tree
• 2-3-4 tree
• Fusion tree
• Bx-tree

[edit] Heaps

• Heap
• Binary heap
• Binomial heap
• Fibonacci heap
• 2-3 heap
• Soft heap
• Pairing heap
• Leftist heap
• Treap
• Beap
• Skew heap
• Ternary heap
• D-ary heap
• Van Emde Boas tree

[edit] Tries

In these data structures each tree node compares a bit slice of key values.

• Trie
• Radix tree
• Suffix tree
• Suffix array
• FM-index
• Generalised suffix tree
• B-trie
• Judy array

[edit] Multiway trees

• Ternary search tree
• And–or tree
• (a,b)-tree
• Link/cut tree
• SPQR-tree
• Spaghetti stack
• Disjoint-set data structure
• Fusion tree
• Enfilade
• Exponential tree
• Fenwick tree

[edit] Space-partitioning trees

This is data structures used for space partitioning or binary space partitioning.

• Segment tree
• Interval tree
• Range tree
• Bin
• Kd-tree
• Implicit kd-tree
• Min/max kd-tree
• Adaptive k-d tree
• Kdb tree
• Quadtree
• Octree
• Linear octrees
• Z-order
• UB-tree
• R-tree
• R+ tree
• R* tree
• Hilbert R-tree
• X-tree
• Metric tree
• Cover tree
• M tree
• VP-tree
• BK-tree
• Bounding interval hierarchy
• BSP tree

[edit] Application specific trees

• Syntax tree
• Abstract syntax tree
• Parse tree
• Decision tree
• Alternating decision tree
• Minimax tree
• Expectiminimax tree
• Finger tree

[edit] Hashes

• Hash table
• Bloom filter
• Hash list
• Hash tree
• Prefix hash tree
• Hash trie
• Hash array mapped trie
• Distributed hash table
• Koorde

[edit] Graphs

• Graph
• Adjacency list
• Adjacency matrix
• Graph-structured stack
• Scene graph
• Binary decision diagram
• Zero suppressed decision diagram
• And-inverter graph
• Propositional directed acyclic graph