A list header is a permanent dummy linked list node, distinct from the ordinary elements. It gives a stable reference to the linked list and can store metadata such as its length. In a circular linked list, following successor links eventually returns to the starting point; with a list header, the last ordinary element links to the header, and the empty structure has the header linked to itself.
A singly linked list stores a successor reference per linked list node. A doubly linked list additionally stores a predecessor reference. The latter supports traversal in both directions and deletion of a known linked list node in constant time, without first searching for its predecessor. It costs another reference per linked list node and additional updates whose mutual consistency must be maintained. A list header makes insertion and deletion at an endpoint use the same local splicing rules as an interior change; the empty case does not require replacing an external head reference.
Use an immutable index and mutable value and links:For the sparse linked vector representation, a header
class Node(var value: Double, val index: Int,
var prev: Node = null, var next: Node = null)h has h.index >= 0, records that vector's dimension, and lies on a finite circular linked list. Every ordinary linked list node has an index in [0,h.index), a nonzero finite value, and a unique index; indices increase strictly from h.next to h.prev. For every reachable linked list node, including h, p.next.prev eq p and p.prev.next eq p. The abstraction function fills unspecified coordinates with zero. The header's value has no meaning. Finite real coordinates are assumed throughout; infinities and NaN are not ordinary real number coordinates for a mathematical inner product.Only the list header is present:
h.next eq h, h.prev eq h, and h.index is the dimension. This represents every coordinate as zero, including the unique zero-dimensional vector when the dimension is zero. The header is never treated as a nonzero coordinate.The runtime precondition check rules out negative dimensions:Both links point to the fresh list header, so all reciprocal-link conditions hold and there are no ordinary entries to violate ordering or nonzero-value requirements. The abstraction function therefore yields the zero vector of dimension
def makeZeroVector(size: Int): Node = {
require(size >= 0)
val h = new Node(0.0, size)
h.prev = h
h.next = h
h
}size. Construction uses constant time and constant space.Assume The search loop invariant says that the structure is unchanged and every ordinary linked list node passed has index smaller than
vector already satisfies the full representation invariant in part (b). Check the local bounds and value preconditions, then find the first index not smaller than the requested one:def setElement(vector: Node, value: Double, index: Int): Unit = {
require(vector != null)
require(0 <= index && index < vector.index)
require(value != 0.0 && !java.lang.Double.isNaN(value) &&
!java.lang.Double.isInfinite(value))
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 left = p.prev
val fresh = new Node(value, index, left, p)
left.next = fresh
p.prev = fresh
}
}index; p is the next candidate. The number of unpassed ordinary entries is a loop variant. The short-circuit evaluation prevents testing the header index as an ordinary entry. If an equal index exists, changing only its nonzero value preserves the representation invariant. Otherwise left and p delimit the unique insertion position: initializing both new links before redirecting their neighbors preserves reciprocal links and strict index order. Exactly the requested coordinate changes. With stored entries, the search costs and the splice costs constant time; checking the whole input structure is a caller obligation, rather than an unmentioned scan inside each call.An already-zero entry needs no new linked list node: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
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
}
}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. The requested coordinate is zero and all others are unchanged, in time complexity.Append entries in increasing index order, keeping a tail reference so that repeated searches do not make construction quadratic:The loop invariant is , a valid circular representation of the nonzero entries in
def makeVector(elems: Array[Double]): Node = {
require(elems != null)
val h = makeZeroVector(elems.length)
var tail = h
var i = 0
while (i < elems.length) {
val v = elems(i)
require(!java.lang.Double.isNaN(v) &&
!java.lang.Double.isInfinite(v))
if (v != 0.0) {
val fresh = new Node(v, i, tail, h)
tail.next = fresh
h.prev = fresh
tail = fresh
}
i += 1
}
h
}elems[0..i), a fixed header dimension elems.length, and tail eq h.prev. The next nonzero index is greater than every stored index; appending the fresh linked list node preserves reciprocal links, including tail.next eq h. The loop variant is elems.length-i. At exit the abstraction function yields exactly the input array as a vector. There is one pass and constant work per entry: time complexity for , including emptiness, and output storage for nonzero entries. Both signs of floating-point zero are represented by absence.Use the sorted sparse dot product merge, processing a coordinate only when it appears in both supports of a vector:Both structures must satisfy the representation invariant; equal dimension is checked explicitly. The loop invariant says that
def dotProduct(vec1: Node, vec2: Node): Double = {
require(vec1 != null && vec2 != null)
require(vec1.index == vec2.index)
var p = vec1.next
var q = vec2.next
var result = 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 {
result += p.value * q.value
p = p.next
q = q.next
}
}
result
}result contains exactly the products for all matching indices already passed, and that every skipped unequal index has zero in the other vector. The latter follows from sortedness: if p.index < q.index, that index cannot appear at q or later, and all earlier entries of the other vector have already been settled. Equality contributes its product exactly once. The total number of remaining ordinary entries is a loop variant; every iteration advances at least one cursor. Once either cursor reaches its header, all remaining entries pair with zeros. Thus the exact-arithmetic result is . With stored entries, time complexity is and auxiliary space is constant. Floating-point products and additions may round or overflow even when input coordinates are finite; no exact real-arithmetic accuracy claim is made for Double. Articles by others on the same topic
There are currently no matching articles.