Sentinel node

From Wikipedia, the free encyclopedia

A sentinel node is a programming idiom used to speed up some operations on linked lists and trees.

Below is an example of a sentinel node in a binary tree implementation, from [1] (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.