前哨節點

在電腦程式設計中，哨兵節點（sentinel node）是一種特殊指定的節點，在鏈結串列和樹中用作遍歷路徑的終止符。此類節點不持有或引用該資料結構所管理的任何資料。

優點

哨兵節點被用來替代 `NULL` 作為路徑終止符，以獲得以下一個或多個好處：

• 略微提升操作速度
• 提升資料結構的穩健性（有爭議）

缺點

• 略微增加記憶體用量，尤其是在鏈結串列很短時。

範例

在鏈結串列中搜尋

以下是兩個用於在單向鏈結串列中查找給定搜尋鍵的子程式版本（以 C 程式語言實作）。第一個版本使用哨兵值 `NULL`，第二個版本使用（指向）哨兵節點 `Sentinel` 的指標，作為串列結尾的指示符。兩種子程式的單向鏈結串列資料結構宣告和結果都是相同的。

<syntaxhighlight lang="c"> struct sll_node { // 單向鏈結串列的一個節點

   struct sll_node *next;                 // 串列結尾指示符或 -> 下一個節點
   int key;

</syntaxhighlight>

第一個版本，使用 NULL 作為串列結尾指示符

<syntaxhighlight lang="c" line highlight="7,10"> // 全域初始化 first = NULL; // 在首次插入前（未顯示）

struct sll_node *Search(struct sll_node *first, int search_key) {

   struct sll_node *node;
   for (node = first;
       node != NULL;
       node = node->next)

       if (node->key == search_key)
           return node;                   // 找到

   // search_key 不包含在串列中：
   return NULL;

</syntaxhighlight> `for` 迴圈的每次迭代包含兩個測試（黃色標示行）：

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

第二個版本，使用哨兵節點

全域可用的指標 `sentinel` 指向特意準備的資料結構 `Sentinel`，並被用作串列結尾指示符。 <syntaxhighlight lang="c" line> // 全域變數 sll_node Sentinel, *sentinel = &Sentinel; // 全域初始化 sentinel->next = sentinel; first = sentinel; // 在首次插入前（未顯示） </syntaxhighlight> 請注意，`sentinel` 指標必須始終保持在串列的末端。 這必須由插入和刪除函式來維護。然而，這與使用 NULL 指標所需的功夫大致相同。

<syntaxhighlight lang="c" highlight="6"> struct sll_node *SearchWithSentinelnode(struct sll_node *first, int search_key) {

   struct sll_node *node;
   // 為搜尋準備「節點」Sentinel：
   sentinel->key = search_key;
   for (node = first;
       node->key != search_key;
       node = node->next)

   // 後續處理：
   if (node != sentinel)
       return node;                       // 找到
   // search_key 不包含在串列中：
   return NULL;

</syntaxhighlight> `for` 迴圈的每次迭代只包含一個測試（黃色標示行）：

• `node->key != search_key;`。

Python 的環狀雙向鏈結串列實作

鏈結串列的實作，特別是環狀雙向鏈結串列，可以透過使用哨兵節點來標記串列的開頭和結尾，從而顯著簡化。

• 串列始於一個單一節點，即哨兵節點，其 `next` 和 `previous` 指標都指向自身。此條件可用於判斷串列是否為空。
• 在非空串列中，哨兵節點的 `next` 指標指向串列的頭部，而 `previous` 指標則指向串列的尾部。

以下是 Python 的環狀雙向鏈結串列實作：

<syntaxhighlight lang="python"> 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={self.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

</syntaxhighlight>

請注意 `add_node()` 方法如何將會被新節點取代的節點作為參數 `curnode` 傳入。當在左側附加時，此節點是非空串列的頭部；而在右側附加時，則是尾部。但由於鏈結的設定方式會指回哨兵節點，因此這段程式碼對於空串列同樣有效，此時 `curnode` 會是哨兵節點。

在二元樹中搜尋

一般宣告，類似於二元搜尋樹的文章： <syntaxhighlight lang="c"> struct bst_node { // 二元搜尋樹的一個節點

   struct bst_node *child[2];        // 每個：->node 或 結尾路徑指示符
   int key;

struct bst { // 二元搜尋樹

   struct bst_node *root;            // ->node 或 結尾路徑指示符

</syntaxhighlight>

全域可用的指標 `sentinel` 指向單一特意準備的資料結構 `Sentinel = *sentinel`，用來指示子節點不存在。 <syntaxhighlight lang="c" line highlight="12"> // 全域變數 bst_node Sentinel, *sentinel = &Sentinel; // 全域初始化 Sentinel.child[0] = Sentinel.child[1] = sentinel;

BST->root = sentinel; // 在首次插入前（未顯示） </syntaxhighlight> 請注意，`sentinel` 指標必須始終代表樹中的每一個葉節點。 這必須由插入和刪除函式來維護。然而，這與使用 NULL 指標所需的功夫大致相同。

<syntaxhighlight lang="c" line="11"> struct bst_node *SearchWithSentinelnode(struct bst *bst, int search_key) {

   struct bst_node *node;
   // 為搜尋準備「節點」Sentinel：
   sentinel->key = search_key;

   for (node = bst->root;;) {
       if (search_key == node->key)
           break;
       if search_key < node->key:
           node = node->child[0];    // 向左
       else
           node = node->child[1];    // 向右

   // 後續處理：
   if (node != sentinel)
       return node;                  // 找到
   // search_key 不包含在樹中：
   return NULL;

</syntaxhighlight>

備註：

1. 使用 `SearchWithSentinelnode` 會使搜尋失去其唯讀屬性。這意味著在有並行處理的應用程式中，它必須受到互斥鎖（mutex）的保護，這種額外開銷通常會超過使用哨兵節點所節省的效益。
2. `SearchWithSentinelnode` 不支援處理重複值。
3. 必須有且僅有一個「節點」用作哨兵，但可以有極多個指標指向它。

參見

• 金絲雀值 (Canary value)
• 開羅的大象 (Elephant in Cairo)
• 衛述句 (電腦科學) (Guard (computer science))，一個布林表達式，若程式要繼續在該分支中執行，則此表達式必須為真
• 魔法數字 (程式設計) (Magic number (programming))
• 魔法字串 (Magic string)
• 空物件模式 (Null object pattern)
• 半謂詞問題 (Semipredicate problem)
• 哨兵值 (Sentinel value)
• 時間格式化與儲存錯誤 (Time formatting and storage bugs)