摘要訊息 : 前向連結串列是連結式的向量, 它對插入和移除操作機其友好

0. 前言

對於向量 $\boldsymbol {\alpha} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$, 在《【資料結構】向量 (順序表)》中, 它是以連續的方式儲存在空間中的. 因此, 插入和移除都要對元素進行移動, 但是向量存取元素的效率極高. 前向連結串列是一個剛好相反的資料結構, 它在空間中並不一定是連續儲存的, 因此存取其中的元素的效率遠不如連續儲存的向量. 但是對於插入和移除元素操作, 它卻有著極高的效率.

更新紀錄 :

• 2022 年 3 月 25 日進行第一次更新和修正.

1. 定義

定義 1. 我們稱由元素 $e$ 和指向型標記 $p$ 組成的 $(e, p)$ 為結點 (node).

定義 2. 我們稱向量 $\boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$ 的擴展 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$ 為前向連結串列 (forward list). 其中, $(\alpha_{i}, p_{i})$ 為前向連結串列的結點, $p_{i}$ 為結點 $(\alpha_{i}, p_{i})$ 的指向型標記 (directional subscript), $1 \leq i \leq n$.

一般來說, 對於定義 2 中向量 $\boldsymbol {\alpha}_{0}$的擴展 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$, 除了最後一個元素之外的每一個結點的指向性標記都有 $\displaystyle {p_{i} = i + 1}.$ 其中, $i = 1, 2, ..., n - 1$. 對於最後一個元素對應的指向性標記 $p_{n}$, 它可以指向第一個元素, 即 $p_{n} = 1$; 也可以不指向任何結點, 此時我們可以記 $p_{n} = 0$ 或者 $p_{n} = \infty$. 為了統一起見, 也為了避免資料結構和程式設計中可能產生的歧異, 接下來如果遇到前向連結串列中最後一個結點的指向性標記不指向任何結點, 我們統一使用標記 $p_{n} = \infty$.

在程式設計中, 前向連結串列結點中的指向性標記 $p$ 指向的可能是記憶體或者其它儲存空間中的某個區塊 :

而當前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$ 退化為向量 $\boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$ 時, 它在記憶體中的儲存方式可能是這樣的 :

在 Figure 2 中, 記憶體區間 $[\text {0x0FFF}, \text {0xFBE9}]$ 中儲存著前向連結串列中的各個結點, 但是這裡面還儲存著別的一些資料. 而在 Figure 3 中, 記憶體區間 $[\text {0x3000}, \text {0x3FFF}]$ 中儲存著向量的所有元素, 這段記憶體區間完全由向量掌控, 不存在任何其它的資料. 這便是向量和前向連結串列最大的區別.

2. 插入

我們已經在前面提到過, 前向連結串列的插入比向量要簡單得多. 假設我們在前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) : p_{1} = 2, p_{2} = 3, ..., p_{n - 1} = n, p_{n} = \infty \right \}$ 的第 $i$ 位置插入 $m$ 個元素 $\beta_{1}, \beta_{2}, ..., \beta_{m}$ ($1 \leq i \leq n + 1$). 那麼 $\beta_{1}$ 就在 $\boldsymbol {\alpha}$ 中的第 $i$ 個結點中, $\beta_{2}$ 就在 $\boldsymbol {\alpha}$ 中的第 $i + 1$ 個結點中, ..., $\beta_{m}$ 就在 $\boldsymbol {\alpha}$ 中的第 $i + m - 1$ 個結點中. 而原來的 $\alpha_{i}$ 在插入之後應該在 $\boldsymbol {\alpha}$ 的第 $i + m$ 個結點中, 原來的 $\alpha_{i + 1}$ 在插入之後應該在 $\boldsymbol {\alpha}$ 的第 $i + m + 1$ 個結點中, ..., 原來的 $\alpha_{n}$ 在插入之後應該在 $\boldsymbol {\alpha}$ 的第 $n + m$ 個結點中. 具體過程應該是 :

1. 配置 $m$ 個結點 $(\beta_{1}, p_{n + 1}), (\beta_{2}, p_{n + 2}), ..., (\beta_{m}, p_{n + m})$;
2. 令 $p_{n + 1} = i + 1, p_{n + 2} = i + 2, ..., p_{n + m} = i + m$;
3. 令 $p_{i} = i + m + 1, p_{i + 1} = i + m + 2, ..., p_{n - 1} = n + m$.

但是在程式設計中, 結點中的指向型標記儲存的基本都是記憶體位址, 所以上面的指派操作都應該替換為具體的記憶體位址. 為了讓 $p_{i - 1}$ 指向新的位置, 我們應該將其更新為結點 $(\beta_{1}, p_{n + 1})$ 的記憶體位址; 為了讓前向連結串列保持連結, 還應該讓 $p_{n + m}$ 指向結點 $(\alpha_{i}, p_{i})$ 的記憶體位址. 另外, 對於 $p_{i}, p_{i + 1}, ..., p_{n}$, 在程式設計中是不需要更新的 :

如果假設 $m = 1$, 那麼向前向連結串列中插入元素的時間複雜度和空間複雜度都為 $\Theta(1)$. 事實上, 在 C++ 中, 獲取第 $i$ 個結點 ($0 \leq 1 < n$) 的記憶體位址的時間複雜度通常不是 $\Theta(1)$ 的, 因為我們要從頭部結點開始向後走過 $i$ 個結點才能到達第 $i$ 個結點. 但是, 我們通常不將這個時間考慮到時間複雜度當中 (例如之前已經把第 $i$ 個結點的記憶體位址保存下來了), 我們只考慮真正屬於插入的操作. 如果計入向後走過 $i$ 個結點這種情況, 時間複雜度就會變成 $\Theta(n)$, 我們一般不採用這個說法.

