Sentinel node should not be confused with sentinel value.
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:
NULL
it suffices to protect the data structure as a whole for “read-only” (if an update operation will not follow).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 *Search(struct sll_node *first, int search_key) The for
-loop contains two tests (yellow lines) per iteration:
node != NULL;
if (node->key == search_key)
.The globally available pointer sentinel
to the deliberately prepared data structure Sentinel
is used as end-of-list indicator.
for
-loop contains only one test (yellow line) per iteration:
node->key != search_key;
.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:
def __repr__(self) -> str: return f'Node(data=)'
class LinkedList: def __init__(self): self._sentinel = Node(data=None) self._sentinel.next = self._sentinel self._sentinel.prev = self._sentinel
def pop_left(self) -> Node: return self.remove_by_ref(self._sentinel.next)
def pop(self) -> Node: return self.remove_by_ref(self._sentinel.prev)
def append_nodeleft(self, node): self.add_node(self._sentinel, node)
def append_node(self, node): self.add_node(self._sentinel.prev, node)
def append_left(self, data): node = Node(data=data) self.append_nodeleft(node)
def append(self, data): node = Node(data=data) self.append_node(node)
def remove_by_ref(self, node) -> Node: if node is self._sentinel: raise Exception('Can never remove sentinel.') node.prev.next = node.next node.next.prev = node.prev node.prev = None node.next = None return node
def add_node(self, curnode, newnode): newnode.next = curnode.next newnode.prev = curnode curnode.next.prev = newnode curnode.next = newnode
def search(self, value): self._sentinel.data = value node = self._sentinel.next while node.data != value: node = node.next self._sentinel.data = None if node is self._sentinel: return None return node
def __iter__(self): node = self._sentinel.next while node is not self._sentinel: yield node.data node = node.next
def reviter(self): node = self._sentinel.prev while node is not self._sentinel: yield node.data node = 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.
General declarations, similar to article Binary search tree:
struct bst *BST;
The globally available pointer sentinel
to the single deliberately prepared data structure Sentinel = *sentinel
is used to indicate the absence of a child.
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.