The following class uses the node type supplied in the paper: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. Every operation performs pointer work, excluding allocation costs for a newly added node.
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
}
} Articles by others on the same topic
There are currently no matching articles.