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