Sentinel approach with Doubly Linked List

Question

I am going through the doubly linked list in Java, I am reading about Sentinels in the doubly linked list from Book. Which states that

In order to avoid some special cases when operating near the boundaries of a doubly-linked list, it helps to add special nodes at both ends of the list: a header node at the beginning of the list, and a trailer node at the end of the list. These “dummy” nodes are known as sentinels (or guards), and they do not store elements of the primary sequence

What are those special cases? Why we need Sentinels approach? Is it compulsory? If we use the normal approach (without sentinels) for doubly linked list wouldnt that save the memory of these extra nodes? When making double linked list with circularly approach in that way we have to remove sentinels?

SSP SSP · Accepted Answer · 2019-09-22T14:13:13

The Wikipedia notes briefly mention using a sentinel node to simplify the implementation of linked lists.

A sentinel node is a dummy node that goes at the front of a list.

In a doubly-linked list, the sentinel node points to the first and last elements of the list. We no longer need to keep separate pointers for the head and tail of the list, like we had to do with singly-linked lists.

We also do not have to worry about updating the head and tail pointers, since as we shall see, this happens automatically if we insert after a sentinel node, hence prepending an item to the list, or insert before a sentinel node, hence appending an item to the list.

We could eliminate the container object that we used for singly linked lists, since the sentinel node can keep track of both the first and last elements in the list. If we did so, then we would return a pointer to the sentinel node to the user.

However, data structures are generally designed with a container object that mediates the communication between the user of the data structure and the implementation of the data structure, so we will retain the container object.

An answer by @6502 on How does a sentinel node offer benefits over NULL? is very helpful.

The following is the code for node deletion in a doubly-linked list of nodes where NULL is used to mark the end of the list and where two pointers first and last are used to hold the address of first and last node:

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

and this is the same code where instead there is a special dummy node to mark the end of the list and where the address of first node in the list is stored in the next field of the special node and where the last node in the list is stored in the prev field of the special dummy node:

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

The same kind of simplification is also present for node insertion; for example to insert node n before node x (having x == NULL or x == &dummy meaning insertion in last position) the code would be:

// Using NULL and pointers for first and last

n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

and

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

As you can see the dummy node approach removed for a doubly-linked list all special cases and all conditionals.

Sentinel approach with Doubly Linked List

1 Answers