= Solution
Append nonzero entries in increasing index order; repeatedly calling `setElement` would unnecessarily rescan earlier entries and could make construction quadratic.
``
def makeVector(elems: Array[Double]): Node = {
require(elems != null)
val head = makeZeroVector(elems.length)
var tail = head
var i = 0
while (i < elems.length) {
val v = elems(i)
require(!v.isNaN && !v.isInfinity)
if (v != 0.0) {
val fresh = new Node(v, i, tail, head)
tail.next = fresh
head.prev = fresh
tail = fresh
}
i += 1
}
head
}
``
The <loop invariant> says that the list represents exactly the nonzero entries of the processed input prefix, in their original coordinate order, and `tail` is the final node or the header when none exist. Every append preserves the cycle and ordering. At exit, all input coordinates have their intended values. \b[Construction takes $O(n)$ time and $O(k)$ data nodes], where $n$ is the <array> length and $k$ the number of nonzeros, plus one header. The input <array> is unchanged.
Back to article page
