Catching Broken Rules
A broken invariant occurs when an operation leaves a data structure in a state its rules forbid. Make invariants explicit to catch bugs instantly.
| Structure | Core Invariant |
|---|---|
| Binary Search Tree | Left child < node < right child |
| Heap | Parent stands in correct order relation |
| Doubly Linked List | a.next.prev == a always holds |
| Hash Table | Every key resides in its hashed bucket |
Write a checker, a function that walks and verifies the structure after each operation. This applies the "fail fast" principle, catching corruption at the exact moment it happens.
The Debugging Secret
A checker function stops you from hunting bugs downstream when reads finally return nonsense. Invariant checkers are cheap to write and double as executable documentation.
Common pitfall: Debugging a data structure by inspecting only the output of operations. A corrupted structure often returns correct-looking results for a while before failing bizarrely.
Always check the invariant directly after each operation to instantly localize the bug to the exact code that broke your structure.