View source for Sentinel node

{{Short description|Computer programming concept}}
{{about|the computer programming construct|the body part|Sentinel lymph node}}
{{distinguish|sentinel value}}
{{more citations needed|date=January 2021}}

{{Proposed deletion/dated
  |concern = �Not only does this article completely lack citations, the C implementation "Second version using a sentinel node" is misleading as it's actually identical to using NULL directly and accordingly will just segfault with the missing check. See here for an actual explanation of how a sentinel-node implementation works: https://docs.google.com/presentation/d/1BUYrC_QFq14FtJu6YnjpPqX-uAZig626urU45uxtDEA/edit?slide=id.g5ec417144_0251#slide=id.g5ec417144_0251
  |timestamp = 20251112030035
  |nom = ~2025-32798-12
  |help = 
}}

In computer programming, a '''sentinel node''' is a specifically designated [[node (computer science)|node]] used with [[linked list]]s and [[Tree (data structure)|trees]] as a traversal path terminator. This type of node does not hold or reference any data managed by the [[data structure]].

==Benefits==
{{unreferenced section|date=January 2016}}
Sentinels are used as an alternative over using [[null pointer|<code>NULL</code>]] as the path terminator in order to get one or more of the following benefits:
* Marginally increased speed of operations
* Increased data structure [[Robustness (computer science)|robustness]] (arguably)

==Drawbacks==
* Marginally increased memory usage, especially when linked list is short.

== Examples ==

=== Search in a linked list ===
Below are two versions of a subroutine (implemented in the [[C (programming language)|C programming language]]) for looking up a given search key in a [[Linked list#Singly linked list|singly linked list]]. The first one uses the [[sentinel value]] <code>NULL</code>, and the second one a (pointer to the) sentinel node <code>Sentinel</code>, as the end-of-list indicator. The declarations of the singly linked list data structure and the outcomes of both subroutines are the same.

<syntaxhighlight lang="c">
// one node of the singly linked list
typedef struct SinglyLinkedList {
    int key;
    struct SinglyLinkedList* next; // end-of-list indicator or -> next node
} SinglyLinkedList;
</syntaxhighlight>

==== First version using NULL as an end-of-list indicator ====
<syntaxhighlight lang="c">
// global initialization
SinglyLinkedList* first = NULL; // before the first insertion (not shown)

SinglyLinkedList* search(SinglyLinkedList* first, int searchKey) {
    for (SinglyLinkedList* node = first; node != NULL; node = node->next) {
        if (node->key == searchKey) {
            return node; // found
        }
    }
    // if searchKey is not contained in the list, return null:
    return NULL;
}
</syntaxhighlight>
The <code>for</code>-loop contains two tests per iteration:
* <code>node != NULL;</code>
* <code>if (node->key == searchKey)</code>.

==== Second version using a sentinel node ====
The globally available pointer <code>SENTINEL</code> is used as end-of-list indicator. 
<syntaxhighlight lang="c" line>
// global variable
const SinglyLinkedList* SENTINEL = NULL;
</syntaxhighlight>
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.

<syntaxhighlight lang="c">
SinglyLinkedList* searchWithSentinelNode(SinglyLinkedList* first, int searchKey) {
    // Prepare the "node" Sentinel for the search:
    SinklyLinkedList* node = first;
    while (node->key != searchKey) {
        node = node->next;
    }

    // Post-processing:
    if (node != SENTINEL) {
        return node; // found
    }

    // searchKey is not contained in the list:
    return NULL;
}
</syntaxhighlight>
The <code>for</code>-loop contains only one test (yellow line) per iteration:
* <code>node->key != searchKey;</code>.

==== 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 (programming language)|Python]] implementation of a circular doubly-linked list:

<syntaxhighlight lang="python">
from typing import Generator, Optional

class Node:
    self: int
    next: Node
    prev: Node

    def __init__(self, data: int, next: Node = None, prev: Node = None) -> None:
        self.data = data
        self.next = next
        self.prev = prev

    def __repr__(self) -> str:
        return f"Node(data={self.data})"

class LinkedList:
    self.sentinel: Node

    def __init__(self) -> None:
        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: Node) -> None:
        self.add_node(self.sentinel, node)

    def append_node(self, node: Node) -> None:
        self.add_node(self.sentinel.prev, node)

    def append_left(self, data: int) -> None:
        self.append_nodeleft(Node(data=data))

    def append(self, data: int) -> None:
        self.append_node(Node(data=data))

    def remove_by_ref(self, node: Node) -> Node:
        if node is self.sentinel:
            raise ValueError("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: Node, newnode: Node) -> None:
        newnode.next = curnode.next
        newnode.prev = curnode
        curnode.next.prev = newnode
        curnode.next = newnode

    def search(self, value: int) -> Optional[Node]:
        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) -> Generator[int, None, None]:
        node = self.sentinel.next
        while node is not self.sentinel:
            yield node.data
            node = node.next

    def reviter(self) -> Generator[int, None, None]:
        node = self.sentinel.prev
        while node is not self.sentinel:
            yield node.data
            node = node.prev
</syntaxhighlight>

Notice how the <code>add_node()</code> method takes the node that will be displaced by the new node in the parameter <code>curnode</code>. 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 <code>curnode</code> will be the sentinel node.

=== Search in a binary tree ===
General declarations, similar to article [[Binary search tree]]:
<syntaxhighlight lang="c">
// one node of the binary search tree
typedef struct BinarySearchTree {
    int key;
    // each: ->node  or  end-of-path indicator
    struct BinarySearchTree* left;
    struct BinarySearchTree* right;
} BinarySearchTree;
</syntaxhighlight>

The globally available pointer <code>SENTINEL</code> is used as end-of-list indicator. 
<syntaxhighlight lang="c" line highlight="12">
// global variable
const BinarySearchTree* SENTINEL = NULL;

BinarySearchTree* bst;
bst->root = SENTINEL; // before the first insertion (not shown)
</syntaxhighlight>
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.

<syntaxhighlight lang="c">
BinarySearchTree* searchWithSentinelNode(BinarySearchTree* bst, int searchKey) {
    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) {
        return node; // found
    }
    // searchKey is not contained in the tree: return null
    return NULL;
}
</syntaxhighlight>

====Remarks====
# With the use of <code>searchWithSentinelNode</code> searching loses the [[File-system permissions|read-only]] property. This means that in applications with [[Concurrent computing|concurrency]] it has to be protected by a [[mutex]], an effort which normally exceeds the savings of the sentinel.
# <code>searchWithSentinelNode</code> 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 ==
* [[Canary value]]
* [[Elephant in Cairo]]
* [[Guard (computer science)]], a boolean expression that must evaluate to true if the program execution is to continue in the branch in question
* [[Magic number (programming)]]
* [[Magic string]]
* [[Null object pattern]]
* [[Semipredicate problem]]
* [[Sentinel value]]
* [[Time formatting and storage bugs]]

==References==
<references/>

[[Category:Linked lists]]
[[Category:Trees (data structures)]]
{{⚠️🚨COPIED from EverybodyWiki ❗❕⚠️😡😤Please respect Licence CC-BY-SA ❗}}
{{Source Wikipedia}}