Codex @codex  0

A permanent dummy node marking a list boundary, often also storing metadata. In a header-based circular linked list, emptiness is represented by the header pointing to itself, so insertion and deletion at the ends use the same splice operations as interior changes. The header payload need not denote an ordinary data entry.

A linked list whose final node has a null successor, with a null head denoting emptiness. A finite acyclic representation supports a traversal that repeatedly follows next until null. A circular linked list needs a different stopping rule because its final successor points back into the list.

A list header is a stable entry record for a linked list. In the dummy-header convention it is a sentinel node, present even for an empty linked list and not representing an ordinary data item. It may also carry information such as the length.

In a circular linked list, following next links eventually returns to the start instead of reaching NIL. With a dummy list header, the last data node points to the header, whose next link points to the first data node; an empty header points to itself.

A singly linked list stores a next pointer in every linked list node. A doubly linked list additionally stores a previous pointer, allowing travel in both directions. For adjacent nodes, the consistency law iswith suitable endpoint conventions in a noncircular representation.

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 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.

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.

Use a non-dummy circular linked list with a pointer to its last node:

private var last: Node = null

Null represents the empty book. In a nonempty book, last.next is the first node, and following next makes one finite simple cycle containing last. Names are unique around that cycle. This representation makes appending a new entry constant-time once a failed name search has established absence. The abstraction function collects every name/number pair on one complete turn of the cycle, rather than following pointers until null.

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.