各位好，再開始新的章節前，我們先對鏈結串列(Linked List)做一些補充，我們在從Python認識資料結構(三)．陣列與之前的文章中設計了許多動態鏈結串列，也提過鏈結串列的好處是不用提前指定記憶體空間，較靜態結構來說更保有彈性，但在之前的範例我們會發現，鏈結串列也隱藏了一些問題，舉例來說，最明顯的問題就是當我們丟失了head節點時，我們就直接失去了整個串列資料。為了能避免上述問題發生，我們可以設計與過往稍有不同的鏈結串列來處理這個問題。
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
- [email protected]
