CLRS Data Structures & Algorithms Reference

A comprehensive reference for data structures and algorithms based on "Introduction to Algorithms" (CLRS). This skill provides language-agnostic guidance with pseudocode examples that can be translated to any programming language.

When This Skill Activates

This skill automatically activates when you:

• Ask about or need to implement a data structure
• Need to choose between data structures for a problem
• Discuss time/space complexity trade-offs
• Need algorithm implementations (sorting, searching, graph algorithms)
• Mention specific structures: B-tree, heap, hash table, graph, etc.

Quick Data Structure Reference

Linear Structures

| Structure | Access | Search | Insert | Delete | Use When | |-----------|--------|--------|--------|--------|----------| | Array | O(1) | O(n) | O(n) | O(n) | Known size, index access | | Dynamic Array | O(1) | O(n) | O(1)* | O(n) | Unknown size, frequent append | | Linked List | O(n) | O(n) | O(1) | O(1) | Frequent insert/delete | | Stack | O(1) | O(n) | O(1) | O(1) | LIFO needed | | Queue | O(1) | O(n) | O(1) | O(1) | FIFO needed | | Deque | O(1) | O(n) | O(1) | O(1) | Both ends access |

Trees

| Structure | Search | Insert | Delete | Use When | |-----------|--------|--------|--------|----------| | Binary Search Tree | O(log n)* | O(log n)* | O(log n)* | Ordered data, frequent search | | AVL Tree | O(log n) | O(log n) | O(log n) | Guaranteed balance needed | | Red-Black Tree | O(log n) | O(log n) | O(log n) | Frequent inserts/deletes | | B-Tree | O(log n) | O(log n) | O(log n) | Disk-based storage | | Trie | O(m) | O(m) | O(m) | String/prefix operations | | Heap | O(1)/O(n) | O(log n) | O(log n) | Priority queue needed | | Splay Tree | O(log n)* | O(log n)* | O(log n)* | Self-adjusting, temporal locality | | Treap | O(log n)* | O(log n)* | O(log n)* | Randomized balance, split/merge | | Interval Tree | O(log n) | O(log n) | O(log n) | Interval overlap queries | | Order-Statistic Tree | O(log n) | O(log n) | O(log n) | Rank/select queries | | K-D Tree | O(log n)* | O(log n)* | O(log n)* | Multi-dimensional spatial data |

Hash-Based

| Structure | Search | Insert | Delete | Use When | |-----------|--------|--------|--------|----------| | Hash Table | O(1)* | O(1)* | O(1)* | Fast key-value lookup | | Hash Set | O(1)* | O(1)* | O(1)* | Unique membership testing | | Bloom Filter | O(k) | O(k) | N/A | Probabilistic membership |

Graphs

| Structure | Space | Add Edge | Query Edge | Use When | |-----------|-------|----------|------------|----------| | Adjacency List | O(V+E) | O(1) | O(degree) | Sparse graphs | | Adjacency Matrix | O(V²) | O(1) | O(1) | Dense graphs |

Graph Algorithms

| Algorithm | Time | Use When | |-----------|------|----------| | Network Flow | O(VE²) | Max flow, bipartite matching, min cut | | Strongly Connected Components | O(V+E) | Find SCCs, 2-SAT, dependency analysis |

Strings

| Structure | Build | Search | Use When | |-----------|-------|--------|----------| | Suffix Array | O(n log n) | O(m log n) | Space-efficient string matching | | Suffix Tree | O(n) | O(m) | Fast pattern matching, LCS | | String Algorithms | O(m) | O(n) | KMP, Rabin-Karp, Boyer-Moore, Aho-Corasick |

Advanced

| Structure | Use When | |-----------|----------| | Skip List | Probabilistic balanced list | | Disjoint Set | Union-find operations | | Segment Tree | Range queries with updates | | Fenwick Tree | Prefix sums with updates | | Fibonacci Heap | Dijkstra, Prim with O(1) decrease-key | | Binomial Heap | Mergeable priority queue | | van Emde Boas Tree | Integer keys with O(log log u) operations |

Algorithms

| Algorithm | Use When | |-----------|----------| | Sorting Algorithms | QuickSort, MergeSort, HeapSort, RadixSort, and more |

* = amortized or average case

Decision Guides

• Which Data Structure Should I Use? - Decision guide by use case
• Complexity Cheat Sheet - Quick reference for Big-O

How to Use This Reference

1. Choosing a structure: Start with the decision guides
2. Learning a structure: Read the full documentation with examples
3. Quick reminder: Use the tables above for at-a-glance reference
4. Implementation: Follow the pseudocode, adapt to your language

Language Translation Notes

The pseudocode in this reference uses these conventions:

• class for type definitions
• function for methods/functions
• -> for method calls on objects
• // for comments
• Type hints shown as name: Type

Translate to your language:

• PHP: class, function, ->, //, type hints in docblocks or PHP 8+
• JavaScript/TypeScript: class, function/arrow, ., //, TS types
• Python: class, def, ., #, type hints
• Java/C#: Direct mapping with new, generics

---

Based on concepts from "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS), MIT Press.