Data Structures
Study Data Structures
Hash tables, trees & heaps, arrays and memory layout, and how to choose the right structure
Topics
Arrays, Lists & Memory Layout
Arrays are the structure everything else is built on, and their advantage is not an operation count — it is physical contiguity. A CPU reads memory in cache lines of 64 bytes and aggressively prefetches sequential addresses, so a linear…
Choosing the Right Structure
This is the part of the competency that actually shows up in code review. The question is never "what is a red-black tree" — it is "you wrote List.Contains inside a loop over another list, do you know that is O(n·m)?" This note is the…
Hash Tables
A hash table turns a key into an array index by hashing it, which is why lookup is O(1) — you compute the address rather than search for it. Everything interesting follows from what happens when two keys compute the same address. The…
Trees & Heaps
Trees buy you ordering at O(log n) — but only while they stay balanced, and an unbalanced binary search tree is a linked list wearing a costume. That single fact explains red-black trees, AVL trees, and B-trees, and it explains why…