Skip to content

Latest commit

 

History

History
79 lines (75 loc) · 1.91 KB

File metadata and controls

79 lines (75 loc) · 1.91 KB

List of data structures used in competitive programming, organized from basic to advanced:

Basic Data Structures:

  1. Arrays
    • Static Arrays
    • Dynamic Arrays (Vector in C++, ArrayList in Java)
  2. Linked Lists
    • Singly Linked List
    • Doubly Linked List
  3. Stacks
  4. Queues
    • Simple Queue
    • Deque (Double-Ended Queue)
    • Circular Queue
  5. Strings

Intermediate Data Structures:

  1. Hash Tables
    • Hash Maps
    • Hash Sets
  2. Binary Trees
    • Binary Search Tree (BST)
    • Balanced BSTs (AVL Tree, Red-Black Tree)
  3. Heaps
    • Binary Heap (Min-Heap, Max-Heap)
    • Binomial Heap
    • Fibonacci Heap
  4. Tries
    • Standard Trie
    • Compressed Trie (Radix Tree)
  5. Graphs
    • Adjacency Matrix
    • Adjacency List
  6. Segment Trees
    • Point Updates
    • Range Updates
    • Lazy Propagation
  7. Fenwick Tree (Binary Indexed Tree)
    • Point Updates
    • Range Queries

Advanced Data Structures:

  1. Disjoint Set Union (DSU) / Union-Find
    • Path Compression
    • Union by Rank/Size
  2. Balanced Trees
    • Splay Tree
    • Treap
    • Scapegoat Tree
  3. Sparse Table
  4. Heavy-Light Decomposition
  5. Suffix Trees
  6. Suffix Arrays
  7. K-D Trees
  8. Range Minimum Query (RMQ) Structures
  9. Fenwick Tree of Fenwick Trees (2D BIT)
  10. Dynamic Segment Trees
  11. Persistent Data Structures
    • Persistent Segment Tree
    • Persistent Fenwick Tree
  12. Self-Adjusting Heaps
    • Pairing Heap
  13. Suffix Automaton
  14. Wavelet Trees
  15. Link/Cut Tree
  16. Euler Tour Tree
  17. B-Trees
  18. Trie Variants
    • Aho-Corasick Automaton
  19. Bloom Filter
  20. Skip Lists
  21. Van Emde Boas Tree

Specialized Data Structures:

  1. Doubly Linked List with Skip Pointers
  2. Dancing Links (Knuth’s Algorithm X)
  3. Cuckoo Hashing
  4. X-fast and Y-fast Tries
  5. Fusion Trees