Sentinel node

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about the computer programming construct. For the body part, see Sentinel lymph node.
Not to be confused with sentinel value.

A sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. A sentinel node does not hold or reference any data managed by the data structure. Sentinels are used as an alternative over using null as the path terminator in order to get one or more of the following benefits:

  1. Increased speed of operations
  2. Reduced algorithmic complexity and code size
  3. Increased data structure robustness (arguably)

Example[edit]

Below shows an initialization of a sentinel node in a binary tree implemented in the C programming language:[1]

struct jsw_node {
   int data;
   int level;
   struct jsw_node *link[2];                  // link[0] to next_left node; link[1] to next_right node
};
 
struct jsw_node *nil;                         // pointer to the sentinel node
 
int jsw_init ( void )
{
   nil = malloc ( sizeof *nil );              // allocating memory for the sentinel node
   if ( nil == NULL )                         // check for malloc() failure
      return 0;                               // malloc() failed to allocate memory
 
   nil->level = 0;
   nil->link[0] = nil->link[1] = nil;         // link both right and left nodes to self (empty tree)
 
   return 1;                                  // successful initialization
}

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.

References[edit]

  1. ^ http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx