Data StructuresInteractive lecture notes and videos
Nine chapters on the structures behind every program: arrays and linked lists, stacks and queues, recursion, search trees, hash tables, heaps and graphs, with complexity and proof methods as the common language. Every chapter has short videos, interactive notes that ask you to predict before they show you, a self-check and exercises. Every program has been run, and every output shown is the real output. Pick Python or Java at the top: the concepts are shared, the code is in your language.
- Boxi YuINSTRUCTOR
- Yintong HuoINSTRUCTOR
Complexity and Proof Methods
Counting operations and Big-O · Proving asymptotic bounds · Amortized analysis · Induction and loop invariants
Arrays and Linked Lists
Arrays in memory · Dynamic arrays and resizing · Linked lists: rewiring pointers · Singly, doubly and circularly linked lists
Linear Data Structures
Stacks · Queues: circular array and linked · Deques · Applications: bracket matching, BFS preview
Recursion
The call stack and recursion trees · Binary search and recurrences · Merge sort · Quicksort
Trees and Binary Search Trees
Tree terms and traversals · BST search and insert · BST delete · Why BSTs degenerate
Sorted Maps and Balanced Search Trees
Rotations and AVL trees · (2,4) trees: split and fuse · Red-black trees as (2,4) trees · Sorted map operations
Unsorted Maps and Hashing
Hash functions · Separate chaining · Open addressing · Load factor and rehashing
Heaps and Priority Queues
The priority queue ADT · Heap: up-heap and down-heap · Bottom-up heap construction · Heap sort
Graphs and Graph Algorithms
Graph representations · BFS and DFS · Dijkstra's shortest paths · Minimum spanning trees and union-find