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 Sentinels are used as an alternative over using NULL as the path terminator in order to get one or more of the following benefits: Marginally increased speed of operations Increased data structure robustness (arguably) Drawbacks Marginally increased algorithmic complexity and code size. If the data structure is accessed concurrently (which means that all nodes being accessed have to be protected at least for “read-only”), for a sentinel-based implementation the sentinel node has to be protected for “read-write” by a mutex. This extra mutex in quite a few use scenarios can cause severe performance degradation. One way to avoid it is to protect the list structure as a whole for “read-write”, whereas in the version with NULL it suffices to protect the data structure as a whole for “read-only” (if an update operation will not follow). The sentinel concept is not useful for the recording of the data structure on disk. Examples Search in a linked list 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 struct sll_node *next; // end-of-list indicator or -> next node int key; } sll, *first; First version using NULL as an end-of-list indicator // global initialization first = NULL; // before the first insertion (not shown) struct sll_node *Search(struct sll_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 } // search_key is not contained in the list: return NULL; } The for-loop contains two tests (yellow lines) per iteration: 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. // global variable sll_node Sentinel, *sentinel = &Sentinel; // global initialization