A sentinel node is a specifically designated node

Node (computer science)

A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...

 used with linked list

Linked list

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...

s and trees

Tree (data structure)

In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...

 as a traversal path terminator. A sentinel node does not 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 is an example of a sentinel node in a binary tree

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...

 implementation:


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

Sentinel value

In computer programming, a sentinel value is a special value whose presence guarantees termination of a loop that processes structured data...

, a different approach to the same problem.