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