c++ - How does a sentinel node offer benefits over NULL?

Question

On the Sentinel Node wikipedia page it says that the benefits of a sentinel node over NULL are :

• Increased speed of operations
• Reduced algorithmic code size
• Increased data structure robustness (arguably).

I don't really understand how the checks against a sentinel node would be faster (or how to properly implement them in a linked list or tree), so I suppose this is more of a two part question:

1. What causes the sentinel node to be a better design than NULL?
2. How would you implement a sentinel node in (for example) a list?

Answer 1

I think that a little code example would be a better explanation than a theoretic discussion.

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.

The following picture represents the two approaches for the same list in memory...