Sentinel node

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

Sentinels are used as an alternative over using null as the path terminator in order to get one or more of the following benefits:

  1. Increased speed of operations
  2. Reduced algorithmic complexity and code size
  3. Increased data structure robustness (arguably)

However, sentinel nodes rely on shared memory, which requires extra code to avoid data races. This causes sentinel nodes to have poor performance on concurrent systems.

Examples[edit]

Search[edit]

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 {                          // one node of the singly linked list
   int key;
   struct sll_node *next;                  // end-of-list indicator or -> next node
} sll, *first;

First version using NULL as an end-of-list indicator[edit]

 1 // global initialization
 2 first = NULL;                              // before the first insertion (not shown)
 3 
 4 struct sll_node *Search(struct sll_node *first, int search_key) {
 5     struct sll_node *node;
 6     for (node = first; 
 7         node != NULL; 
 8         node = node->next)
 9     {
10         if (node->key == search_key)
11             return node;                   // found
12     }
13     // not found
14     return NULL;
15 }

The for-loop contains two tests (yellow lines) per iteration:

  • node != NULL;
  • if (node->key == search_key).

Second version using a sentinel node[edit]

The globally available pointer sentinel to the deliberately prepared data structure Sentinel is used as end-of-list indicator.

 1 // global variable
 2 sll_node Sentinel, *sentinel = &Sentinel;
 3 // global initialization
 4 sentinel->next = sentinel;
 5 first = sentinel;                          // before the first insertion (not shown)
 6 // Note that the pointer  sentinel  has always to be kept at the END of the list.
 7 
 8 struct sll_node *SearchWithSentinelnode(struct sll_node *first, int search_key) {
 9     struct sll_node *node;
10     sentinel->key = search_key;
11     for (node = first; 
12         node->key != search_key; 
13         node = node->next)
14     {
15     }
16     if (node != sentinel)
17         return node;                       // found
18     // not found
19     return NULL;
20 }

The for-loop contains only one test (yellow line) per iteration:

  • node->key != search_key;.

Remark[edit]

If the data structure is accessed concurrently then for a sentinel-based implementation, not only the node pointed to by first has to be protected for “read-only” by a mutex, but also the node Sentinel has to be protected for “read-write”; this extra mutex in quite a few use scenarios can cause severe performance degradation [1]. One way to avoid it is to protect the list structure as a whole for “read-write”, whereas in the first version (with end-of-list indicator NULL) it suffices to protect the list structure as a whole for “read-only” (if an update operation will not follow).

Linked list implementation[edit]

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):
        return 'Node(data={})'.format(self.data)


class LinkedList:
    def __init__(self):
        self._sentinel = Node(data=None)
        self._sentinel.next = self._sentinel
        self._sentinel.prev = self._sentinel

    def popleft(self):
        return self.remove_by_ref(self._sentinel.next)

    def pop(self):
        return self.remove_by_ref(self._sentinel.prev)

    def appendnodeleft(self, node):
        self.add_node(self._sentinel, node)

    def appendnode(self, node):
        self.add_node(self._sentinel.prev, node)

    def appendleft(self, data):
        node = Node(data=data)
        self.appendnodeleft(node)

    def append(self, data):
        node = Node(data=data)
        self.appendnode(node)

    def remove_by_ref(self, 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 setup to refer back to the sentinel, the code just works for empty lists as well, where curnode will be the sentinel node.

See also[edit]

References[edit]

  1. ^ Ignatchenko, Sergey (1998), "STL Implementations and Thread Safety", C++ Report