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.
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.[1] 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 valueNULL, 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.
structsll_node{// one node of the singly linked liststructsll_node*next;// end-of-list indicator or -> next nodeintkey;}sll,*first;
First version using NULL as an end-of-list indicator
// global initializationfirst=NULL;// before the first insertion (not shown)structsll_node*Search(structsll_node*first,intsearch_key){structsll_node*node;for(node=first;node!=NULL;node=node->next){if(node->key==search_key)returnnode;// found}// search_key is not contained in the list:returnNULL;}
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 variablesll_nodeSentinel,*sentinel=&Sentinel;// global initializationsentinel->next=sentinel;first=sentinel;// before the first insertion (not shown)
Note that the pointer sentinel has always to be kept at the end of the list.
This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer.
structsll_node*SearchWithSentinelnode(structsll_node*first,intsearch_key){structsll_node*node;// Prepare the “node” Sentinel for the search:sentinel->key=search_key;for(node=first;node->key!=search_key;node=node->next){}// Post-processing:if(node!=sentinel)returnnode;// found// search_key is not contained in the list:returnNULL;}
The for-loop contains only one test (yellow line) per iteration:
node->key != search_key;.
Python implementation of a circular doubly-linked list
Linked list implementations, especially one of a circular, doubly-linked list, can be simplified remarkably using a sentinel node to demarcate the beginning and end of the list.
The list starts out with a single node, the sentinel node which has the next and previous pointers point to itself. This condition determines if the list is empty.
In a non-empty list, the sentinel node's next pointer gives the head of the list, and the previous pointer gives the tail of the list.
Following is a Python implementation of a circular doubly-linked list:
classNode:def__init__(self,data,next=None,prev=None):self.data=dataself.next=nextself.prev=prevdef__repr__(self)->str:returnf'Node(data={self.data})'classLinkedList:def__init__(self):self._sentinel=Node(data=None)self._sentinel.next=self._sentinelself._sentinel.prev=self._sentineldefpop_left(self)->Node:returnself.remove_by_ref(self._sentinel.next)defpop(self)->Node:returnself.remove_by_ref(self._sentinel.prev)defappend_nodeleft(self,node):self.add_node(self._sentinel,node)defappend_node(self,node):self.add_node(self._sentinel.prev,node)defappend_left(self,data):node=Node(data=data)self.append_nodeleft(node)defappend(self,data):node=Node(data=data)self.append_node(node)defremove_by_ref(self,node)->Node:ifnodeisself._sentinel:raiseException('Can never remove sentinel.')node.prev.next=node.nextnode.next.prev=node.prevnode.prev=Nonenode.next=Nonereturnnodedefadd_node(self,curnode,newnode):newnode.next=curnode.nextnewnode.prev=curnodecurnode.next.prev=newnodecurnode.next=newnodedefsearch(self,value):self._sentinel.data=valuenode=self._sentinel.nextwhilenode.data!=value:node=node.nextself._sentinel.data=Noneifnodeisself._sentinel:returnNonereturnnodedef__iter__(self):node=self._sentinel.nextwhilenodeisnotself._sentinel:yieldnode.datanode=node.nextdefreviter(self):node=self._sentinel.prevwhilenodeisnotself._sentinel:yieldnode.datanode=node.prev
Notice how the add_node() method takes the node that will be displaced by the new node in the parameter curnode. For appending to the left, this is the head of a non-empty list, while for appending to right, it is the tail. But because of how the linkage is set up to refer back to the sentinel, the code just works for empty lists as well, where curnode will be the sentinel node.
structbst_node{// one node of the binary search treestructbst_node*child[2];// each: ->node or end-of-path indicatorintkey;};structbst{// binary search treestructbst_node*root;// ->node or end-of-path indicator}*BST;
The globally available pointersentinel to the single deliberately prepared data structure Sentinel = *sentinel is used to indicate the absence of a child.
// global variablebst_nodeSentinel,*sentinel=&Sentinel;// global initializationSentinel.child[0]=Sentinel.child[1]=sentinel;BST->root=sentinel;// before the first insertion (not shown)
Note that the pointer sentinel has always to represent every leaf of the tree.
This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer.
structbst_node*SearchWithSentinelnode(structbst*bst,intsearch_key){structbst_node*node;// Prepare the “node” Sentinel for the search:sentinel->key=search_key;for(node=bst->root;;){if(search_key==node->key)break;ifsearch_key<node->key:node=node->child[0];// go leftelsenode=node->child[1];// go right}// Post-processing:if(node!=sentinel)returnnode;// found// search_key is not contained in the tree:returnNULL;}
Remarks
With the use of SearchWithSentinelnode searching loses the R/O property. This means that in applications with concurrency it has to be protected by a mutex, an effort which normally exceeds the savings of the sentinel.
SearchWithSentinelnode does not support the tolerance of duplicates.
There has to be exactly one “node” to be used as sentinel, but there may be extremely many pointers to it.