# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://bryan-guner.gitbook.io/my-docs/pythonnotes/misc/data-structures-types.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.