從Python認識資料結構(四)．陣列

4-1、單向鏈結串列 vs. 環形鏈結串列

這邊我們要先清楚的區分單向鏈結串列(Single Linked List)與環形鏈結串列(Circular Linked List)的差異，過往我們所介紹的功能實作方法都是建立單向鏈結串列，由首節點head出發，最後一個節點的next屬性指向None；環形鏈結串列則是將最後一個節點的next屬性指向head，如此一來，就算我們丟失了head節點，也可以從串列中的任何一個節點找回所有資料，避免了單向鏈結串列會造成的問題，如下圖。

環形鏈結串列的走訪有一個部分要提醒的是，通常在單向鏈節串列中，while回圈內判斷的中止條件都是(ptr != None)，這是因為單向鏈結串列最後一個節點的next屬性為None，當ptr等於None時，也代表我們正處於最後一個節點位置。環形鏈結就有所不同，環形鏈結最後一個節點的next屬性指向了head，如果我們依舊採用等於None來作為判斷跳出的條件，那麼迴圈將不停地重複，所以我們將終止條件設定為(ptr != head)，來確保我們完成了一趟環形鏈結串列的走訪。

---

4-2、單向鏈結串列 vs. 雙向鏈結串列(Double Linked List)

既然有單向鏈結串列，肯定也有雙向的鏈結串列。無論是單向鏈結串列，或是剛剛提到的環形鏈結串列，不難發現其都是依照順序向右(如4-1圖示)尋找下一個節點位置，此時若發生鏈結斷裂，可能是丟失或被錯誤賦值，就會使得整個單向鏈結串列資訊遺失。為了避免此情況，我們可以設計雙向鏈結串列，此串列不僅向右邊鏈結，同時也向左鏈結前位節點位置，如此一來，即使節點其中一個鏈節斷裂，也可以透過另一條鏈結重新建立起節點順序。

雙向與環形兩者不衝突，下圖是由4-1所設計的環形鏈結串列結構修改後的環形雙向鏈結串列，同時保持了環形與雙向鏈結的特色：最後一個節點的next屬性指向head，以及具有兩方向的鏈結，分別指向前一個與後一個節點位置。

相較於單向鏈結串列，雙向鏈結串列雖避免了鏈結丟失的問題，但同時也需要更多的記憶體空間來儲存前位節點位置，實際上使用仍須根據資料的型態來決定使用哪種資料結構。

以下是透過手動方式設計雙向鏈結串列的方式，雙向鏈結的走訪可由head或最後一個節點當開頭，根據next或previous屬性找到下一個節點位置。至於新增、刪除或修改雙向鏈結串列的方式，就留給各位自己實做看看，與單向鏈結串列方式雷同，只是需要注意不要遺失前位節點的資料即可。

以上部分就是Python中建立陣列的方式介紹，順便多介紹了環形鏈結串列與雙向鏈結串列，下一節我們會介紹新的資料結構-堆疊(Stack)，有任何問題歡迎寄信至我的信箱或於底下留言和我討論。

• Institute of Education, NYCU
• clay.jz.huang@gmail.com

---

參考書目

1. 圖解資料結構 - 使用Python(第二版)
2. 圖書演算法 - 使用Python
3. Python3 物件導向程式設計 第二版
4. 精通Python (第二版)