= Solution
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.
Back to article page
