Data Structures
The shapes data takes in memory, what each one buys you, and — the part usually left out — what each one costs you.
- Arrays and Dynamic ArraysOne contiguous block of memory, indexed by arithmetic — and the resize that makes appending free on average but occasionally O(n) at the worst moment.
- Linked ListsO(1) insertion that loses to an O(n) array up to a few thousand elements — the clearest case in this section of asymptotics losing to cache locality.
- Stacks and QueuesTwo structures defined entirely by what they refuse to let you do — and the one-line queue implementation that is quietly O(n) per dequeue.
- Hash TablesConstant-time lookup on average — and what "on average" is quietly hiding, from adversarial collisions to the rehash that stalls one unlucky request.
- Binary TreesO(log n) lookup that silently becomes O(n) the moment your data arrives sorted — and the four traversals that differ by one line each.
- HeapsA tree that lives in a flat array, gives you the smallest element in constant time, and quietly corrupts itself if you mutate a key in place.
- GraphsBFS and DFS differ by one line — queue or stack — and that one line decides whether you get shortest paths or a stack overflow.
- Advanced StructuresTries, segment trees, Fenwick trees, and disjoint sets — four structures that each buy one specific query, and what each one costs you for it.