3. 移除

假設我們需要移除前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) : p_{1} = 2, p_{2} = 3, ..., p_{n - 1} = n, p_{n} = \infty \right \}$ 從第 $i$ 個位置開始的 $m$ 個元素 ($1 \leq i \leq n, i + m \leq n$), 我們只需要這樣做 :

1. 令 $p_{i - 1} = i + m + 1$;
2. 回收結點 $(\alpha_{i}, p_{i}), (\alpha_{i + 1}, p_{i + 1}), ..., (\alpha_{i + m}, p_{i + m})$.

同樣地, 對於 $m = 1$, 顯然移除元素操作的時間複雜度和空間複雜度都是 $\Theta(1)$, 我們通常也不將從頭部結點走到第 $i$ 個結點的時間算入時間複雜度. 一般情況下, 如果不考慮回收結點所需要的時間, 那麼從前向連結串列中移除 $m$ 個元素的時間複雜度和空間複雜度都是 $\Theta(1)$.

4. 搜尋和字典比較

在前向連結串列中進行搜尋或者比較兩個前向連結串列是和向量類似的, 因為前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) : p_{1} = 2, p_{2} = 3, ..., p_{n - 1} = n, p_{n} = \infty \right \}$ 經過退化便可以得到向量 $\boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$. 這其中只是尋訪結點的操作和向量不同罷了. 因此, 前向連結串列上的搜尋和字典比較可以參考向量的搜尋和字典比較 (《【資料結構】向量 (順序表)》), 此處不再累贅.

5. 和前向連結串列有關的演算法

在本節中, 我們將會展示一些專門用於前向連結串列的演算法. 由於前向連結串列在記憶體中的結構和向量完全不同, 這也就導致了部分演算法時前向連結串列所專有的. 在本節中, 我們也將見識到遞迴的威力和魅力.

使用類似於 Algorithm 1 這樣的通用演算法來描述那些和前向連結串列有關的演算法是困難的, 因此我們將改用 C++ 程式設計語言進行描述. 另外為了統一起見, 接下來 C++ 程式碼中前向連結串列的結點我們統一定義為 :

struct node {
    int value;
    node *next;
};

5.1 移除第 $k$ 個結點

首先對於一個前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ... \right \}$, 如果我們不知道 $\boldsymbol {\alpha}$ 中有多少個結點, 那麼如果要刪除第 $k$ 個結點 ($1 \leq k \leq n$), 我們首先要尋訪 $\boldsymbol {\alpha}$ 知曉其結點的數量, 然後第二次尋訪至第 $k - 1$ 個結點, 重新設定 $p_{k - 1}$, 並且回收第 $k$ 個結點. 現在如果要求只能尋訪 $\boldsymbol {\alpha}$ 一次, 應該如何做?

我們注意到, 使用遞迴配合一個變數 $i$ 可以對當前走過的結點數量進行計數. 當 $i + 1 = k$ 的時候, 就說明下一個結點是要移除的結點. 我們只需要讓當前結點的指向型標記指向要被移除結點的指向型標記所指向的結點即可 :

Code 1. 移除第 k 個節點
node *remove_kth_implement(node *first, int k, int i) {
    if(first == nullptr) {
        return nullptr;
    }
    if(i + 1 == k) {
        first->next = remove_kth(first->next->next, k, i + 1);
        // erase the next node first->next here
    }else {
        first->next = remove_kth(first->next, k, i + 1);
    }
    return first;
}

void remove_kth(node *first, int k) {
    first = remove_kth_implement(first, k, 0);
}

這樣, 通過一遍尋訪就可以完成第 $k$ 個結點移除, 時間複雜度仍然為 $\Theta(n)$. 而函式 remove_kth_implement 需要遞迴 $n$ 次, 因此需要保存 $n$ 次函式的狀態 (特別是函式的引數), 那麼空間複雜度應該是 $\Theta(n)$.

5.2 合併 $k$ 個有序的前向連結串列

設有 $k$ 個有序的前向連結串列 $\boldsymbol {\alpha}_{1}, \boldsymbol {\alpha_{2}}, ..., \boldsymbol {\alpha}_{k}$, 我們要合併這 $k$ 個前向連結串列為一個前向連結串列 $\boldsymbol {\alpha}$, 並且要求 $\boldsymbol {\alpha}$ 仍然有序. 為了方便討論, 我們統一讓前向連結串列中的元素是升序 (從小到大) 的.

5.2.1 $k = 2$

為了得到最終的解, 我們先考慮一種比較簡單的情形, 即 $k = 2$. 當其中一個前向連接串列為空的時候, 另外一個就是合併結果, 這是比較特殊的情況. 對於一般的情況而言, 我們遞迴地選出兩個前向連結串列頭部中元素較小的結點, 並將選出的那個結點合併到新的連結串列 $\boldsymbol {\alpha}$ 的尾部 :

Code 2. 合併兩個有序的前向連結串列
node *merge(node *list1, node *list2) {
    if(list1 == nullptr) {
        return list2;
    }
    if(list2 == nullptr) {
        return list1;
    }
    node *new_head {};
    if(list1->value < list2->value) {
        new_head = list1;
        new_head->next = merge(list1->next, list2);
    }else {
        new_head = list2;
        new_head->next = merge(list1, list2->next);
    }
    return new_head;
}

設 $\boldsymbol {\alpha}_{1}$ 的長度為 $n$, $\boldsymbol {\alpha}_{2}$ 的長度為 $m$, 那麼合併兩個有序的前向連結串列的時間複雜度為 $\Theta(\min \left \{ n, m \right \})$. 和一遍尋訪移除第 $k$ 個結點類似, 其空間複雜度為 $\Theta(\min \left \{ n, m \right \})$.

