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
- 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.
1---2name: clrs-algorithms3description: Data structures and algorithms reference based on CLRS. Use this skill when implementing, discussing, or choosing data structures or algorithms. Auto-activates for algorithm selection, complexity analysis, and performance optimization. Comprehensive coverage of fundamental and advanced data structures with pseudocode examples.4---5
6# CLRS Data Structures & Algorithms Reference
7
8A 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.
9
10## When This Skill Activates
11
12This skill automatically activates when you:
13- Ask about or need to implement a data structure
14- Need to choose between data structures for a problem
15- Discuss time/space complexity trade-offs
16- Need algorithm implementations (sorting, searching, graph algorithms)
17- Mention specific structures: B-tree, heap, hash table, graph, etc.
18
19## Quick Data Structure Reference
20
21### Linear Structures
22| Structure | Access | Search | Insert | Delete | Use When |
23|-----------|--------|--------|--------|--------|----------|
24| [Array](data-structures/linear/array.md) | O(1) | O(n) | O(n) | O(n) | Known size, index access |
25| [Dynamic Array](data-structures/linear/dynamic-array.md) | O(1) | O(n) | O(1)* | O(n) | Unknown size, frequent append |
26| [Linked List](data-structures/linear/linked-list.md) | O(n) | O(n) | O(1) | O(1) | Frequent insert/delete |
27| [Stack](data-structures/linear/stack.md) | O(1) | O(n) | O(1) | O(1) | LIFO needed |
28| [Queue](data-structures/linear/queue.md) | O(1) | O(n) | O(1) | O(1) | FIFO needed |
29| [Deque](data-structures/linear/deque.md) | O(1) | O(n) | O(1) | O(1) | Both ends access |
30
31### Trees
32| Structure | Search | Insert | Delete | Use When |
33|-----------|--------|--------|--------|----------|
34| [Binary Search Tree](data-structures/trees/bst.md) | O(log n)* | O(log n)* | O(log n)* | Ordered data, frequent search |
35| [AVL Tree](data-structures/trees/avl-tree.md) | O(log n) | O(log n) | O(log n) | Guaranteed balance needed |
36| [Red-Black Tree](data-structures/trees/red-black-tree.md) | O(log n) | O(log n) | O(log n) | Frequent inserts/deletes |
37| [B-Tree](data-structures/trees/b-tree.md) | O(log n) | O(log n) | O(log n) | Disk-based storage |
38| [Trie](data-structures/trees/trie.md) | O(m) | O(m) | O(m) | String/prefix operations |
39| [Heap](data-structures/trees/heap.md) | O(1)/O(n) | O(log n) | O(log n) | Priority queue needed |
40| [Splay Tree](data-structures/trees/splay-tree.md) | O(log n)* | O(log n)* | O(log n)* | Self-adjusting, temporal locality |
41| [Treap](data-structures/trees/treap.md) | O(log n)* | O(log n)* | O(log n)* | Randomized balance, split/merge |
42| [Interval Tree](data-structures/trees/interval-tree.md) | O(log n) | O(log n) | O(log n) | Interval overlap queries |
43| [Order-Statistic Tree](data-structures/trees/order-statistic-tree.md) | O(log n) | O(log n) | O(log n) | Rank/select queries |
44| [K-D Tree](data-structures/trees/kd-tree.md) | O(log n)* | O(log n)* | O(log n)* | Multi-dimensional spatial data |
45
46### Hash-Based
47| Structure | Search | Insert | Delete | Use When |
48|-----------|--------|--------|--------|----------|
49| [Hash Table](data-structures/hash-based/hash-table.md) | O(1)* | O(1)* | O(1)* | Fast key-value lookup |
50| [Hash Set](data-structures/hash-based/hash-set.md) | O(1)* | O(1)* | O(1)* | Unique membership testing |
51| [Bloom Filter](data-structures/hash-based/bloom-filter.md) | O(k) | O(k) | N/A | Probabilistic membership |
52
53### Graphs
54| Structure | Space | Add Edge | Query Edge | Use When |
55|-----------|-------|----------|------------|----------|
56| [Adjacency List](data-structures/graphs/adjacency-list.md) | O(V+E) | O(1) | O(degree) | Sparse graphs |
57| [Adjacency Matrix](data-structures/graphs/adjacency-matrix.md) | O(V²) | O(1) | O(1) | Dense graphs |
58
59### Graph Algorithms
60| Algorithm | Time | Use When |
61|-----------|------|----------|
62| [Network Flow](data-structures/graphs/network-flow.md) | O(VE²) | Max flow, bipartite matching, min cut |
63| [Strongly Connected Components](data-structures/graphs/strongly-connected-components.md) | O(V+E) | Find SCCs, 2-SAT, dependency analysis |
64
65### Strings
66| Structure | Build | Search | Use When |
67|-----------|-------|--------|----------|
68| [Suffix Array](data-structures/strings/suffix-array.md) | O(n log n) | O(m log n) | Space-efficient string matching |
69| [Suffix Tree](data-structures/strings/suffix-tree.md) | O(n) | O(m) | Fast pattern matching, LCS |
70| [String Algorithms](data-structures/strings/string-algorithms.md) | O(m) | O(n) | KMP, Rabin-Karp, Boyer-Moore, Aho-Corasick |
71
72### Advanced
73| Structure | Use When |
74|-----------|----------|
75| [Skip List](data-structures/advanced/skip-list.md) | Probabilistic balanced list |
76| [Disjoint Set](data-structures/advanced/disjoint-set.md) | Union-find operations |
77| [Segment Tree](data-structures/advanced/segment-tree.md) | Range queries with updates |
78| [Fenwick Tree](data-structures/advanced/fenwick-tree.md) | Prefix sums with updates |
79| [Fibonacci Heap](data-structures/advanced/fibonacci-heap.md) | Dijkstra, Prim with O(1) decrease-key |
80| [Binomial Heap](data-structures/advanced/binomial-heap.md) | Mergeable priority queue |
81| [van Emde Boas Tree](data-structures/advanced/van-emde-boas-tree.md) | Integer keys with O(log log u) operations |
82
83### Algorithms
84| Algorithm | Use When |
85|-----------|----------|
86| [Sorting Algorithms](data-structures/algorithms/sorting-algorithms.md) | QuickSort, MergeSort, HeapSort, RadixSort, and more |
87
88*\* = amortized or average case*
89
90## Decision Guides
91
92- [Which Data Structure Should I Use?](data-structure-selection.md) - Decision guide by use case
93- [Complexity Cheat Sheet](complexity-cheat-sheet.md) - Quick reference for Big-O
94
95## How to Use This Reference
96
971. **Choosing a structure**: Start with the decision guides
982. **Learning a structure**: Read the full documentation with examples
993. **Quick reminder**: Use the tables above for at-a-glance reference
1004. **Implementation**: Follow the pseudocode, adapt to your language
101
102## Language Translation Notes
103
104The pseudocode in this reference uses these conventions:
105- `class` for type definitions
106- `function` for methods/functions
107- `->` for method calls on objects
108- `//` for comments
109- Type hints shown as `name: Type`
110
111Translate to your language:
112- **PHP**: `class`, `function`, `->`, `//`, type hints in docblocks or PHP 8+
113- **JavaScript/TypeScript**: `class`, `function`/arrow, `.`, `//`, TS types
114- **Python**: `class`, `def`, `.`, `#`, type hints
115- **Java/C#**: Direct mapping with `new`, generics
116
117---
118
119*Based on concepts from "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS), MIT Press.*
majiayu000