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.
Articles by others on the same topic
There are currently no matching articles.