5.2.2 $k > 2$

對於 $k > 2$ 這種情況, 我們首先可以想到使用贏者樹 (《【資料結構】樹 – 贏者樹》) 或者堆積 (《【資料結構和演算法】堆積, 堆積排序和優先佇列》) 這樣的資料結構, 每次從樹或者堆積的頭部取出一個元素連結到 $\boldsymbol {\alpha}$ 的尾部.

然而, 分而治之這種演算法的思想 (《【演算法】分而治之》) 同樣也可以用於合併 $k$ 個有序的前向連結串列. 首先我們兩兩合併這些前向連結串列, 現在剩餘的前向連結串列的數量為 $\left \lceil \frac {k}{2} \right \rceil$ 個. 然後繼續進行兩兩合併, 直到 $k = 1$ 為止. 由於兩兩合併前向連結串列是具有並行性的, 我們可以進行並行操作以減少合併所需要的時間, 這個優點是使用贏者樹或者堆積所做不到的.

5.3 $k$ 個一組翻轉前向連結串列

設前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$, $k$ 一組翻轉之後可以得到 :

• 當 $n \mod k = 0$ 且 $\frac {n}{k} = q$ 時, $\displaystyle {\begin {aligned} \boldsymbol {\alpha} = \{ &(\alpha_{k}, p_{k}), (\alpha_{k - 1}, p_{k - 1}), …, (\alpha_{2}, p_{2}), (\alpha_{1}, p_{1}), \\ &(\alpha_{2k}, p_{2k}), (\alpha_{2k - 1}, p_{2k - 1}), …, (\alpha_{k + 2}, p_{k + 2}), (\alpha_{k + 1}, p_{k + 1}), \\ &…, \\ &(\alpha_{qk}, p_{qk}), (\alpha_{qk - 1}, p_{qk - 1}), …, (\alpha_{(q - 1)k + 2}, p_{(q - 1)k + 2}), (\alpha_{(q - 1)k + 1}, p_{(q - 1)k + 1}) \}; \end {aligned}}$
• 當 $n \mod k \neq 0$ 且 $\left \lfloor \frac {n}{k} \right \rfloor = q$ 時, $\displaystyle {\begin {aligned} \boldsymbol {\alpha} = \{ &(\alpha_{k}, p_{k}), (\alpha_{k - 1}, p_{k - 1}), …, (\alpha_{2}, p_{2}), (\alpha_{1}, p_{1}), \\ &(\alpha_{2k}, p_{2k}), (\alpha_{2k - 1}, p_{2k - 1}), …, (\alpha_{k + 2}, p_{k + 2}), (\alpha_{k + 1}, p_{k + 1}), \\ &…, \\ &(\alpha_{(q - 1)k}, p_{(q - 1)k}), (\alpha_{(q - 1)k - 1}, p_{(q - 1)k - 1}), …, (\alpha_{(q - 2)k + 2}, p_{(q - 2)k + 2}), (\alpha_{(q - 2)k + 1}, p_{(q - 2)k + 1}), \\ &(\alpha_{n}, p_{n}), (\alpha_{n - 1}, p_{n - 1}), ..., (\alpha_{(q - 1)k + 1}, p_{(q - 1)k + 1}), (\alpha_{(q - 1)k + 2}, p_{(q - 1)k + 2}) \}. \end {aligned}}$

需要注意的是, 我們不僅僅是交換兩個結點中的元素, 否則結果應該類似於這樣 $\boldsymbol {\alpha} = \left \{ (\alpha_{k}, p_{1}), (\alpha_{k - 1}, p_{2}), …, (\alpha_{2}, p_{k - 1}), (\alpha_{1}, p_{k}), ... \right \}$.

首先, 不考慮 $k$ 個一組, 而是翻轉整個前向連結串列. 這個演算法比較簡單 : 假設當前位於第一個結點 $(\alpha_{1}, p_{1})$, 讓其下一個結點的指向性標記指向第一個結點就可以了, 即 $p_{2} = 1$; 類似地, 令 $p_{3} = 2, p_{4} = 3, ..., p_{n} = n - 1, p_{1} = \infty$, 我們得到了 $\boldsymbol {\alpha} = \left \{ (\alpha_{n}, p_{n}), (\alpha_{n - 1}, p_{n - 1}), ..., (\alpha_{1}, p_{1}) \right \}$. 但是在程式設計中, 當位於第一個結點的時候, 我們還需要保存第三個結點, 以免第二個結點的指向性標記更改之後, 剩餘的前向連結串列丟失 :

Code 3. 翻轉前向連結串列
node *reverse(node *first) {
    node *previous {};
    auto current {first};
    while(current not_eq nullptr) {
        auto backup {current->next};
        current->next = previous;
        previous = current;
        current = backup;
    }
    return previous;        // the new first node
}

對於 $k$ 個一組的翻轉, 我們只需要進行計數, 在第 $k$ 個位置處停止翻轉, 然後遞迴地從第 $k + 1$ 個位置開始繼續翻轉, 利用回傳的新頭部結點, 將首位相連結即可. 如果中間遇到不足 $k$ 個的尾部情況, 直接停止反轉操作.

翻轉整個前向連結串列的時間複雜度是 $\Theta(n)$, 空間複雜度為 $\Theta(1)$. 對於 $k$ 個一組進行的翻轉, 使用了遞迴的方法, 次數為 $\left \lceil \frac {n}{k} \right \rceil$. 因此, 其時間複雜度仍然為 $\Theta(n)$, 空間複雜度為 $\Theta(\left \lceil \frac {n}{k} \right \rceil)$.

