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.

In computer programming, a sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.

Benefits[edit]

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 are two versions of a subroutine (implemented in the C programming language) for looking up a given search key in a singly linked list. The first one uses the sentinel value NULL, and the second one a (pointer to the) sentinel node Sentinel, as the end-of-list indicator. The declarations of the singly linked list data structure and the outcomes of both subroutines are the same.

struct sll_node {                          // one node of the singly linked list
   int key;
   struct sll_node *next;                  // end-of-list indicator or -> next node
} sll, *first;

First version using NULL as an end-of-list indicator[edit]

// global initialization
first = NULL;                              // before the first insertion (not shown)

struct sll_node *Search(struct Node *first, int search_key) {
    struct sll_node *node;
    for (node = first; node != NULL; node = node->next) {
        if (node->key == search_key)
            return node;                   // found
    }
    // not found
    return NULL;
}

The for-loop contains two tests per iteration:

  1. if (node != NULL)
  2. if (node->key == search_key).

Second version using a sentinel node[edit]

The globally available pointer sentinel to the deliberately prepared data structure Sentinel is used as end-of-list indicator.

// global variable
sll_node Sentinel, *sentinel = &Sentinel;
// global initialization
sentinel->next = sentinel;
first = sentinel;                          // before the first insertion (not shown)

struct sll_node *SearchWithSentinelnode(struct Node *first, int search_key) {
    struct sll_node *node;
    sentinel->key = search_key;
    for (node = first; node->key != search_key; node = node->next) {
    }
    if (node != sentinel)
        return node;                       // found
    // not found
    return NULL;
}

The for-loop contains only one test per iteration:

  1. if (node->key != search_key).

See also[edit]

References[edit]