What Must Always Be True
Every well-designed data structure maintains invariants: properties that must hold before and after every operation. A bug in a structure is almost always a broken invariant — an operation that left the structure in a state its rules forbid. Making invariants explicit is one of the most powerful debugging tools there is.
Each structure has characteristic invariants:
- A binary search tree: for every node, left-subtree values < node < right-subtree values.
- A heap: every parent stands in the correct order relation to its children.
- A doubly linked list: for adjacent nodes,
a.next.prev == a— the back-pointer of your successor points back to you. - A hash table: every key resides in the bucket its hash function selects.
To debug, write a checker — a function that walks the structure and verifies its invariant holds — and run it after each operation while hunting a bug. The moment the checker fails, you have caught the operation that corrupted the structure, at the exact point of corruption, instead of discovering the damage far downstream when a later read returns nonsense.
This is the structural version of "fail fast": rather than trusting that operations preserve the invariant, you verify it. Invariant checkers are cheap to write, catch whole classes of subtle bugs (a mis-linked pointer, an unbalanced subtree, a mis-hashed key), and double as executable documentation of what the structure guarantees.
Common pitfall: debugging a data structure by only inspecting the output of operations, rather than checking the invariant directly. A corrupted structure may return correct-looking results for a while before failing bizarrely much later. Checking the invariant after each operation localizes the bug to the exact operation that broke it.