現在, 我們提高要求 : 是否可以使用遞迴對前向連結串列進行翻轉? 答案當然是可以的. 我們只需要將前向連結串列一分為二, 然後假設後面那一部分已經完成了翻轉 :

Code 4. 遞迴翻轉前向連結串列
node *reverse(node *first, node *previous, node *&result) {
    if(first->next == nullptr) {
        first->next = previous;
        result = first;
        return previous;
    }
    reverse(first->next, first, result)->next = previous;
    return previous;
}
node *reverse(node *first) {
    if(first == nullptr or first->next == nullptr) {
        return first;
    }
    node *result {};
    reverse(first, nullptr, result);
    return result;
}

遞迴翻轉前向連結串列的時間複雜度仍然為 $\Theta(n)$, 但是遞迴了 $n$ 次, 因此空間複雜度就是 $\Theta(n)$.

在使用遞迴來解決和前向連結串列有關的問題的時候, 我們首先要以解決問題為目標, 而不是一開始就想著降低空間複雜度, 使用更少的變數來解決問題. 於是, 當你想明白上面使用遞迴的解決方案的時候, 自然地, 你會想到下面程式碼會更加簡便 :

Code 5. 更加簡潔地遞迴翻轉前向連結串列
node *reverse(node *first) {
    if(first == nullptr or first->next == nullptr) {
        return first;
    }
    auto r {reverse(first->next)};
    first->next->next = first;
    first->next = nullptr;
    return r;
}

5.4 旋轉

我們在《【資料結構】向量 (順序表)》中提到了向量的旋轉, 現在我們要旋轉前向連結串列. 在向量的旋轉中, 我們了解到旋轉的本質是循環位移, 所以在前向連結串列上, 旋轉變得非常簡單. 以向左旋轉為例, 假設我們對前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$ 向左旋轉 $k$ 個元素 ($1 < k < n$), 我們只需要令 $p_{n} = 1$, 然後令 $p_{k} = \infty$ 即可.

Code 5. 旋轉
node *rotate(node *first, int k) {
    auto previous {first};
    while(--k) {
        previous = previous->next;
    }
    auto end {previous};
    while(end->next) {
        end = end->next;
    }
    end->next = first;
    auto new_first {previous->next};
    previous->next = nullptr;
    return new_first;
}

儘管旋轉需要尋訪整個前向連結串列, 但是如果單純考慮旋轉本身的操作, 那麼其空間複雜度和時間複雜度都是 $\Theta(1)$.

5.5 移除存在重複的元素

設有一個有序的前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$. 不妨設 $\boldsymbol {\alpha}$ 中的元素是升序的, 即有 $\displaystyle {\alpha_{1} \leq \alpha_{2} \leq ... \leq \alpha_{n}}.$ 若在 $\boldsymbol {\alpha}$ 中存在重複的元素, 那麼將重複元素對應的結點全部從前向連結串列中移除. 這個在資料結構中非常簡單, 如果發現 $\alpha_{i} = \alpha_{i + 1} = ... = \alpha_{i + j} < \alpha_{i + j + 1}$, 那麼只需要移除結點 $(\alpha_{i}, p_{i}), (\alpha_{i + 1}, p_{i + 1}), ..., (\alpha_{i + j}, p_{i + j})$, 然後令 $p_{i - 1} = i + j + 1$ 就可以了. 其中, $i \geq 1$ 且 $i + j + 1 \leq n$.

Code 6. 移除重複元素
node *nonrepeatable(node *first) {
    auto before_begin {new node {{}, first}};
    auto current {before_begin};
    while(current->next and current->next->next) {
        if(current->next->value == current->next->next->value) {
            const auto &value {current->next->value};
            auto cursor {current->next->next};
            while(cursor->next) {
                if(cursor->next->value not_eq value) {
                    current->next = cursor->next;
                    /* erase nodes from current->next to cursor */
                    break;
                }
            }
        }else {
            current = current->next;
        }
    }
    auto result {before_begin->next};
    delete before_begin;
    return result;
}

在 Code 6 中, 我們為前向連結串列增加了一個 before_begin 結點, 這是處理前向連結串列的一種技巧. 當演算法可能導致前向連結串列的頭部結點改變的時候, 增加一個 before_begin 結點可以大大簡化程式碼, 並且不增加空間複雜度的級別.

移除前向連結串列中的重複元素需要尋訪整個前向連結串列, 因此時間複雜度為 $\Theta(n)$. 而移除所需要的輔助空間和元素數量無關, 因此空間複雜度為 $\Theta(1)$.

在 Code 6 中, 對於 before_begin 中的元素, 它是沒有被指定的. 現在 node 中儲存的是型別為 int 的值, 它的建構和複製是非常快的. 但是如果 node 中儲存值的建構非常慢, 這就會消耗額外的時間來進行毫無意義的建構操作. 此時, 我們可以將陳述式 auto before_begin {new node {{}, first}} 改為 auto before_begin {static_cast<node *>(::operator new(sizeof(node)))} 或者 auto before_begin {static_cast<node *>(std::malloc(sizeof(node)))}.

5.6 分隔前向連結串列

