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 iswith suitable endpoint conventions in a noncircular representation.
A dummy list header makes insertion or deletion at the front resemble insertion or deletion in the middle: there is always a predecessor record to update. In a circular doubly linked list, it also supplies a stable end position, handles the empty case uniformly, and avoids changing an external head pointer every time the first data node changes.
Its disadvantage is the extra record and associated storage and initialization work; traversal must also distinguish the sentinel node from real data. Thus
A doubly linked list supports backward traversal and removal of a known linked list node in constant time, because that node supplies its own predecessor. In a singly linked list, removing a known node generally requires finding its predecessor by a forward scan unless the caller already supplies it. Inserting before a known node has the same advantage.
The cost is another pointer per node, more link assignments on every update, and a stronger consistency invariant to maintain. HenceThis does not make locating an arbitrary data value faster: a search still takes linear time in the worst case.
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.