Data Structures Types

Linear data structures

A data structure is said to be linear if its elements form a sequence.

Arrays[edit]

• Array

• Bit array

• Bit field

• Bitboard

• Bitmap

• Circular buffer

• Control table

• Image

• Dope vector

• Dynamic array

• Gap buffer

• Hashed array tree

• Lookup table

• Matrix

• Parallel array

• Sorted array

• Sparse matrix

• Iliffe vector

• Variable-length array

Lists

• Doubly linked list

• Array list

• Linked list

• Association list

• Self-organizing list

• Skip list

• Unrolled linked list

• VList

• Conc-tree list

• Xor linked list

• Zipper

• Doubly connected edge list also known as half-edge

• Difference list

• Free list

Trees

Main article: Tree (data structure)

Binary trees

• AA tree

• AVL tree

• Binary search tree

• Binary tree

• Cartesian tree

• Conc-tree list

• Left-child right-sibling binary tree

• Order statistic tree

• Pagoda

• Randomized binary search tree

• Red–black tree

• Rope

• Scapegoat tree

• Self-balancing binary search tree

• Splay tree

• T-tree

• Tango tree

• Threaded binary tree

• Top tree

• Treap

• WAVL tree

• Weight-balanced tree

B-trees

• B-tree

• B+ tree

• B*-tree

• B sharp tree

• Dancing tree

• 2–3 tree

• 2–3–4 tree

• Queap

• Fusion tree

• Bx-tree

• AList

Heaps

• Heap

• Binary heap

• B-heap

• Weak heap

• Binomial heap

• Fibonacci heap

• AF-heap

• Leonardo heap

• 2–3 heap

• Soft heap

• Pairing heap

• Leftist heap

• Treap

• Beap

• Skew heap

• Ternary heap

• D-ary heap

• Brodal queue

Trees

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

• Tree (data structure)

• Radix tree

• Suffix tree

• Suffix array

• Compressed suffix array

• FM-index

• Generalised suffix tree

• B-tree

• Judy array

• X-fast trie

• Y-fast trie

• Merkle tree

• C tree

Multi-way trees

• Ternary tree

• K-ary tree

• And–or tree

• (a,b)-tree

• Link/cut tree

• SPQR-tree

• Spaghetti stack

• Disjoint-set data structure (Union-find data structure)

• Fusion tree

• Enfilade

• Exponential tree

• Fenwick tree

• Van Emde Boas tree

• Rose tree

Space-partitioning trees

These are data structures used for space partitioning or binary space partitioning.

• Segment tree

• Interval tree

• Range tree

• Bin

• K-d tree

• Implicit k-d tree

• Min/max k-d tree

• Relaxed k-d tree

• Adaptive k-d tree

• Quadtree

• Octree

• Linear octree

• 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

• Bounding volume hierarchy

• BSP tree

• Rapidly exploring random tree

Application-specific trees

• Abstract syntax tree

• Parse tree

• Decision tree

• Alternating decision tree

• Minimax tree

• Expectiminimax tree

• Finger tree

• Expression tree

• Log-structured merge-tree

• Lexicographic Search Tree

Hash-based structures

• Bloom filter

• Count–min sketch

• Distributed hash table

• Double hashing

• Dynamic perfect hash table

• Hash array mapped trie

• Hash list

• Hash table

• Hash tree

• Hash trie

• Koorde

• Prefix hash tree

• Rolling hash

• MinHash

• Quotient filter

• Ctrie

Graphs

Many graph-based data structures are used in computer science and related fields:

• Graph

• Adjacency list

• Adjacency matrix

• Graph-structured stack

• Scene graph

• Decision tree

  • Binary decision diagram

• Zero-suppressed decision diagram

• And-inverter graph

• Directed graph

• Directed acyclic graph

• Propositional directed acyclic graph

• Multigraph

• Hypergraph

Other

• Lightmap

• Winged edge

• Quad-edge

• Routing table

• Symbol table