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:
If the data structure is accessed concurrently, 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”.
The sentinel concept is not useful for the recording of the data structure on disk.
Examples
Search
Below are two versions of a subroutine for looking up a given search key in a singly linked list. The first one uses the sentinel valueNULL, and the second one a 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 sll, *first;
First version using NULL as an end-of-list indicator
// global initialization first = NULL; // before the first insertion struct sll_node *Search
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 sentinel->next = sentinel; first = sentinel; // before the first insertion // Note that the pointer sentinel has always to be kept at the END of the list. struct sll_node *SearchWithSentinelnode
The for-loop contains only one test per iteration:
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: class Node: def __init__ -> None: self.data = data self.next = next self.prev = prev def __repr__ -> str: return 'Node'.format class LinkedList: def __init__ -> None: self._sentinel = Node self._sentinel.next = self._sentinel self._sentinel.prev = self._sentinel def pop_left: return self.remove_by_ref def pop: return self.remove_by_ref def append_nodeleft -> None: self.add_node def append_node: self.add_node def append_left -> None: node = Node self.append_nodeleft def append -> None: node = Node self.append_node def remove_by_ref: if node is self._sentinel: raise Exception node.prev.next = node.next node.next.prev = node.prev node.prev = None node.next = None return node def add_node -> None: newnode.next = curnode.next newnode.prev = curnode curnode.next.prev = newnode curnode.next = newnode def search: 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__: node = self._sentinel.next while node is not self._sentinel: yield node.data node = node.next def reviter: 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 setup to refer back to the sentinel, the code just works for empty lists as well, where curnode will be the sentinel node.