設有前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$, 給定一個值 $x$, 分隔前向連結串列的要求是所有小於 $x$ 的元素都在大於等於 $x$ 元素的左側. 設分隔處為 $i_{k}$ ($1 \leq k \leq n$), 也就是說分隔之後我們有 $\displaystyle {{\boldsymbol {\alpha}}' = \left \{ (\alpha_{i_{1}}, p_{i_{1}}), (\alpha_{i_{2}}, p_{i_{2}}), ..., (\alpha_{i_{k}}, p_{i_{k}}), (\alpha_{i_{k + 1}}, p_{i_{k + 1}}), (\alpha_{i_{k + 2}}, p_{i_{k + 2}}), ..., (\alpha_{i_{n}}, p_{i_{n}}) \right \}}.$ 其中, $\alpha_{i_{1}} \leq \alpha_{i_{2}} \leq ... \leq \alpha_{i_{n}}$, $i_{1}, i_{2}, ..., i_{n} \in \left \{ 1, 2, ..., n \right \}$ 且 $i_{1} \neq i_{2} \neq ... \neq i_{n}$.

在程式設計中, 要解決這個問題的思路也很簡單, 只需要建立兩個新的頭部結點, 一個用於連結小於 $x$ 的元素結點, 另外一個用於連結大於等於 $x$ 的元素結點. 在分隔結束之後, 把這兩個新結點之後的元素連結起來即可 :

Code 7. 分隔前向連結串列
#include <utility>

std::pair<node *, node *> partition(node *first, int x) {
    if(first == nullptr or first->next == nullptr) {
        return {first, first};
    }
    auto less {new node}, greater {new node};
    auto cursor {first}, less_cursor {less}, greater_cursor {greater};
    do {
        if(cursor->value < x) {
            less_cursor->next = cursor;
            less_cursor = cursor;
        }else {
            greater_cursor->next = cursor;
            greater_cursor = cursor;
        }
        cursor = cursor->next;
    }while(cursor);
    less_cursor->next = greater->next;
    auto less_result {less->next}, greater_result {greater->next};
    delete less;
    delete greater;
    return {less_result, greater_result};       // pair.first is the new first of forward list, pair.second is the partition of forward list
}

分隔前向連結串列需要尋訪全部元素, 所以時間複雜度為 $\Theta(n)$, 所使用的輔助空間數量和元素數量無關, 因此空間複雜度為 $\Theta(1)$.

5.7 環狀前向連結串列

定義 3. 對於前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$, 若 $p_{n} \in [1, n - 1]$, 則稱 $\boldsymbol {\alpha}$ 為環狀前向連結串列 (circular forward list).

判斷一個前向連結串列是否存在環, 一般來說我們可以為每一個結點建立一個紀錄, 如果到達兩次, 就說明這個前向連結串列是環狀的前向連結串列. 但是這個解決方案的空間複雜度為 $\Theta(n)$, 那麼是否有辦法在空間複雜度為 $\Theta(1)$ 的要求下解決這個問題呢?

現在我們介紹另外一個解決前向連結串列問題的技巧 : 快慢指標. 快慢指標的意思是設定兩個指標, 快指標一次向後走兩步, 慢指標一次向後走一步. 對於前項鏈結串列來說, 如果它是環狀的, 那麼這兩個指標必定會相遇 :

Code 8. 判斷環狀前向連結串列
bool is_circular_forward_list(node *first) {
    if(first == nullptr or first->next == nullptr) {
        return false;
    }
    auto fast {first->next}, slow {first};
    do {
        if(fast == slow) {
            return true;
        }
        fast = fast->next->next;
        slow = slow->next;
    }while(fast);
    return false;
}

現在我們提高要求, 在保持空間複雜度為 $\Theta(1)$ 的情況下, 我們要求回傳環開始的結點. 在 Figure 6 的第一個前向連結串列中, 環開始的結點為 $(\alpha_{1}, p_{1})$; 而在第二個前向連結串列中, 環開始的結點為 $(\alpha_{i}, p_{i})$.

假設環外連結串列的長度為 $x$, 環的長度為 $y$. 若慢指標進入環之後, 走了 $d$ 步之後與快指標相遇, 若快指標此時已經走了 $c$ 圈 (即 $cy$ 步), 則快指標此時走過的總距離為 $\displaystyle {x + cy + d}.$ 另外, 在任意時刻, 快指標走過的路程總是慢指標的兩倍, 於是有 $\displaystyle {\begin {aligned} &x + cy + d = 2(x + d) \\ \Rightarrow &x + cy + d = 2x + 2d \\ \Rightarrow &cy = x + d \\ \Rightarrow &x = cy - d \\ \Rightarrow &x = (c - 1)y + y - d \\ \Rightarrow &x = (c - 1)y + (y - d). \end {aligned}}$

在相遇點處, 我們再讓慢指標走 $y - d$ 步, 就到達了環開始的地方. 接著, 我們再讓慢指標圍繞著環走 $c - 1$ 圈, 我們就得到了 $x$ 的具體值. 如果我們在慢指標開始走之前, 再設定一個新指標從前向連結串列的頭部開始走, 當我們得到 $x$ 的具體值時, 新指標和慢指標就會相遇, 這也就是環開始的結點 :

Code 9. 尋找環狀前向連結串列中環的起點
node *is_circular_forward_list(node *first) {
    auto slow {first}, fast {first};
    while(fast) {
        slow = slow->next;
        if(slow == nullptr) {
            return nullptr;
        }
        fast = fast->next->next;
        if(slow == fast) {
            auto cursor {first};
            while(cursor not_eq slow) {
                slow = slow->next;
                cursor = cursor->next;
            }
            return cursor;
        }
    }
    return nullptr;
}

5.8 分岔路口

設有三個前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}, \boldsymbol {\beta} = \left \{ (\beta_{1}, q_{1}), (\beta_{2}, q_{2}), ..., (\beta_{m}, q_{m}) \right \}, \boldsymbol {\gamma} = \left \{ (\gamma_{1}, r_{1}), (\gamma_{2}, r_{2}), ..., \right \}$. 其中, $p_{n}$ 和 $q_{m}$ 都指向 $(\gamma_{1}, r_{1})$.

