Sentinel node

A sentinel node is a programming idiom used to speed up some operations on linked lists and trees. It refers to a special type of object that represents the end of a data structure. Linked list data structures may use a sentinel object to indicate the end of a list. Similarly, a tree data structure can use a sentinel to indicate a node without children. It is not always necessary to use a sentinel node. Often null is used instead.

Example

Below is an example of a sentinel node in a binary tree implementation, from [http://www.eternallyconfuzzled.com/tuts/andersson.html] (which is about AA trees):

struct jsw_node { int data; int level; struct jsw_node *link [2] ;};

struct jsw_node *nil;

int jsw_init ( void ){ nil = malloc ( sizeof *nil ); if ( nil = NULL ) return 0;

nil->level = 0; nil->link [0] = nil->link [1] = nil;

return 1;}

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. NULL itself is known as a "sentinel value", a different approach to the same problem.

Sentinel nodes are often used when implementing linked lists.