Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / b

Keep private references first and last, both initially null. A nonempty representation is a finite acyclic chain from first through next to last. Its representation invariant requires first.prev == null, last.next == null, and reciprocal links between every adjacent pair. The nodes reached by following prev from last are exactly the same nodes in reverse order. No internal node reference is exposed to clients.

The abstraction function reads the datum values along the forward chain, giving the abstract sequence from left to right. The empty representation has both endpoint references null; the invariant requires that either both are null or both are nonnull. A single node has both links null. Updating both endpoint references when removing that last node is therefore essential.