在程式設計中, 我們要找到 $(\gamma_{1}, r_{1})$ 這個分岔路口.

簡單的方法就是為每一個結點建立檔案, 第一個被尋訪兩次的結點就是分岔路口. 這個演算法的空間複雜度為 $\Omega(m + n)$. 但是我們同樣不滿足於這個簡單的方案, 我們希望找到一個時間複雜度為 $\Theta(m + n)$ 且空間複雜度為 $\Theta(1)$ 的解決方案.

這裡, 我們直接給出演算法 :

1. 若任意一個前向連結串列為空, 則我們可以直接確定不存在分岔路口;
2. 設定兩個指標 $p$ 和 $q$ 分別指向 $(\alpha_{1}, p_{1})$ 和 $(\beta_{1}, q_{1})$;
3. 嘗試讓指標 $p$ 和 $q$ 向後走一步 :
   • 若指標 $p = \infty$, 那麼把指標 $p$ 重新指向 $(\beta_{1}, q_{1})$;
   • 若指標 $q = \infty$, 那麼把指標 $q$ 重新指向 $(\alpha_{1}, p_{1})$;
   • 若指標 $p$ 和 $q$ 相遇, 那麼相遇結點就是分岔路口;
   • 若指標 $p = \infty$ 和 $q = \infty$ 同時成立, 那麼不存在分岔路口.

斷言 1. 由 Algorithm 3 所描述的演算法思路正確.

$證明$ :

設 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$, $\boldsymbol {\beta} = \left \{ (\beta_{1}, q_{1}), (\beta_{2}, q_{2}), ..., (\beta_{m}, q_{m}) \right \}$, $\boldsymbol {\gamma} = \left \{ (\gamma_{1}, r_{1}), (\gamma_{2}, r_{2}), ..., (\gamma_{l}, r_{l}) \right \}$. 顯然, $\boldsymbol {\alpha}$ 中有 $n$ 個結點, $\boldsymbol {\beta}$ 中有 $m$ 個結點, $\boldsymbol {\gamma}$ 中有 $l$ 個結點.

首先假設前向連結串列 $\boldsymbol {\alpha}$ 和 $\boldsymbol {\beta}$ 存在分岔路口, 即 $p_{n}$ 和 $q_{m}$ 同時指向結點 $(\gamma_{1}, r_{r})$ :

• 當 $m = n$ 時, 指標 $p$ 和 $q$ 經過 $n + 1$ 步之後必定會停留在結點 $(\gamma_{1}, r_{1})$, 這也是 $p$ 和 $q$ 首次相遇的地方, 而 $(\gamma_{1}, r_{1})$ 也正是 $\boldsymbol {\alpha}$ 和 $\boldsymbol {\beta}$ 的分岔路口;
• 當 $m \neq n$ 時, 指標 $p$ 和 $q$ 不會同時滿足 $p = \infty$ 且 $q = \infty$. 當某個指標指向了 $\infty$, 它會重新指向到另外一個前向連結串列的頭部結點 ($p$ 指向結點 $(\beta_{1}, q_{1})$, $q$ 指向結點 $(\alpha_{1}, p_{1})$). 此時, 不妨假設 $n < m$, 對於 $n > m$ 的情形我們只需要交換 $\boldsymbol {\alpha}$ 和 $\boldsymbol {\beta}$ 之後類似可證. 當 $n < m$ 時, 指標 $p$ 會首先指向 $\infty$. 這個時候, 指標 $p$ 移動的長度為 $n + l$, 而指標 $q$ 仍然在 $\boldsymbol {\beta} + \boldsymbol {\gamma}$ 中. 下一步, 指標 $p$ 將移動到 $(\beta_{1}, q_{1})$. 為了讓指標 $p$ 移動到分岔路口結點 $(\gamma_{1}, r_{1})$, $p$ 還需要經過 $m$ 個結點. 即指標 $p$ 要到達結點 $(\gamma_{1}, r_{1})$ 總共需要經過 $n + l + m$ 個結點. 接下來, 我們只需要證明經過 $n + l + m$ 個結點之後, 指標 $q$ 也停留在分岔路口結點 $(\gamma_{1}, r_{1})$ 即可. 當指標 $q$ 走過 $m + l$ 個結點之後, $q = \infty$, 那麼下面要將 $q$ 重新指向 $(\alpha_{1}, p_{1})$. 為了讓指標 $q$ 也移動到 $(\gamma_{1}, r_{1})$, 只需要讓 $q$ 再移動 $n$ 個結點即可, 總共經過的結點恰好為 $n + l + m$ 個. 最終, 指標 $p$ 和 $q$ 相遇.

現在假設前向連結串列 $\boldsymbol {\alpha}$ 和 $\boldsymbol {\beta}$ 不存在分岔路口, 即 $p_{n} = q_{m} = \infty$ :

