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?

Prenomen

Answer 1

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.

Funeral

Thanks for the example, that makes a lot more sense now. I was just thinking in terms of iterating, so I didn't really see the benefit. – Prenomen

You're welcome - sentinels are really just a clever way of setting invariants for your algorithms that you can exploit! – Funeral

I don't like the idea that find() should alter the data structure; for example rules off using find from multiple threads even if all of them are only searching elements. – Skepticism

I'm very much aware of that, but that's a hazard you have to deal with when using sentinels. You can't have data invariants without setting them somewhere. I think it illustrates the idea very well tho. For a more useful example, intro-sort's unguarded partition is a lot better but also a lot more complex. – Funeral

Also, you can just always use the sentinel variant of find for the first thread and use the non-sentinel version for other threads - You'll have some gain and the function is still reentrant. – Funeral

Could you checkout my answer? I did some little add-ups. – Churning

Code in this answer is totally wrong. With *list.end() = x; you will be laughed out of any code review. Of course std::list doesn't implement it this way. @HanXIAO this thread is 8 years old, good luck getting attention from the originators. – Disarming

@n.m. haha. I just want the correct answer be expressed in a more accessible way. – Churning

@HanXIAO your code doesn't use a sentinel node. end could just as well be a null pointer. So it doesn't answer the question. – Disarming

@n.m. yeah. My point is that sentinel is not merely used to reduce code complexity, but also it helps to reduce the boundary checking expense, because the loop will terminate due to the existence of sentinel value. – Churning

Answer 2

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

Skepticism

+1 another good example, especially for the code complexity category. – Funeral

Note that there are at least two different meanings to "sentinel" node: this one (a dummy extra node to avoid the annoying empty cases) and the one in the accepted answer (a node at the end of the list, which can be used to reduce branches when searching, and gain efficiency). – Metallist

Answer 3

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.

Mena

Answer 4

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; 
}

Selfsealing

Answer 5

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.

Churning

"here, even compared with the code with sentinel, this version is better" You simply state that your version of the snippet is "better", but do you have any arguments supporting that? To me it looks exactly like the first snippet in ltjax's answer (maybe better in terms of style only). It seems to have the same problem: it requires 2 comparsions per iteration, compared to 1 comparsion when using a sentiel. So the version with the sentiel should be better, no? – Cower

Yes. The version I am providing is somewhat better because of the reduced code complexity and we can easily see the loop termination condition, without going through the whole loop body, to reason about correctness compared with the non-sentinel version Itjax provides. But because it does not use sentinel, it still suffers from one more comparison. – Churning

I see. The wording of the answer confused me then, I though you were saying it's better than the sentiel version as well. – Cower

I will concise it now. – Churning

@Cower of course it is better, simply because the sentinel version is plainly broken (it modifies the list it searches, which is very much unacceptable). Anything non-broken is better than anything broken. – Disarming

@n.m. It's unacceptable if you need to search the list from several threads. If it's used from a single thread only, I think that could be a viable option, if the performance increase is worth it. (Since only the sentiel node is modified, the data in the list is not really "modified".) – Cower

@Cower No, it is just unacceptable, period. There's a host of assumptions you need to make for this to work, beside the single threaded-ness. It's just not worth it. And of course mentioning std::list in the same post is just misleading. This is not how std::list is allowed to operate. If you need top performance, there's a much better option: not using linked lists in the first place. – Disarming

Answer 6

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.

Precipitate