= Solution
Place these methods inside the `LLBuffer` class. The two private insertion methods operate on physical endpoints; the public methods interpret logical endpoints using the reversal flag.
``
private def addFirst(x: Int): Unit = {
val q = new Node(x)
q.next = first
if (first == null) last = q else first.prev = q
first = q
size += 1
}
private def addLast(x: Int): Unit = {
val q = new Node(x)
q.prev = last
if (last == null) first = q else last.next = q
last = q
size += 1
}
def append(x: Int): Unit = {
if (backwards) addFirst(x) else addLast(x)
}
def prepend(x: Int): Unit = {
if (backwards) addLast(x) else addFirst(x)
}
def get(i: Int): Int = {
require(0 <= i && i < size)
val j = if (backwards) size - 1 - i else i
var q: Node = null
if (j <= size - 1 - j) {
q = first
var k = 0
while (k < j) { q = q.next; k += 1 }
} else {
q = last
var k = size - 1
while (k > j) { q = q.prev; k -= 1 }
}
val x = q.value
if (q.prev == null) first = q.next else q.prev.next = q.next
if (q.next == null) last = q.prev else q.next.prev = q.prev
q.prev = null
q.next = null
size -= 1
x
}
def rev: Unit = { backwards = !backwards }
``
In the forward traversal, the <loop invariant> is that `q` is physical node $k$, with $0\leq k\leq j$; its <loop variant> is $j-k$. In the backward traversal, `q` is physical node $k$, with $j\leq k<size$; its <loop variant> is $k-j$. Thus both locate physical index $j$, which is exactly logical index $i$ under the <abstraction function>.
Deletion bypasses the chosen <linked list node> in both directions. Deleting the first or last <linked list node> updates the corresponding endpoint; deleting the only <linked list node> sets both endpoints to null. The surviving values keep their physical relative order, so the <abstraction function> gives precisely the required logical deletion. Each insertion preserves reciprocal links and adds its value at the physical end corresponding to the required logical end. Toggling the flag changes $s$ to its <list reversal> without moving any <linked list nodes>. Consequently
$$
\boxed{append,prepend,rev:O(1),\qquad get(i):O(1+\min(i,size_0-1-i)).}
$$
These are worst-case <time complexity> bounds in the constant-cost pointer model; total storage is $O(size)$ and each operation uses constant <auxiliary space>.
Back to article page