• 當 $m = n$ 時, 指標 $p$ 和 $q$ 經過 $n + 1$ 步之後必定會同時指向 $\infty$. 此時有 $p = q = \infty$, 於是我們可以判定這兩個前向連結串列沒有分岔路口;
• 當 $m \neq n$ 時, 指標 $p$ 和 $q$ 同樣不會同時滿足 $p = \infty$ 且 $q = \infty$. 不妨假設 $n < m$, 對於 $n > m$ 的情形我們只需要交換 $\boldsymbol {\alpha}$ 和 $\boldsymbol {\beta}$ 之後類似可證. 當 $n < m$ 時, 指標 $p$ 會首先指向 $\infty$, 此時 $p$ 經歷了 $n$ 個結點. 下一步, 指標 $p$ 將重新指向 $(\beta_{1}, q_{1})$, 再經過 $m$ 步之後, 再次有 $p = \infty$. 現在來分析指標 $q$. 當指標 $q$ 首次指向 $\infty$ 時, $q$ 經過了 $m$ 個結點, 接下來要將 $q$ 重新指向 $(\alpha_{1}, p_{1})$. 而指標 $q$ 再經過 $n$ 個結點之後, 便再次有 $q = \infty$, 則 $q$ 總共經過了 $m + n$ 個結點之後, $p = q = \infty$ 成立. 最終, 我們可以判定前向連結串列 $\boldsymbol {\alpha}$ 和 $\boldsymbol {\beta}$ 不存在分岔路口.

$\blacksquare$

Code 10. 尋找分岔路口
node *fork_node(node *first_1, node *first_2) {
    if(first_1 == nullptr or first_2 == nullptr) {
        return nullptr;
    }
    auto cursor_1 {first_1}, cursor_2 {first_2};
    while(cursor_1 not_eq cursor_2) {
        if(cursor_1) {
            cursor_1 = cursor_1->next;
        }else {
            cursor_1 = first_2;
        }
        if(cursor_2) {
            cursor_2 = cursor_2->next;
        }else {
            cursor_2 = cursor_2;
        }
    }
    return cursor_1;
}

我們首先分析 Algorithm 3 的空間複雜度. 在演算法的運作過程中, 我們所需要的輔助空間與 $\boldsymbol {\alpha}$ 的結點數量 $n$, $\boldsymbol {\beta}$ 的結點數量 $m$ 以及 $\boldsymbol {\gamma}$ 的結點數量 $l$ 無關, 因此空間複雜度為 $\Theta(1)$. 而在斷言 1 的證明中, 我們發現演算法運作的過程中, 我們至多需要經過 $n + m + l$ 個結點才能讓指標 $p$ 和 $q$ 相遇. 因此, 尋找分岔路口的時間複雜度為 $\Theta(n + m + l)$.

對於某些不明顯的演算法, 當演算法直接給出的時候, 我們需要對這個演算法的正確性進行證明. 當然, 這並不是說對於一些很明顯就能想到的演算法就不需要證明, 只是那些演算法的證明過程通常都是比較簡單的. 以 5.1 節中移除第 $k$ 個結點為例, 當找到第 $k$ 個結點, 並且將 $p_{k - 1}$ 更改為 $k + 1$ 的時候, 前向連結串列就會變成 $\left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{k - 1}, p_{k - 1}), (\alpha_{k + 1}, p_{k + 1}), (\alpha_{k + 2}, p_{k + 2}), ..., (\alpha_{n}, p_{n}) \right \}$. 很顯然, 原前向連結串列中的第 $k$ 個結點已經被移除了. 此時, 證明就完成了.

5.9 使用前向連結串列儲存數字

給定一個非負整數 $k$, 按順序從頭開始將每一位都放入前向連結串列中儲存, 得到 $\mathfrak {N} = \left \{ (n_{1}, p_{1}), (n_{2}, p_{2}), ..., (n_{m}, p_{m}) \right \}$. 例如數字 $517394$, 儲存它的前向連結串列為 $\displaystyle {\mathfrak {N}_{517394} = \left \{ (5, p_{1}), (1, p_{2}), (7, p_{3}), (3, p_{4}), (9, p_{5}), (4, p_{6}) \right \}.}$ 其中, $p_{1} = 2, p_{2} = 3, p_{3} = 4, p_{4} = 5, p_{5} = 6, p_{6} = \infty$.

5.9.1 加一

設 $\mathfrak {N} = \left \{ (n_{1}, p_{1}), (n_{2}, p_{2}), ..., (n_{m}, p_{m}) \right \}$ 儲存了一個數字. 其中, $n_{1} \neq 0$ 且 $n_{1} \neq 9$. 要求一次尋訪將 $\mathfrak {N}$ 這個數字加上一.

解決這個問題的總體方案仍然是遞迴, 因為問題要求我們使用一次尋訪. 總體的思路是檢查下一個結點加一之後會不會超過 $9$, 如果超過的話, 當前結點的數字就需要加一. 依次往復直到第一個結點結束 :

Code 11. 給前向連結串列中儲存的數字加一
int add_one_implement(node *first) {
    if(first->next) {
        if(add_one_implement(first->next) == 1) {
            if(first->value == 9) {
                first->value = 0;
                return 1;
            }
            first->value += 1;
        }
    }else {
        if(first->value == 9) {
            first->value = 0;
            return 1;
        }
        first->value += 1;
    }
    return 0;
}
void add_one(node *first) {
    add_one_implement(first);
}

加一是需要尋訪整個前向連結串列的, 因此加一操作的時間複雜度為 $\Theta(m)$. 而遞迴的次數為 $m$ 次, 因此空間複雜度為 $\Theta(m)$.

如果我們只要求 $n_{1} \neq 0$, 那麼這個時候就需要注意頭部結點可能發生變化. 也就是對於 $999$ 這種數字, 我們還要在前向連結串列的最前面增加一個新的結點, 結點中儲存的數字為 $1$ :

Code 12. 改進 Code 11 中的函式 add_one
node *add_one(node *first) {
    if(add_one_implement(first) == 1) {
        auto new_first {new node {1, first}};
        return new_first;
    }
    return first;
}

5.9.2 兩數相加

