上一篇練習的單向鏈結串列，每個節點存放資料，並用 next 記住下一個節點的位置。從 head 出發，就能沿著 next 逐一找到後面的節點，直到最後的 NULL。

如果想從目前位置直接往回走，或讓走到尾端的串列重新回到開頭，就要改變節點之間的連接方式。今天比較四種串列。可以先記住兩個問題：能往哪個方向走？走到尾端會遇到 NULL，還是回到開頭？

以下用 10、20、30 三個節點示範。圖中的箭頭表示指標指向，不表示節點在記憶體中實際排列的位置。

單向鏈結串列：沿著 next 往後走

單向串列的每個節點只有 next，尾端以 NULL 表示沒有下一個節點：

head → 10 → 20 → 30 → NULL

從 10 開始，依序可以找到 20 和 30。假如現在在 30，想回到 20，節點本身沒有記錄前一個位置；必須回到 head，再走一次才能找到 20。這種結構簡單，適合只需要依序往後處理資料的情況。

單向環狀鏈結串列：尾端接回開頭

單向環狀串列一樣只能沿著 next 往後走，差別是尾節點的 next 不再是 NULL，而是指回第一個節點：

從 10 出發，走訪順序是 10、20、30，接著又回到 10。這種串列適合需要輪流處理的情況，例如依序輪到不同項目，再從頭開始。

因為環狀串列不會自然遇到 NULL，走訪時要改用「回到起點就停止」的條件。否則程式會一圈又一圈地走下去。串列是空的時，也要先檢查 head 是否為 NULL，避免嘗試走訪不存在的節點。

雙向鏈結串列：可以往前也可以往後

雙向串列的每個節點多存一個 prev，用來記住前一個節點；next 則記住下一個節點。線性雙向串列的頭尾仍以 NULL 結束：

從 head 沿著 next 可以讀到 10、20、30。圖中另外用 tail 記住尾節點，因此也能從 tail 沿著 prev 讀到 30、20、10。假如手上已經有節點 30 的位置，就能直接沿著 prev 找到 20，不必回到開頭重走。

多了 prev，每個節點需要多存一個指標；插入或刪除節點時，也要同時照顧前後兩邊的連線。可以把它想成每個節點不只留下「下一站」的地址，也留下「上一站」的地址：回頭方便一些，但需要多保存資訊。

雙向環狀鏈結串列：兩個方向都能繞回來

雙向環狀串列同時有 prev 和 next，而且尾端會接回開頭：

沿著 next 從 10 出發，會走到 20、30，再回到 10；沿著 prev 從 10 出發，則會走到 30、20，再回到 10。它適合需要反覆循環，而且可能要往前或往後切換方向的情況。

如果環狀串列只有一個節點，該節點的 next 會指向自己；雙向環狀串列的 prev 也會指向自己。這是因為這個節點的前一個和下一個，都是它自己。

四種串列的差異

「單向或雙向」描述節點能直接往哪些方向移動；「一般或環狀」描述走到尾端後會發生什麼事。這兩個特性可以自由組合，所以環狀串列不一定是雙向串列，雙向串列也不一定是環狀串列。

插入與刪除時，差在哪裡？

假設要在 20 和 30 之間插入 25。單向串列要讓 25 指向 30，再讓 20 指向 25；雙向串列除了這兩條連線，還要讓 25 的 prev 指向 20，並讓 30 的 prev 指向 25。雙向串列能往回走，但更新節點時也要顧到反方向的連線。

刪除時也有差別。若要從 10 → 20 → 30 移除 20，單向串列需要知道它前面的節點 10，才能讓 10 直接指向 30。雙向串列若已經找到 20，就能沿著 prev 找到 10，再接好前後兩邊。環狀串列在修改頭尾時，還要記得維持尾端接回開頭的關係。

走訪與操作要花多少時間？

假設 n 代表串列中的節點數。要從頭找到某個還不知道位置的節點，四種串列通常都得沿著鏈結逐一尋找，最壞會檢查 n 個節點，時間複雜度是 O(n)。環狀只改變尾端的連接方式，不會讓搜尋自動變快。

如果已知要插在哪個節點後面，修改附近的鏈結只需固定幾步，時間是 O(1)。刪除單向串列的節點時，通常還要知道它的前一個節點；若得從頭尋找前一個節點，總時間仍可能是 O(n)。雙向串列可透過 prev 直接找到前一個節點，但每個節點要多存一個指標。

小結

分辨四種鏈結串列時，先看節點有沒有 prev，再看尾端是指向 NULL 還是接回開頭。方向決定能不能直接往回走，是否成環則決定走訪要在哪裡停止。

今日重點：

• 單向節點有 next；雙向節點另外有 prev，可以直接往回走。
• 一般串列走到 NULL 停止；環狀串列走一圈回到起點時停止。
• 環狀串列走訪時要設好停止條件，避免無限繞圈。
• 四種串列搜尋指定節點通常都要逐一走訪，最壞時間為 O(n)。
• 單向串列刪除節點時通常需要前一個節點；雙向串列可沿 prev 直接找到它。

下一篇將進入堆疊的世界，認識 push、pop、peek，並用「後進先出」理解資料進出的順序。