A list header is a permanent dummy node that represents the list boundary rather than a data entry. A circular linked list links the last node back to the first or to the header. A singly linked list stores only a successor; a doubly linked list stores both successor and predecessor references.
A header provides a stable object even for an empty list, makes insertions and deletions at the ends resemble interior operations, and can hold metadata such as the vector length in this question. In a circular header-based representation, the empty list is the header linked to itself.
A doubly linked list permits backward traversal and constant-time unlinking of a known node without searching for its predecessor. It uses an extra reference per node and requires more pointer updates and a stronger consistency invariant. Finding a node by an arbitrary index can still require a linear scan: bidirectional links alone do not provide random access.
Within the sparse-vector implementation, use:
class Node(var value: Double, val index: Int,
var prev: Node, var next: Node)The header's
index is the fixed vector dimension, so it need not change after construction. For a data node it is the coordinate index. The representation invariant requires a finite simple cycle through the header, reciprocal predecessor/successor links, strictly increasing indices in the forward data-node traversal, indices in , and a nonzero value at every data node. The header's value is ignored. The abstraction function assigns stored values to their indices and zero to all missing coordinates.The numerical code below takes entries to be finite
Double values. Excluding NaN and infinities makes the relationship to a real sparse vector explicit; arithmetic results still follow ordinary floating-point arithmetic.A single header with
index == n, and with both next and prev pointing to itself, represents the entirely zero vector. It has no data nodes. The ignored header value can be 0.0. The vector dimension remains , even though the number of stored nonzero entries is zero.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 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.Assume
vector is a well-formed header satisfying the sparse-vector representation invariant; checking that whole invariant on each operation would require traversing the list. Check the requested bounds and value, then find the first stored coordinate at or after the target.def setElement(vector: Node, value: Double, index: Int): Unit = {
require(vector != null)
require(0 <= index && index < vector.index)
require(value != 0.0 && !value.isNaN && !value.isInfinity)
var p = vector.next
while ((p ne vector) && p.index < index) p = p.next
if ((p ne vector) && p.index == index) p.value = value
else {
val fresh = new Node(value, index, p.prev, p)
p.prev.next = fresh
p.prev = fresh
}
}The scan excludes all smaller stored indices. An existing coordinate is updated without duplicating it; otherwise the new node is spliced immediately before
p, with both directions repaired. The header also serves as the insertion boundary after the final data node. Strict index order and nonzero storage are preserved. The cost is search and pointer work, where is the number of stored entries.An absent coordinate already has value zero. If found, unlink its node in both directions:
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) {
p.prev.next = p.next
p.next.prev = p.prev
}
}Identity comparison with the header prevents treating its dimension field as a data index. The splice preserves reciprocal links even when removing the only data node: the two header links then point to the header again. All other coordinates are unchanged, and an absent coordinate causes no mutation. The running time is , with constant work after the node is located.
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. Construction takes time and data nodes, where is the array length and the number of nonzeros, plus one header. The input array is unchanged.Use sparse dot product by merging indices: only equal coordinate indices can contribute, so merge the two increasing index streams:
def dotProduct(vec1: Node, vec2: Node): Double = {
require(vec1 != null && vec2 != null)
require(vec1.index == vec2.index, "dimension mismatch")
var p = vec1.next
var q = vec2.next
var answer = 0.0
while ((p ne vec1) && (q ne vec2)) {
if (p.index < q.index) p = p.next
else if (q.index < p.index) q = q.next
else {
answer += p.value * q.value
p = p.next
q = q.next
}
}
answer
}The loop invariant states that the accumulator contains all common-coordinate products already passed, while no unprocessed smaller coordinate can acquire a future partner. If one current index is smaller, the other list has no remaining entry at that index, so its product is zero. Equal indices add their product and advance both. Once either list ends, all remaining coordinates of the other have zero partners.
Thus the code computes the dot product in coordinate order, subject to floating-point rounding, using time and constant auxiliary storage. It does not scan implicit zeros or alter either vector, and it also handles both arguments referring to the same header.
Articles by others on the same topic
There are currently no matching articles.