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

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, 大家可以參考後自行實作.