Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / b

Use an immutable index and mutable value and links:For the sparse linked vector representation, a header 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.