= Solution
Use a <doubly linked list>, store both physical endpoints and its length, and maintain a flag for <lazy reversal of a doubly linked list>. This makes endpoint insertion and reversal constant time. Finding an arbitrary indexed element takes a traversal from whichever physical endpoint is nearer.
``
class LLBuffer extends ReversableBuffer {
private class Node(val value: Int) {
var prev: Node = null
var next: Node = null
}
private var first: Node = null
private var last: Node = null
private var size = 0
private var backwards = false
// Methods from (ii) go here.
}
``
Define $F$ to be the <sequence> of values obtained by starting at `first` and repeatedly following `next` until null. The <representation invariant> says that `size` is nonnegative; `size == 0` holds exactly when both endpoints are null; otherwise there are exactly `size` distinct reachable <linked list nodes>, the final one is `last`, `first.prev == null`, `last.next == null`, and all neighboring links are reciprocal. These conditions make $F$ finite and the physical <linked list> acyclic. The <abstraction function> is
$$
\boxed{s=\begin{cases}F&\text{if }\neg backwards,\\\operatorname{reverse}(F)&\text{if }backwards.\end{cases}}
$$
The flag does not change the <representation invariant>. An empty physical <linked list> represents the empty <sequence> for either flag value. No client receives a <linked list node> reference, so clients cannot invalidate its links.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/imperative-programming-2013-buffer-reversal.png]
{title=Physical <doubly linked list> order and logical <sequence> order under <lazy reversal of a doubly linked list>}
Back to article page
