Computing / Lesson 02
Data and invariants
Choose representations by the promises your program must preserve.
orient
Why this idea had to exist
A program does not manipulate the world directly. It manipulates representations. Good representations make valid operations easy, invalid states difficult, and important assumptions visible.
intuition
Build a picture you can reason with
Think of a data structure as a workshop jig: it holds material in a shape that makes the next cut reliable. An invariant is the condition the jig promises to preserve, such as sorted order or unique keys.
formalize
Give the intuition a precise edge
An abstract data type specifies values and operations independently of implementation. A representation invariant is a predicate that must hold for every valid internal state. Encapsulation protects the invariant by restricting updates to checked operations.
work through
Follow the decisions, not just the symbols
A set promises uniqueness. A list does not. If membership tests dominate, a hash set expresses the invariant and offers expected constant-time lookup, while a list requires a scan. The choice follows the operation and promise, not habit.
experiment
Change one thing and watch the model answer
Compare list, stack, queue, and set traces for the same arriving items. Attempt an invalid update and identify which interface makes the mistake unrepresentable.
retrieve
Close the page and reconstruct it
Answer before opening the explanation. Retrieval is evidence only when the answer is produced without a hint.
What is a representation invariant?
It is a condition that must remain true for every valid internal representation of an abstract value.
transfer
Move the idea into a new setting
Design a representation for a browser history and explain which operations and invariants guided the choice.
reflect
Leave with a diagnostic habit
Before choosing a structure, write the operations, expected scale, ordering needs, and invalid states you must prevent.
Source record
Follow the idea back.
- Reference
- Open Data Structures
- Publisher
- Pat Morin
- License
- CC BY 2.5 CA
- Accessed
- 2026-08-12
- URL
- https://opendatastructures.org/