Abstract data types and representation invariants

Prerequisites: Functions, lists, mutation, and basic asymptotic cost.

Learning objectives

• Specify operations independently of representation.
• State a representation invariant and abstraction function.
• Compare implementations using both semantics and cost.

An interface promises behavior

An abstract data type defines values and permitted operations without requiring one internal representation. A queue holds a sequence and supports adding at the back, removing from the front, and checking emptiness. Its defining property is first-in, first-out behavior. A list, linked nodes, or a circular array can implement that same abstraction with different costs.

A representation invariant states which internal states are valid. An abstraction function maps each valid representation to the abstract value clients observe. For a queue represented by a Python list data and an integer head, the invariant is 0 <= head <= len(data), and the abstract queue is data[head:]. Values before head have already been removed.

Enqueue appends to data. Dequeue first rejects an empty queue when head equals len(data); otherwise it returns data[head] and increments head. The operations preserve the invariant and implement the promised sequence changes. Incrementing head avoids shifting every remaining element on every removal, but old elements stay referenced until storage is reclaimed.

Performance needs an accounting argument

A two-stack queue offers another representation. New values enter an incoming stack. To remove a value, pop from an outgoing stack; when outgoing is empty, move every incoming value to outgoing, reversing their order. Suppose incoming receives A, B, C. Transferring yields outgoing with C at the bottom and A at the top, so A is removed first.

One removal can cost linear time when it triggers a large transfer. Across a sequence of operations, however, each item enters incoming once, transfers once, and leaves outgoing once. The total number of stack operations is linear in the number of queue operations. This is an amortized bound, not a promise that every operation is fast and not a claim about a random workload.

Encapsulation supports the proof

If callers can directly edit head or remove arbitrary entries from data, the invariant can fail without any queue operation being called. Keep representation details behind a small interface. Tests can run the same operation sequences against multiple implementations and compare observable results to a simple reference model.

Error behavior belongs to the interface too. An empty removal might raise a specific exception or return an explicitly tagged missing value. Returning None is ambiguous if None is a valid queue element. A good abstraction specifies successful results, invalid operations, mutation effects, and any cost guarantees that clients are allowed to depend on. Internal optimizations remain safe only while those promises continue to hold.

Practice problem

Specify a bounded stack with capacity three. Define push, pop, peek, and length, including behavior on overflow and underflow. Choose a list representation and state its invariant and abstraction function. Walk through push(A), push(B), pop(), push(C), peek(), and give the returned values and final abstract stack. Then explain why a method returning the internal list makes the capacity guarantee unenforceable, and propose a safe inspection operation.

Worked solution

The abstract value is an ordered sequence of at most three items, with its last item at the top. The representation invariant is 0 <= len(items) <= 3, and the abstraction function interprets items in that order. Push appends only below capacity; pop removes and returns the final element only when nonempty; peek returns it without removal. Overflow and underflow raise documented exceptions before mutation. The trace returns B from pop and C from peek, leaving [A,C]. Returning items lets a caller append arbitrary values and exceed capacity outside the checked interface. Return an immutable tuple snapshot or a copied sequence instead, while specifying whether nested element objects remain shared. Test both failures leave the stack unchanged.

Check your understanding

What does an amortized constant-time queue operation guarantee?

• Every operation finishes in the same time.
• The total work over an operation sequence is linear in its length under the stated model.
• Its expected time is constant for random inputs only.

Explanation

Amortized analysis distributes occasional expensive work across a sequence; it does not require a probability distribution.

Why is a representation invariant useful?

• It describes which internal states operations must preserve.
• It prevents callers from ever passing invalid inputs without checks.
• It requires every implementation to use the same memory layout.

Explanation

The invariant defines valid representations and supplies a proof obligation for constructors and operations.

Primary reading

• Structure and Interpretation of Computer Programs: University of California, Berkeley

Open the study and save your work →