檢視前哨節點的原始碼

在電腦程式設計中，哨兵節點（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>

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

== 參見 ==
* 金絲雀值 (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)

==參考資料==

[[分類: 待校正]]