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.Define to be the sequence of values obtained by starting at
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.
}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 finite and the physical linked list acyclic. The abstraction function isThe 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.
Physical doubly linked list order and logical sequence order under lazy reversal of a doubly linked list
. Details. 
Place these methods inside the In the forward traversal, the loop invariant is that
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 }q is physical node , with ; its loop variant is . In the backward traversal, q is physical node , with ; its loop variant is . Thus both locate physical index , which is exactly logical index 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 to its list reversal without moving any linked list nodes. ConsequentlyThese are worst-case time complexity bounds in the constant-cost pointer model; total storage is and each operation uses constant auxiliary space.
Articles by others on the same topic
There are currently no matching articles.