HOME

TheInfoList



OR:

In computer programming, a sentinel node is a specifically designated
node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...
used with
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
s and
trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
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: * Marginally increased speed of operations * Increased data structure
robustness Robustness is the property of being strong and healthy in constitution. When it is transposed into a system, it refers to the ability of tolerating perturbations that might affect the system’s functional body. In the same line ''robustness'' ca ...
(arguably)


Drawbacks

* 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 In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concur ...
. 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” (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 ''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as ...
) for looking up a given search key in a
singly linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which ...
. The first one uses the
sentinel value In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in ...
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 sll, *first;


First version using NULL as an end-of-list indicator

// global initialization first = NULL; // before the first insertion (not shown) 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)
.


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 variable sll_node Sentinel, *sentinel = &Sentinel; // global initialization sentinel->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. struct sll_node *SearchWithSentinelnode(struct sll_node *first, int search_key) 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: class Node: def __init__(self, data, next=None, prev=None): self.data = data self.next = next self.prev = prev 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.


Search in a binary tree

General declarations, similar to article
Binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
: struct bst_node ; 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. // global variable bst_node Sentinel, *sentinel = &Sentinel; // global initialization Sentinel.child = Sentinel.child = 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. struct bst_node *SearchWithSentinelnode(struct bst *bst, int search_key) { struct bst_node *node; // Prepare the “node” Sentinel for the search: sentinel->key = search_key; for (node = bst->root;;) { if (search_key

node->key) break; if search_key < node->key: node = node->child // go left else node = node->child // go right } // Post-processing: if (node != sentinel) return node; // found // search_key is not contained in the tree: return NULL; }
;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 In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concur ...
, 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.


See also

*
Sentinel value In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in ...
*
Magic number (programming) In computer programming, a magic number is any of the following: * A unique value with unexplained meaning or multiple occurrences which could (preferably) be replaced with a named constant * A constant numerical or text value used to identify a ...
*
Magic string In computer programming, a magic string is an input that a programmer believes will never come externally and which activates otherwise hidden functionality. A user of this program would likely provide input that gives an expected response in mo ...
*
Null object pattern In object-oriented computer programming, a null object is an object with no referenced value or with defined neutral (''null'') behavior. The null object design pattern, which describes the uses of such objects and their behavior (or lack thereof) ...
*
Time formatting and storage bugs In computer science, time formatting and storage bugs are a class of software bugs that may cause time and date calculation or display to be improperly handled. These are most commonly manifestations of arithmetic overflow, but can also be the re ...
*
Elephant in Cairo An elephant in Cairo is a term used in computer programming to describe a piece of data that matches the search criteria purposefully inserted at the end of a search space, in order to make sure the search algorithm terminates; it is a humorous exa ...
*
Canary value Canary originally referred to the island of Gran Canaria on the west coast of Africa, and the group of surrounding islands (the Canary Islands). It may also refer to: Animals Birds * Canaries, birds in the genera '' Serinus'' and '' Crithagra'' ...
*
Semipredicate problem In computer programming, a semipredicate problem occurs when a subroutine intended to return a useful value can fail, but the signalling of failure uses an otherwise valid return value. The problem is that the caller of the subroutine cannot tell ...


References

Linked lists Trees (data structures)