Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / a / 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.