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
Graph Algorithms
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
Algorithms
** = amortized or average case*
Decision Guides
How to Use This Reference
- Choosing a structure: Start with the decision guides
- Learning a structure: Read the full documentation with examples
- Quick reminder: Use the tables above for at-a-glance reference
- Implementation: Follow the pseudocode, adapt to your language
Language Translation Notes
The pseudocode in this reference uses these conventions:
class for type definitionsfunction 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.*
