SENTINEL NODE

For other uses, see Sentinel lymph node.

A sentinel node is 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.

There is more information about their use in linked lists here.

This computer programming-related article is a stub. You can help Wikipedia by expanding it.