摘要訊息 : 連結串列是前向連結串列的擴展, 它允許我們在尋訪的時候向後倒退.

0. 前言

對於前向連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, p_{1}), (\alpha_{2}, p_{2}), ..., (\alpha_{n}, p_{n}) \right \}$, 在《【資料結構】前向連結串列》中, 它只有一個向後的指向型標記. 因此, 我們在尋訪前向連結串列的時候, 只能向前進, 而不可以倒退. 連結串列是加強型的前向連結串列, 它允許尋訪的時候向後倒退.

更新紀錄 :

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

閱讀提示 : 部分在《【資料結構】前向連結串列》中介紹過的細節我們在這篇文章中不再累贅, 如果閣下沒有學習過前向連結串列, 請優先學習前向連結串列.

1. 定義

定義 1. 我們稱向量 $\boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$ 的擴展 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, \overrightarrow {p_{1}}, \overleftarrow {p_{1}}), (\alpha_{2}, \overrightarrow {p_{2}}, \overleftarrow {p_{2}}), ..., (\alpha_{n}, \overrightarrow {p_{n}}, \overleftarrow {p_{n}}) \right \}$ 為連結串列 (list), 又稱為雙向連結串列 (bidirectional list). 其中, $\overrightarrow {p_{i}}$ 是後指向的指向型標記, $\overleftarrow {p_{i}}$ 是前指向的指向型標記, $i = 1, 2, ..., n$.

指向型標記的定義見《【資料結構】前向連結串列》第 1 節.

在前向連結串列中, 我們通常習慣設定 $p_{n} = \infty$, 而在連結串列中, 我們習慣設定 $\overrightarrow {p_{n}} = 1$ 且 $\overleftarrow {p_{1}} = n$.

2. 插入

在前項連結串列中, 插入操作只需要更新 $p_{i}$ 即可, 但是由於連結串列中有兩個指向型標記, 所以這兩個指向型標記都需要進行更新. 假設我們在連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, \overrightarrow {p_{1}}, \overleftarrow {p_{1}}), (\alpha_{2}, \overrightarrow {p_{2}}, \overleftarrow {p_{2}}), ..., (\alpha_{n}, \overrightarrow {p_{n}}, \overleftarrow {p_{n}}) \right \}$ 的第 $i$ 個位置插入 $m$ 個元素 $\beta_{1}, \beta_{2}, ..., \beta_{m}$. 其中, $1 \leq i \leq n$. 插入操作可以描述為 :

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

但是在程式設計中, 結點中的指向型標記儲存的基本都是記憶體位址, 所以上面的指派操作都應該替換為具體的記憶體位址. 另外, 我們需要將 $\overrightarrow {p_{i - 1}}$ 指向新的結點 $(\beta_{1}, \overrightarrow {p_{n + 1}}, \overleftarrow {p_{n + 1}})$, 還需要將 $\overleftarrow {p_{i}}$ 指向 $(\beta_{m}, \overrightarrow {p_{n + m}}, \overleftarrow {p_{n + m}})$.

和前向連結串列類似, 雖然向連結串列中插入元素會比前向連結串列插入元素要慢一些, 當 $m = 1$ 的時候, 單純插入一個元素操作的時間複雜度仍然是 $\Theta(1)$, 空間複雜度也是 $\Theta(1)$ 的. 這裡, 我們同樣忽略了可能的尋訪操作.

3. 移除

同樣地, 從連結串列中移除元素不僅要更新向後的指向型標記, 也需要更新向前的指向型標記. 假設我們要移除連結串列 $\boldsymbol {\alpha} = \left \{ (\alpha_{1}, \overrightarrow {p_{1}}, \overleftarrow {p_{1}}), (\alpha_{2}, \overrightarrow {p_{2}}, \overleftarrow {p_{2}}), ..., (\alpha_{n}, \overrightarrow {p_{n}}, \overleftarrow {p_{n}}) \right \}$ 第 $i$ 個位置起的 $m$ 個元素 ($i \geq 1$ 且 $i + m \leq n$), 具體的步驟是這樣 :

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

對於 $m = 1$ 的情況, 從連結串列中移除元素的時間複雜度和空間複雜度都是 $\Theta(1)$. 對於移除, 我們也是和插入操作一樣不將可能的尋訪考慮進時間複雜度中.

4. 搜尋和字典比較

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

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

所有和前項連結串列有關的演算法同樣可以用在連結串列上, 只是現在我們可能還需要考慮更新前指向的指向型標記. 因此, 所有演算法都可以參考《【資料結構】前向連結串列》第 5 節, 此處不再累贅.

6. 實作

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