 | This article needs additional citations for verification .(January 2021) |
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.
| |
Sentinels are used as an alternative over using NULL as the path terminator in order to get one or more of the following benefits:
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.
// one node of the singly linked listtypedefstructSinglyLinkedList{intkey;structSinglyLinkedList*next;// end-of-list indicator or -> next node}SinglyLinkedList;// global initializationSinglyLinkedList*first=NULL;// before the first insertion (not shown)SinglyLinkedList*search(SinglyLinkedList*first,intsearchKey){for(SinglyLinkedList*node=first;node;node=node->next){if(node->key==searchKey){returnnode;// found}}// if searchKey is not contained in the list, return null:returnNULL;}The for-loop contains two tests (yellow lines) per iteration:
node != NULL;if (node->key == searchKey).The globally available pointer SENTINEL is used as end-of-list indicator.
// global variableconstSinglyLinkedList*SENTINEL=NULL;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.
SinglyLinkedList*searchWithSentinelNode(SinglyLinkedList*first,intsearchKey){// Prepare the "node" Sentinel for the search:SinklyLinkedList*node=first;while(node->key!=searchKey){node=node->next;}// Post-processing:if(node!=SENTINEL){returnnode;// found}// searchKey is not contained in the list:returnNULL;}The for-loop contains only one test (yellow line) per iteration:
node->key != searchKey;.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.
Following is a Python implementation of a circular doubly-linked list:
fromtypingimportGenerator,OptionalclassNode:self:intnext:Nodeprev:Nodedef__init__(self,data:int,next:Node=None,prev:Node=None)->None:self.data=dataself.next=nextself.prev=prevdef__repr__(self)->str:returnf"Node(data={self.data})"classLinkedList:self.sentinel:Nodedef__init__(self)->None: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:Node)->None:self.add_node(self.sentinel,node)defappend_node(self,node:Node)->None:self.add_node(self.sentinel.prev,node)defappend_left(self,data:int)->None:self.append_nodeleft(Node(data=data))defappend(self,data:int)->None:self.append_node(Node(data=data))defremove_by_ref(self,node:Node)->Node:ifnodeisself.sentinel:raiseValueError("Can never remove sentinel.")node.prev.next=node.nextnode.next.prev=node.prevnode.prev=Nonenode.next=Nonereturnnodedefadd_node(self,curnode:Node,newnode:Node)->None:newnode.next=curnode.nextnewnode.prev=curnodecurnode.next.prev=newnodecurnode.next=newnodedefsearch(self,value:int)->Optional[Node]:self.sentinel.data=valuenode=self.sentinel.nextwhilenode.data!=value:node=node.nextself._sentinel.data=Noneifnodeisself.sentinel:returnNonereturnnodedef__iter__(self)->Generator[int,None,None]:node=self.sentinel.nextwhilenodeisnotself.sentinel:yieldnode.datanode=node.nextdefreviter(self)->Generator[int,None,None]:node=self.sentinel.prevwhilenodeisnotself.sentinel:yieldnode.datanode=node.prevNotice 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.
General declarations, similar to article Binary search tree:
// one node of the binary search treetypedefstructBinarySearchTree{intkey;// each: ->node or end-of-path indicatorstructBinarySearchTree*left;structBinarySearchTree*right;}BinarySearchTree;The globally available pointer SENTINEL is used as end-of-list indicator.
// global variableconstBinarySearchTree*SENTINEL=NULL;BinarySearchTree*bst;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.
BinarySearchTree*searchWithSentinelNode(BinarySearchTree*bst,intsearchKey){BinarySearchTree*node;while(node->Key!=searchKey){if(search_key<node->key){node=node->left;// go left}else{node=node->right;// go right}}// Post-processing:if(node!=SENTINEL){returnnode;// found}// searchKey is not contained in the tree: return nullreturnNULL;}searchWithSentinelNode searching loses the read-only 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.