Sentinel node

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 doesn't 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

Below shows 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 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 end-of-list indicator

// 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 per iteration the 2 tests:

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

Second version using a sentinel node

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 per iteration only 1 test:

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

See also

• Sentinel value
• Elephant in Cairo