= Solution
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. \b[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.
Back to article page
