Data Structures

Arrays, lists, trees, hash tables and their trade-offs.

Data Structures is taught here in 13 lessons, running from Arrays, linked lists, stacks and queues through to Benchmarking and testing your data structure. Each lesson takes one topic, shows the working code, and links onward to the next, so the course can be read straight through in order.

Lessons

1. Arrays, linked lists, stacks and queuesContiguous memory versus pointers, why pop from the front is the classic performance mistake, and how to pick a container.
2. Hash tablesHow hashing turns a key into a slot, what collisions and load factor do to performance, and what makes a key usable.
3. Trees and choosing a structureBinary search trees, why balance decides everything, heaps for priority, and a decision table for real code.
4. Amortised analysis: what operations really costBest, average and worst case per operation, why a single push onto a dynamic array is sometimes O(n) but still O(1) on average, and why constant factors and cache locality decide real performance.
5. Sets, maps and the abstract data type viewSeparating the interface from the implementation, ordered versus unordered iteration, the guarantees each container actually makes, and how to read a standard library's naming.
6. Heaps and priority queuesThe array layout and heap invariant, sift-up and sift-down, linear-time bulk build, and the top-k and scheduling patterns that make a priority queue the right tool.
7. Graphs and their representationsAdjacency lists, matrices and edge lists compared, how directed and weighted edges change the storage, degree and connectivity basics, and how to pick based on density.
8. Balanced trees: AVL, red-black and B-treesWhy an unbalanced BST degrades to a list, how rotations restore height balance, what red-black invariants buy over AVL, and why databases use wide B-tree nodes.
9. Tries and prefix treesNode-per-character layout, insert and prefix search, the memory cost of wide alphabets, compressed and radix variants, and the autocomplete patterns tries exist for.
10. Union-Find and disjoint setsThe parent array, union by rank and path compression, why the amortised cost is nearly constant, and the cycle detection and clustering patterns it powers.
11. LRU caches and composite structuresCombining a hash map with a doubly linked list for O(1) eviction, the TTL and LFU variants, thread-safety concerns, and the metrics that tell you whether the cache helps.
12. Probabilistic structures: Bloom filters and skip listsBloom filters and the false positive rate you trade for memory, counting variants, the expected cost of skip list operations, and count-min sketches for frequency estimates.
13. Benchmarking and testing your data structureInvariant checks that run after every operation, randomised fuzzing against a reference implementation, and how to measure throughput, latency and memory without fooling yourself.

More in Computer Science Fundamentals

Algorithms Computer Networks Operating Systems Character Encodings Hashing & Checksums Data Formats Dates & Time Regular Expressions

FAQ