= Solution
The following class uses the node type supplied in the paper:
``
class DoublyLinkedDoubleEndedQueue extends DoubleEndedQueue {
private var first: Node = null
private var last: Node = null
def isEmpty: Boolean = first == null
def addLeft(x: Int): Unit = {
val node = new Node(x, null, first)
if (first == null) last = node
else first.prev = node
first = node
}
def addRight(x: Int): Unit = {
val node = new Node(x, last, null)
if (last == null) first = node
else last.next = node
last = node
}
def getLeft(): Int = {
require(!isEmpty)
val old = first
first = old.next
if (first == null) last = null
else first.prev = null
old.next = null
old.datum
}
def getRight(): Int = {
require(!isEmpty)
val old = last
last = old.prev
if (last == null) first = null
else last.next = null
old.prev = null
old.datum
}
}
``
An insertion connects a fresh endpoint to the old chain and updates its <reciprocal> link. A removal reconnects the exposed endpoint to null; the singleton case also clears the opposite endpoint. The remaining chain therefore satisfies the same <representation invariant> and has exactly the abstract <sequence> required by the specification. \b[Every operation performs $O(1)$ pointer work], excluding allocation costs for a newly added node.
Back to article page
