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 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.

clrs-algorithms