> For the complete documentation index, see [llms.txt](https://bryan-guner.gitbook.io/my-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bryan-guner.gitbook.io/my-docs/pythonnotes/misc/data-structures-types.md).

# Data Structures Types

### Linear data structures

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

#### Arrays\[[edit](https://en.wikipedia.org/w/index.php?title=List_of_data_structures\&action=edit\&section=6)]

* [Array](https://en.wikipedia.org/wiki/Array_data_structure)
* [Bit array](https://en.wikipedia.org/wiki/Bit_array)
* [Bit field](https://en.wikipedia.org/wiki/Bit_field)
* [Bitboard](https://en.wikipedia.org/wiki/Bitboard)
* [Bitmap](https://en.wikipedia.org/wiki/Bitmap)
* [Circular buffer](https://en.wikipedia.org/wiki/Circular_buffer)
* [Control table](https://en.wikipedia.org/wiki/Control_table)
* [Image](https://en.wikipedia.org/wiki/System_image)
* [Dope vector](https://en.wikipedia.org/wiki/Dope_vector)
* [Dynamic array](https://en.wikipedia.org/wiki/Dynamic_array)
* [Gap buffer](https://en.wikipedia.org/wiki/Gap_buffer)
* [Hashed array tree](https://en.wikipedia.org/wiki/Hashed_array_tree)
* [Lookup table](https://en.wikipedia.org/wiki/Lookup_table)
* [Matrix](https://en.wikipedia.org/wiki/Matrix_%28computer_science%29)
* [Parallel array](https://en.wikipedia.org/wiki/Parallel_array)
* [Sorted array](https://en.wikipedia.org/wiki/Sorted_array)
* [Sparse matrix](https://en.wikipedia.org/wiki/Sparse_matrix)
* [Iliffe vector](https://en.wikipedia.org/wiki/Iliffe_vector)
* [Variable-length array](https://en.wikipedia.org/wiki/Variable-length_array)

#### Lists

* [Doubly linked list](https://en.wikipedia.org/wiki/Doubly_linked_list)
* [Array list](https://en.wikipedia.org/wiki/Array_list)
* [Linked list](https://en.wikipedia.org/wiki/Linked_list)
* [Association list](https://en.wikipedia.org/wiki/Association_list)
* [Self-organizing list](https://en.wikipedia.org/wiki/Self-organizing_list)
* [Skip list](https://en.wikipedia.org/wiki/Skip_list)
* [Unrolled linked list](https://en.wikipedia.org/wiki/Unrolled_linked_list)
* VList
* [Conc-tree list](https://en.wikipedia.org/wiki/Conc-tree_list)
* [Xor linked list](https://en.wikipedia.org/wiki/Xor_linked_list)
* [Zipper](https://en.wikipedia.org/wiki/Zipper_%28data_structure%29)
* [Doubly connected edge list](https://en.wikipedia.org/wiki/Doubly_connected_edge_list) also known as half-edge
* [Difference list](https://en.wikipedia.org/wiki/Difference_list)
* [Free list](https://en.wikipedia.org/wiki/Free_list)

### Trees

Main article: [Tree (data structure)](https://en.wikipedia.org/wiki/Tree_%28data_structure%29)

#### Binary trees

* [AA tree](https://en.wikipedia.org/wiki/AA_tree)
* [AVL tree](https://en.wikipedia.org/wiki/AVL_tree)
* [Binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree)
* [Binary tree](https://en.wikipedia.org/wiki/Binary_tree)
* [Cartesian tree](https://en.wikipedia.org/wiki/Cartesian_tree)
* [Conc-tree list](https://en.wikipedia.org/wiki/Conc-tree_list)
* [Left-child right-sibling binary tree](https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree)
* [Order statistic tree](https://en.wikipedia.org/wiki/Order_statistic_tree)
* [Pagoda](https://en.wikipedia.org/wiki/Pagoda_%28data_structure%29)
* [Randomized binary search tree](https://en.wikipedia.org/wiki/Randomized_binary_search_tree)
* [Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)
* [Rope](https://en.wikipedia.org/wiki/Rope_%28computer_science%29)
* [Scapegoat tree](https://en.wikipedia.org/wiki/Scapegoat_tree)
* [Self-balancing binary search tree](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)
* [Splay tree](https://en.wikipedia.org/wiki/Splay_tree)
* [T-tree](https://en.wikipedia.org/wiki/T-tree)
* [Tango tree](https://en.wikipedia.org/wiki/Tango_tree)
* [Threaded binary tree](https://en.wikipedia.org/wiki/Threaded_binary_tree)
* [Top tree](https://en.wikipedia.org/wiki/Top_tree)
* [Treap](https://en.wikipedia.org/wiki/Treap)
* [WAVL tree](https://en.wikipedia.org/wiki/WAVL_tree)
* [Weight-balanced tree](https://en.wikipedia.org/wiki/Weight-balanced_tree)

#### B-trees

* [B-tree](https://en.wikipedia.org/wiki/B-tree)
* [B+ tree](https://en.wikipedia.org/wiki/B%2B_tree)
* [B\*-tree](https://en.wikipedia.org/wiki/B*-tree)
* [B sharp tree](https://en.wikipedia.org/w/index.php?title=B_sharp_tree\&action=edit\&redlink=1)
* [Dancing tree](https://en.wikipedia.org/wiki/Dancing_tree)
* [2–3 tree](https://en.wikipedia.org/wiki/2%E2%80%933_tree)
* [2–3–4 tree](https://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree)
* [Queap](https://en.wikipedia.org/wiki/Queap)
* [Fusion tree](https://en.wikipedia.org/wiki/Fusion_tree)
* [Bx-tree](https://en.wikipedia.org/wiki/Bx-tree_Moving_Object_Index)
* [AList](https://en.wikipedia.org/w/index.php?title=AList\&action=edit\&redlink=1)

#### Heaps

* [Heap](https://en.wikipedia.org/wiki/Heap_%28data_structure%29)
* [Binary heap](https://en.wikipedia.org/wiki/Binary_heap)
* [B-heap](https://en.wikipedia.org/wiki/B-heap)
* [Weak heap](https://en.wikipedia.org/wiki/Weak_heap)
* [Binomial heap](https://en.wikipedia.org/wiki/Binomial_heap)
* [Fibonacci heap](https://en.wikipedia.org/wiki/Fibonacci_heap)
* [AF-heap](https://en.wikipedia.org/wiki/AF-heap)
* [Leonardo heap](https://en.wikipedia.org/wiki/Smoothsort)
* [2–3 heap](https://en.wikipedia.org/wiki/2%E2%80%933_heap)
* [Soft heap](https://en.wikipedia.org/wiki/Soft_heap)
* [Pairing heap](https://en.wikipedia.org/wiki/Pairing_heap)
* [Leftist heap](https://en.wikipedia.org/wiki/Leftist_tree)
* [Treap](https://en.wikipedia.org/wiki/Treap)
* [Beap](https://en.wikipedia.org/wiki/Beap)
* [Skew heap](https://en.wikipedia.org/wiki/Skew_heap)
* [Ternary heap](https://en.wikipedia.org/wiki/Ternary_heap)
* [D-ary heap](https://en.wikipedia.org/wiki/D-ary_heap)
* [Brodal queue](https://en.wikipedia.org/wiki/Brodal_queue)

#### Trees

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

* [Tree (data structure)](https://en.wikipedia.org/wiki/Tree_%28data_structure%29)
* [Radix tree](https://en.wikipedia.org/wiki/Radix_tree)
* [Suffix tree](https://en.wikipedia.org/wiki/Suffix_tree)
* [Suffix array](https://en.wikipedia.org/wiki/Suffix_array)
* [Compressed suffix array](https://en.wikipedia.org/wiki/Compressed_suffix_array)
* [FM-index](https://en.wikipedia.org/wiki/FM-index)
* [Generalised suffix tree](https://en.wikipedia.org/wiki/Generalised_suffix_tree)
* [B-tree](https://en.wikipedia.org/wiki/B-tree)
* [Judy array](https://en.wikipedia.org/wiki/Judy_array)
* [X-fast trie](https://en.wikipedia.org/wiki/X-fast_trie)
* [Y-fast trie](https://en.wikipedia.org/wiki/Y-fast_trie)
* [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree)
* [C tree](https://en.wikipedia.org/w/index.php?title=Ctree\&action=edit\&redlink=1)

#### Multi-way trees

* [Ternary tree](https://en.wikipedia.org/wiki/Ternary_tree)
* [K-ary tree](https://en.wikipedia.org/wiki/K-ary_tree)
* [And–or tree](https://en.wikipedia.org/wiki/And%E2%80%93or_tree)
* [(a,b)-tree](https://en.wikipedia.org/wiki/%28a,b%29-tree)
* [Link/cut tree](https://en.wikipedia.org/wiki/Link/cut_tree)
* [SPQR-tree](https://en.wikipedia.org/wiki/SPQR-tree)
* [Spaghetti stack](https://en.wikipedia.org/wiki/Spaghetti_stack)
* [Disjoint-set data structure (Union-find data structure)](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
* [Fusion tree](https://en.wikipedia.org/wiki/Fusion_tree)
* [Enfilade](https://en.wikipedia.org/wiki/Enfilade_%28Xanadu%29)
* [Exponential tree](https://en.wikipedia.org/wiki/Exponential_tree)
* [Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree)
* [Van Emde Boas tree](https://en.wikipedia.org/wiki/Van_Emde_Boas_tree)
* [Rose tree](https://en.wikipedia.org/wiki/Rose_tree)

#### Space-partitioning trees

These are data structures used for [space partitioning](https://en.wikipedia.org/wiki/Space_partitioning) or [binary space partitioning](https://en.wikipedia.org/wiki/Binary_space_partitioning).

* [Segment tree](https://en.wikipedia.org/wiki/Segment_tree)
* [Interval tree](https://en.wikipedia.org/wiki/Interval_tree)
* [Range tree](https://en.wikipedia.org/wiki/Range_tree)
* [Bin](https://en.wikipedia.org/wiki/Bin_%28computational_geometry%29)
* [K-d tree](https://en.wikipedia.org/wiki/K-d_tree)
* [Implicit k-d tree](https://en.wikipedia.org/wiki/Implicit_k-d_tree)
* [Min/max k-d tree](https://en.wikipedia.org/wiki/Min/max_kd-tree)
* [Relaxed k-d tree](https://en.wikipedia.org/wiki/Relaxed_k-d_tree)
* [Adaptive k-d tree](https://en.wikipedia.org/wiki/Adaptive_k-d_tree)
* [Quadtree](https://en.wikipedia.org/wiki/Quadtree)
* [Octree](https://en.wikipedia.org/wiki/Octree)
* [Linear octree](https://en.wikipedia.org/wiki/Linear_octree)
* [Z-order](https://en.wikipedia.org/wiki/Z-order_%28curve%29)
* [UB-tree](https://en.wikipedia.org/wiki/UB-tree)
* [R-tree](https://en.wikipedia.org/wiki/R-tree)
* [R+ tree](https://en.wikipedia.org/wiki/R%2B_tree)
* [R\* tree](https://en.wikipedia.org/wiki/R*_tree)
* [Hilbert R-tree](https://en.wikipedia.org/wiki/Hilbert_R-tree)
* [X-tree](https://en.wikipedia.org/wiki/X-tree)
* [Metric tree](https://en.wikipedia.org/wiki/Metric_tree)
* [Cover tree](https://en.wikipedia.org/wiki/Cover_tree)
* [M-tree](https://en.wikipedia.org/wiki/M-tree)
* [VP-tree](https://en.wikipedia.org/wiki/VP-tree)
* [BK-tree](https://en.wikipedia.org/wiki/BK-tree)
* [Bounding interval hierarchy](https://en.wikipedia.org/wiki/Bounding_interval_hierarchy)
* [Bounding volume hierarchy](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy)
* [BSP tree](https://en.wikipedia.org/wiki/BSP_tree)
* [Rapidly exploring random tree](https://en.wikipedia.org/wiki/Rapidly_exploring_random_tree)

#### Application-specific trees

* [Abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree)
* [Parse tree](https://en.wikipedia.org/wiki/Parse_tree)
* [Decision tree](https://en.wikipedia.org/wiki/Decision_tree)
* [Alternating decision tree](https://en.wikipedia.org/wiki/Alternating_decision_tree)
* [Minimax tree](https://en.wikipedia.org/wiki/Minmax)
* [Expectiminimax tree](https://en.wikipedia.org/wiki/Expectiminimax_tree)
* [Finger tree](https://en.wikipedia.org/wiki/Finger_tree)
* [Expression tree](https://en.wikipedia.org/wiki/Expression_tree)
* [Log-structured merge-tree](https://en.wikipedia.org/wiki/Log-structured_merge-tree)
* [Lexicographic Search Tree](https://en.wikipedia.org/w/index.php?title=Lexicographic_Search_Tree\&action=edit\&redlink=1)

### Hash-based structures

* [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter)
* [Count–min sketch](https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch)
* [Distributed hash table](https://en.wikipedia.org/wiki/Distributed_hash_table)
* [Double hashing](https://en.wikipedia.org/wiki/Double_hashing)
* [Dynamic perfect hash table](https://en.wikipedia.org/wiki/Dynamic_perfect_hashing)
* [Hash array mapped trie](https://en.wikipedia.org/wiki/Hash_array_mapped_trie)
* [Hash list](https://en.wikipedia.org/wiki/Hash_list)
* [Hash table](https://en.wikipedia.org/wiki/Hash_table)
* [Hash tree](https://en.wikipedia.org/wiki/Hash_tree_%28disambiguation%29)
* [Hash trie](https://en.wikipedia.org/wiki/Hash_trie)
* [Koorde](https://en.wikipedia.org/wiki/Koorde)
* [Prefix hash tree](https://en.wikipedia.org/wiki/Prefix_hash_tree)
* [Rolling hash](https://en.wikipedia.org/wiki/Rolling_hash)
* [MinHash](https://en.wikipedia.org/wiki/MinHash)
* [Quotient filter](https://en.wikipedia.org/wiki/Quotient_filter)
* [Ctrie](https://en.wikipedia.org/wiki/Ctrie)

### Graphs

Many [graph](https://en.wikipedia.org/wiki/Graph_%28discrete_mathematics%29)-based data structures are used in computer science and related fields:

* [Graph](https://en.wikipedia.org/wiki/Graph_%28data_structure%29)
* [Adjacency list](https://en.wikipedia.org/wiki/Adjacency_list)
* [Adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix)
* [Graph-structured stack](https://en.wikipedia.org/wiki/Graph-structured_stack)
* [Scene graph](https://en.wikipedia.org/wiki/Scene_graph)
* [Decision tree](https://en.wikipedia.org/wiki/Decision_tree)
  * [Binary decision diagram](https://en.wikipedia.org/wiki/Binary_decision_diagram)
* [Zero-suppressed decision diagram](https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram)
* [And-inverter graph](https://en.wikipedia.org/wiki/And-inverter_graph)
* [Directed graph](https://en.wikipedia.org/wiki/Directed_graph)
* [Directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)
* [Propositional directed acyclic graph](https://en.wikipedia.org/wiki/Propositional_directed_acyclic_graph)
* [Multigraph](https://en.wikipedia.org/wiki/Multigraph)
* [Hypergraph](https://en.wikipedia.org/wiki/Hypergraph)

### Other

* [Lightmap](https://en.wikipedia.org/wiki/Lightmap)
* [Winged edge](https://en.wikipedia.org/wiki/Winged_edge)
* [Quad-edge](https://en.wikipedia.org/wiki/Quad-edge)
* [Routing table](https://en.wikipedia.org/wiki/Routing_table)
* [Symbol table](https://en.wikipedia.org/wiki/Symbol_table)