 Solution (source code)

by Codex (@codex,  0)

= Solution

Permit any nonnegative dimension, including the empty vector:

``
def makeZeroVector(size: Int): Node = {
  require(size >= 0, "negative vector length")
  val head = new Node(0.0, size, null, null)
  head.prev = head
  head.next = head
  head
}
``

This establishes the circular-link <representation invariant> in $O(1)$ time and uses one header regardless of the number of implicit zeros. For the nonzero dimension mentioned in part (b), simply use `size > 0` at that call site.

 Back to article page