How Does a Sentinel Node Offer Benefits Over Null

How does a sentinel node offer benefits over NULL?

There's no advantage with sentinels if you're just doing simple iteration and not looking at the data in the elements.

However, there's some real gain when using it for "find" type algorithms. For example, imagine a linked list list std::list where you want to find a specific value x.

What you would do without sentinels is:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

But with sentinels (of course, end actually has to be a real node for this...):

iterator i=list.begin();
*list.end() = x;

while (*i != x) // just this branch!
  ++i;

return i;

You see there's no need for the additional branch to test for the end of the list - the value is always guaranteed to be there, so you will automatically return end() if x cannot be found in your "valid" elements.

For another cool and actually useful application of sentinels, see "intro-sort", which is the sorting algorithm that's used in most std::sort implementations. It has a cool variant of the partition algorithm that uses sentinels to remove a few branches.

How to properly use sentinel nodes?

Answer 1

Yes this is a valid position for the sentinelnode to take. head and tail can point to the actual beginning and end of the data. But your add and delete functions will need to be aware of the aberrations caused at the list boundaries by virtue of the sentinel node

Answer 2

Yes this is a valid search strategy and is infact called the Elephant in Cairo technique

Answer 3

Yes, the purpose of the sentinel node is to let you know that it is the sentinel node. You could just maintain a constant pointer (or whatever your lang of choice supports) to this sentinel node to check if you are at the sentinel node or just stick a flag in the node.

Sentinel approach with Doubly Linked List

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.

Dummy nodes in linked lists

Look, there is a significant difference between a "Dummy" node and a "Sentinel" node.

Dummy nodes "Sometimes get used as first and last nodes in the list".

When you initiate a linked list a common approach is to create a dummy node, and interestingly it's the last node at the same time.

Obviously not always first or last nodes of a LL are dummy records.

Please note that you can use a dummy node without any data and a null pointer as a sentinel that shows the last node in the LL.

You may wonder is it possible to have a LL without any dummy node?

Answer: Yes. You can hold initialization of your LL until the insertion of the first data entry, and to that point just have null pointer as the LL, and after insertion(s) hold a pointer to the head node and always use a null pointer as "Next" node of the tail node.

I refer you to this page for more insight.

doubly linked list empty situation

There are two common ways to store a double linked-list:

Let head and tail refer to actual nodes in the tree.

head variable       tail variable
  |                   |
  V                   V
first -> second -> third -> null

In this case, you are correct - head will be null.

Let head and tail be special nodes (called "sentinel nodes", as pointed out in the other answer) which don't actually contain any data and point to the first and last nodes in the list through next and prev respectively.
```
head variable                       tail variable
  |                                   |
  V                                   V
head -> first -> second -> third -> tail -> null
node                                node
```
In this case, header.next == tail will mean the list is empty.
One might use this approach instead of the above one to simplify the implementation a bit and make the code a bit faster - there's no need to make special provision for removing or inserting the first or last nodes.

need for header node

Having sentinel nodes prevents you from having to handle certain edge cases.

The biggest is the null check: You always know that there will be a node at the top of the list that you can insert nodes after, so you don't have to deal with checking if head is null. (also it helps having a tail node for similar reasons)

Consider the two cases:

With a head and a tail node:

addNewDataAtHead( data ):
    newNode = new Node(data);
    newNode.next = head.next;
    newNode.prev = head;
    head.next.prev = newNode;
    head.next = newNode;

Without:

addNewDataAtHead( data ):
    newNode = new Node(data);
    if (head == null):
        head = newNode;
    newNode.next = head;
    head.prev = newNode;
    head =  newNode;

the intent of the first one is a lot clearer because it is like inserting anywhere else. The second case requires you to check for a special circumstance.