What is a sentinel in programming?

Answer 1

A real-world sentinel is a soldier or guard, someone who keeps watch. In programming, a sentinel is typically a "dummy" node that is used specifically to mark the beginning or end of a data sequence. If we consider a singly-linked list (also known as a forward list), each node points forwards to the next node in the sequence. When we insert a new node into a list, we typically specify the node that will come immediately before it in the sequence because that node also points to the node that will (ultimately) come after it. Thus our algorithm can be encoded as follows:

void insert_after (Node* node, Node* prev) {

assert (node);

assert (prev);

node->next = prev->next;

prev->next = node;

}

This is fine until we try and insert a new node at the start of the sequence or try to insert into an empty list. In both cases, p will be a null pointer because there can be no node that can come before the new node, n. Thus the assertion that p is non-null will fail. To cater for this, we must over-complicate the algorithm by testing for each of these special cases and, in order to do so, pass another argument to the function, namely the list itself:

void insert_after (List* list, Node* node, Node* prev) {

assert (list);

assert (node);

if (!list->head) { /* cater for empty list */

assert (!prev);

list->head = node;

node->next = null;

} else if (!prev) { /* insert at head of list */

node->next = list->head;

list->head = node;

} else {

node->next = prev->next;

prev->next = node;

}

}

However, if we place a sentinel at the beginning of the list, we guarantee that even an empty list will always have at least one node (the sentinel) and that whenever we insert a new node into the list there will always be a node that can come before that new node. Thus our original function works efficiently without having to deal with any special cases.

The sentinel node is similar to any other node except that it does not store any data, it simply points to the first node in the sequence or to null if the list is empty.