= Solution
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 is
$$
\boxed{u.next=v\quad\Longleftrightarrow\quad v.prev=u,}
$$
with suitable endpoint conventions in a noncircular representation.
Back to article page
