2022-08-09|閱讀時間 ‧ 約 4 分鐘

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

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

4-1、單向鏈結串列 vs. 環形鏈結串列
這邊我們要先清楚的區分單向鏈結串列(Single Linked List)與環形鏈結串列(Circular Linked List)的差異,過往我們所介紹的功能實作方法都是建立單向鏈結串列,由首節點head出發,最後一個節點的next屬性指向None;環形鏈結串列則是將最後一個節點的next屬性指向head,如此一來,就算我們丟失了head節點,也可以從串列中的任何一個節點找回所有資料,避免了單向鏈結串列會造成的問題,如下圖。
單向鏈結串列 vs. 環形鏈結串列
環形鏈結串列的走訪有一個部分要提醒的是,通常在單向鏈節串列中,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),有任何問題歡迎寄信至我的信箱或於底下留言和我討論。

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

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.