Sentinel

A sentinel value refers to a special value that signifies termination or some other sentinel condition. This avoids the need for separate terminating variables or flags.

Some examples include:

• Null terminator in C strings
• -1 signaling no more values in a loop
• Special value denoting parent node in tree/graph

Java example - linked list traversal:

1
2
3
4
5
6
7

Node traverse(Node head) {
  Node current = head;
  while (current != null) { // null as sentinel
    current = current.next; 
  }
  return current; 
}

C++ example - string processing:

1
2
3
4
5
6

void processString(const char *str) {
  while (*str != '\0') { // null char as sentinel
    processChar(*str);
    str++;
  }
}

Python example - tree traversal:

1
2
3
4
5
6
7

def traverse(root):
  node = root 
  while node is not None: # None as sentinel
    traverse_children(node)
    node = node.next 
  
  process_final(node)  

Sentinels provide an elegant way to denote endings and boundaries without separate constructs.

A sentinel is a special value used to indicate the end of a data structure or a loop. It serves as a flag or marker, simplifying algorithms by eliminating the need for complex termination conditions. Sentinels are commonly used in linked lists, arrays, and algorithms like linear search.

1. Sentinels act as markers or flags.
2. They simplify algorithms.
3. Commonly used in linked lists, arrays, and search algorithms.

A sentinel is a dummy object that allows us to simplify boundary conditions

Code Examples

Java

In Java, you can use a sentinel value in a while loop to read until a specific value is encountered.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int sentinel = -1;
        int value;

        while (true) {
            value = sc.nextInt();
            if (value == sentinel) break;
            System.out.println("Read: " + value);
        }
    }
}

C++

In C++, a sentinel value can be used in the same manner to read input or traverse an array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>
using namespace std;

int main() {
    int sentinel = -1;
    int value;

    while (true) {
        cin >> value;
        if (value == sentinel) break;
        cout << "Read: " << value << endl;
    }

    return 0;
}

Python

Python allows for easy use of sentinel values in loops. The following example uses a sentinel to break a while loop.

1
2
3
4
5
6
7

sentinel = -1

while True:
    value = int(input())
    if value == sentinel:
        break
    print(f"Read: {value}")

Using a sentinel value streamlines the algorithm, making it easier to read and understand.