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.