How does a sentinel node offer benefits over NULL?

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 (ar开发者_Go百科guably).

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?

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...

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.

The answer to your question (1) is in the last sentence of the linked Wikipedia entry: "As nodes that would normally link to NULL now link to "nil" (including nil itself), it removes the need for an expensive branch operation to check for NULL."

Normally you need to test a node for NULL before accessing it. If instead you have a valid nil node then you don't need to do this first test, saving a comparison and a conditional branch, which can otherwise be expensive on modern superscalar CPUs when the branch is mis-predicted.

I will try to answer in the context of the standard template library:

1) In a call to "next()", NULL does not necessarily indicate end-of-list. What if a memory error occurred? Returning a sentinel node, is a definitive way to indicate that end-of-list had occurred, and not some other outcome. In other words, NULL could indicate a variety of things, not just end-of-list.

2) This is just one possible method: when you create your list, create a private node that is not shared outside of the class (called "lastNode" for instance). Upon detecting that you have iterated to the end of the list, have "next()" return a reference to "lastNode". Also have a method called "end()" return a reference to "lastNode". Lastly, depending on how you implement your class, you might need to override the comparison operator for this to work properly.

Example:

class MyNode{

};

class MyList{

public:
    MyList () : lastNode();

    MyNode * next(){

       if (isLastNode) return &lastNode;
       else return //whatever comes next
    }

    MyNode * end() {

       return &lastNode;
    }

    //comparison operator
    friend bool operator == (MyNode &n1, MyNode &n2){

        return (&n1 == &n2); //check that both operands point to same memory
    }


private:
    MyNode lastNode;
};


int main(){

  MyList list;
  MyNode * node = list.next();

  while ( node != list.end() ){ 

     //do stuff!

     node = list.next();
  }

  return 0; 
}

Let's first set aside sentinel. In terms of code complexity, for the answer in ltjax, he provides us with the code

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

The code can be better formed as:

auto iter = list.begin();
while(iter != list.end() && *iter != x)
    ++iter;
return iter;

Because of the cluttered(grouped) loop termination condition, one can easily see the loop termination condition without remembering all loop termination condition when going through the loop body to reason about correctness, and type less. Be aware of the bool circuit here though.

The point is that the sentinel used in here is not for reduced code complexity, but it helps us to reduce index checking in each loop. For linear search, we begin with checking if the index is with valid range, and if in, then check if the value is what we want, without the use of sentinel. But with sentinel which is placed at the end with desired value, we can dispense with index boundary checking, but only check the value, since the loop is guaranteed to terminate. This belongs to sentinel controlled loop: repeat until the desired value is seen.

Recommend reading: Introduction to algorithms,third edition, and if you have pdf format, just search for the keyword sentinel to have it all. In fact, This example is so concise and intriguing. Discussions on how to hunt for an elephant and Elephant in Cairo may interest you. Of course I am not talking about hunting elephants in real.

Especially in case if intrusive lists an important possibility with using a sentinel is that a list element can remove itself from the list without knowing the list it belongs. The element can just be removed from the circular chain. The sentinel element always remains there, so there is no possibility that the lists points to an element that is no longer in the list.