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.
Contents
Benefits
Sentinels are used as an alternative over using null as the path terminator in order to get one or more of the following benefits:
- Increased speed of operations
- Reduced algorithmic complexity and code size
- Increased data structure robustness (arguably)
However, sentinel nodes rely on shared memory, which requires extra code to avoid data races. This causes sentinel nodes to have poor performance on concurrent systems.
Example
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.
First version using NULL as an end-of-list indicator
The for-loop contains two tests per iteration:
if (node != NULL)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.
The for-loop contains only one test per iteration:
if (node->key != search_key).
If the data structure is accessed concurrently then the operation SearchWithSentinelnode belongs into a critical section which has to be protected by a mutex – as modifying operations always do.