= Solution
An already-zero entry needs no new <linked list node>:
``
def zeroElement(vector: Node, index: Int): Unit = {
require(vector != null)
require(0 <= index && index < vector.index)
var p = vector.next
while ((p ne vector) && p.index < index) p = p.next
if ((p ne vector) && p.index == index) {
val left = p.prev
val right = p.next
left.next = right
right.prev = left
}
}
``
The full input <representation invariant> is a <precondition>. The search has the same <loop invariant> and <loop variant> as in part (d). At exit, either `p` is the only stored entry with that index or none exists. In the first case, bypassing it in both directions removes exactly that coordinate and preserves the order of all remaining entries. This also works when its two neighbors are the same <list header>, leaving a self-linked empty structure. The header itself is never removed. \b[The requested coordinate is zero and all others are unchanged], in $O(k+1)$ <time complexity>.
Back to article page
