= Solution
Choose a circular <doubly linked list> with a permanent dummy <list header>. For a concrete <Oberon> definition take `data = INTEGER`; the same link operations work with any chosen data <data type>:
``
TYPE data = INTEGER;
pointerToNode = POINTER TO node;
node = RECORD
value : data;
prev, next : pointerToNode
END;
PROCEDURE NewList() : pointerToNode;
VAR h : pointerToNode;
BEGIN
NEW(h);
h.prev := h;
h.next := h;
RETURN h
END NewList;
PROCEDURE Insert(v : data; n : pointerToNode);
VAR t, p : pointerToNode;
BEGIN
p := n.prev;
NEW(t);
t.value := v;
t.prev := p;
t.next := n;
p.next := t;
n.prev := t
END Insert;
PROCEDURE Delete(n : pointerToNode);
VAR p, q : pointerToNode;
BEGIN
p := n.prev;
q := n.next;
p.next := q;
q.prev := p;
n.prev := NIL;
n.next := NIL
END Delete;
``
The representation invariant is that the live nodes and header form one finite circular chain, with every neighboring next/previous pair mutually consistent. `Insert` replaces the link $p\leftrightarrow n$ by $p\leftrightarrow t\leftrightarrow n$. `Delete` replaces $p\leftrightarrow n\leftrightarrow q$ by $p\leftrightarrow q$. All other links remain unchanged. These arguments also cover insertion into an empty <linked list> and deletion of its sole data node, where the neighboring positions can refer to the same header.
`Insert` requires a live node `n` belonging to this representation and successful allocation. It may be called with `n` equal to the header, meaning append just before the end. `Delete` requires a live \i[data] node and must never be called on the header, on `NIL`, or on a node already deleted or belonging to an incompatible representation. The signature alone cannot enforce those <preconditions>. The detached node is left for <garbage collection>; external references must no longer treat it as a member of the <linked list>. Neither update contains a loop. Apart from allocation and memory management, the link work is
$$
\boxed{O(1)\text{ for insertion before a known node and deletion of a known data node}.}
$$
Back to article page
