= Sparse linked vector representation
Represent a finite <sparse vector> by a sorted <doubly linked list> of its nonzero coordinates. A <list header> stores the dimension; every ordinary <linked list node> stores a distinct valid coordinate index, its nonzero value, and predecessor and successor references. In a <circular linked list>, the endpoints connect to the header, and an all-zero <vector> has the header linked to itself in both directions. The <representation invariant> requires strictly increasing ordinary indices, valid bounds and mutually consistent forward and backward links. The <abstraction function> assigns zero to every coordinate absent from the list. The header is metadata, never an ordinary coordinate.
For example, $(0,3,0,0,-2,0,0,5,0)$ has dimension nine and only three stored coordinates. The header's index field can store nine even though nine is not a valid coordinate index. Keeping the header distinct is therefore essential when searching for or removing entries.
\Image[/sparse-linked-vector.png]
{title=A circular <sparse linked vector representation> stores only nonzero coordinates}
Back to article page