現假設有兩個前向連結串列 $\mathfrak {N} = \left \{ (n_{1}, p_{1}), (n_{2}, p_{2}), ..., (n_{u}, p_{u}) \right \}$ 和 $\mathfrak {M} = \left \{ (m_{1}, q_{1}), (m_{2}, q_{2}), ..., (m_{v}, q_{v}) \right \}$ 分別儲存了數字 $x$ 和 $y$. 新的要求是求得 $x + y$ 的值, 並且將其儲存在一個新的前向連結串列中.

這個問題沒有一次尋訪的限制, 我們可以借助第 5.3 節中翻轉操作, 首先翻轉兩個前向連結串列, 然後逐個結點中的元素相加並且考慮進位即可. 這樣, 如果採用空間複雜度為 $\Theta(1)$ 的翻轉操作, 那麼時間複雜度為 $\Theta(\max \left \{ u, v \right \})$, 空間複雜度為 $\Theta(1)$.

5.10 給定正整數 $k$, 分隔前向連結串列

設有前項鏈結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ...) \right \}$, 給定任一正整數 $k$, 將 $\boldsymbol {\alpha}$ 分成 $k$ 個部分, 任意兩個部分的長度相差不超過一個結點.

這個問題沒有要求一次尋訪, 因此我們可以首先通過尋訪來知曉 $\boldsymbol {\alpha}$ 中有多少個結點, 然後將其分為 $\left \{ \left \lfloor \frac {n}{k} \right \rfloor \right \}$ 個部分. 至於在尾部剩下的那些結點, 按順序一個一個分配至前 $k$ 個部分即可. 這樣, 時間複雜度為 $\Theta(n)$, 空間複雜度為 $\Theta(1)$. 如果要求一次尋訪, 那麼我們需要額外 $n$ 個輔助空間用於記錄每一個結點, 此時空間複雜度為 $\Theta(n)$. 其中, $n$ 為前項鏈結串列 $\boldsymbol {\alpha}$ 的長度.

5.11 合併排序

在《【演算法】合併排序法 (Merge Sort)》中, 我們詳細介紹了合併排序法. 現在, 我們要將合併排序法用到前向連結串列上. 對於向量的合併排序法, 我們可能會使用額外的輔助空間來對兩個子向量進行合併. 然而, 如果我們並不想要使用額外的輔助空間, 可以使用插入排序法. 但是這會導致合併排序法的總體時間複雜度上升至 $\Theta(n^{2})$. 在介紹合併排序法的文章中, 我們借助了旋轉的方法, 讓合併排序法的時間複雜度增加限制在了 $O(n\log {n})$ 下, 從而保持了合併排序法的總體時間複雜度仍然為 $\Theta(n\log {n})$.

由於這個資料結構的特殊性, C++ 針對 std::forward_list 和 std::list 都提供了特別為它們排序而制訂的成員函式 sort.

為了簡便起見, 接下來我們所討論的排序都是對元素進行升序排序 (從小到大).

當前向連結串列中沒有結點或者只有一個結點的時候, 前向連結串列並不需要進行排序; 當前向連結串列中有且唯有兩個結點的時候, 排序的時間是 $\Theta(1)$ 的, 只需要比較這兩個結點中的元素, 有必要的話交換兩個結點即可; 對於前項鏈結串列中有超過兩個元素的時候, 我們採用分而治之的思想, 將其不斷一分為二, 直到一個小部分的結點數量少於三個為止 :

Code 13. 合併排序法的排序部分
node *merge_sort(node *first, int size) {
    switch(size) {
        case 0:
            [[fallthrough]];        // since C++ 17, to avoid the compile warning
        case 1:
            return first;
        case 2:
            if(first->next->value < first->value) {
                auto next {first->next};
                next->next = first;
                first->next = nullptr;
                return next;
            }
            return first;
        default:
            break;
    }
    auto left_size {size / 2};
    size -= left_size;     // right_size
    auto mid_node {[](int n, node *first) -> node * {
        for(auto i {0}; i < n; ++i) {
            first = first->next;
        }
        return first;
    }(left_size - 1, first)};
    auto after_mid {mid_node->next};
    mid_node->next = nullptr;
    return merge(merge_sort(first, left_size), merge_sort(mid_node, size));
}

上面程式碼中, 我們沒有實作 merge 函式, 這個函式可以在 5.2.1 節中找到.

合併排序法的時間複雜度我們不在此處再次分析, 對於空間複雜度, 一分為二的操作至多進行 $\left \lceil \frac {n}{2} \right \rceil$ 次, 因此空間複雜度應該是 $\Theta(n)$.

5.12 刪除總和為零的所有結點

從一個數集合中找到一個子集, 使得這個子集中所有數的總和為 $k$, 這是一個 NP 問題 (詳情可見《貪婪演算法》). 這個問題的正確解法比較難, 此處我們不討論. 現在我們減小問題的難度, 令 $k = 0$, 並且若前向連結串列中存在一個負數 $a$, 則必定存在另外一個正數 $-a$, 不需要考慮例如 $a + b + c = 0$ 三個數之和等於零的這種情況.

降低難度之後, 這個問題便變得非常簡單. 我們第一次尋訪前向連結串列只需要為每個結點建立一個紀錄片, 然後再次尋訪, 找到例如 $a + (-a) = 0$ 這樣的結點, 並且從記錄中移除即可. 最後把記錄中仍然留下的結點連結成一個新的前向連結串列即可. 這種解法的時間複雜度和空間複雜度都為 $\Theta(n)$, 因為我們只尋訪了兩次前向連結串列, 並且使用的輔助空間和數量 $n$ 線性相關.

6. 實作

我自己用 C++ 實作了前向連結串列 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/forward_list.hpp, 大家可以參考後自行實作.