從Python認識資料結構(四)．陣列
更新於 發佈於 閱讀時間約 3 分鐘
各位好，再開始新的章節前，我們先對鏈結串列(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
- clay.jz.huang@gmail.com
參考書目
4會員
8內容數
本專題將以Python程式語言來實作資料結構，依序從陣列(Array)、堆疊(Stack)、佇列(Queue)、樹(Tree)到圖(Graph)，透過不同方式來建立資料結構，並討論部分細節如：建構難度、記憶體空間、效率等等。
留言0
查看全部
你可能也想看
Google News 追蹤
現代社會跟以前不同了，人人都有一支手機，只要打開就可以獲得各種資訊。過去想要辦卡或是開戶就要跑一趟銀行，然而如今科技快速發展之下，金融App無聲無息地進到你生活中。但同樣的，每一家銀行都有自己的App時，我們又該如何選擇呢？(本文係由國泰世華銀行邀約)
今天我會用不同角度帶大家看這款國泰世華CUB
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
在 C 語言中，陣列的大小固定且使用連續記憶體空間，插入新元素可能不便。鏈結串列則提供了靈活性，可以在不需要連續記憶體的情況下，輕鬆插入新節點。本文將探討陣列與鏈結串列各自的特點，並對比它們在插入與查找操作上的 Big O 複雜度，讓讀者瞭解在不同情境下使用的最佳資料結構選擇。
在資料結構與演算法裡，
最簡單的線性資料結構除了list之外就是linked list鏈結串列了。
Linked list又有分為單向Singly linked list 和雙向Doubly linked list
在這篇文章，會從最基礎的Singly linked list開始講起。
定義
Array可以說是各種語言除了基本型別之外，最常用的資料型別與容器之一了。
Array 這種連續格子狀的資料結構，在Python要怎麼表達呢?
建立一個空的陣列
最簡單也最直接的寫法就是
array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
題目敘述 Merge Nodes in Between Zeros
給定一個鏈結串列，合併非零區間的節點(以加總的方式合併)，輸出合併後的鏈結串列。
給定一個Linked list鏈結串列的Head node，
請判斷這條Linked list是否存在環路(Cycle)?
如果有環路，回傳True。
如果沒有，回傳False。
這篇文章，會帶著大家複習以前學過的遞回框架，
並且鏈結串列的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
遞回框架
尋找共通模式(common pattern)，對應到演算法的General case
確立初始條件(initial conditio
題目敘述
題目會給定一個鏈結串列 Linked List的頭部結點，要求我們根據索引的奇偶數重新排列。奇數索引的在前，偶數索引的在後。數的時候，從Head節點的索引=1開始數。
例如:
1 -> 2 -> 3 -> 4 -> 5
重新排列為
1 -> 3 -> 5 -> 2 -> 4
題目敘述
題目會給我們一個鏈結串列的頭部結點Head node，要求我們計算鏈結串列中的Twin sum最大值是多少？
註: Twin Sum的定義就是頭尾結點相對位置相同的，互相配對加總在一起的值。
例如 給定串列= 1 -> 3 -> 2 -> 5 -> 100 -> 8
1, 8 一組
題目敘述
題目會給定我們一條鏈結串列Linked list的起始節點，要求我們刪除Linked List正中央的節點。
註:
正中央的節點，題目定義為索引為floor( 串列長度 / 2 ) 的節點，索引從零(Head Node)出發開始數。
例如
1 -> 2 -> 3 -> 4
鏈結
本文介紹了串列運算式的應用，以及與Lambda匿名函式方法的比較，並提供了程式範例。串列運算式提供了一種簡潔的語法，用於創建、轉換和過濾列表。lambda函式用於創建匿名函式，通常用於簡單的操作。建議在比較複雜的情況下使用一般for迴圈加if來表示。
現代社會跟以前不同了，人人都有一支手機，只要打開就可以獲得各種資訊。過去想要辦卡或是開戶就要跑一趟銀行，然而如今科技快速發展之下，金融App無聲無息地進到你生活中。但同樣的，每一家銀行都有自己的App時，我們又該如何選擇呢？(本文係由國泰世華銀行邀約)
今天我會用不同角度帶大家看這款國泰世華CUB
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
在 C 語言中，陣列的大小固定且使用連續記憶體空間，插入新元素可能不便。鏈結串列則提供了靈活性，可以在不需要連續記憶體的情況下，輕鬆插入新節點。本文將探討陣列與鏈結串列各自的特點，並對比它們在插入與查找操作上的 Big O 複雜度，讓讀者瞭解在不同情境下使用的最佳資料結構選擇。
在資料結構與演算法裡，
最簡單的線性資料結構除了list之外就是linked list鏈結串列了。
Linked list又有分為單向Singly linked list 和雙向Doubly linked list
在這篇文章，會從最基礎的Singly linked list開始講起。
定義
Array可以說是各種語言除了基本型別之外，最常用的資料型別與容器之一了。
Array 這種連續格子狀的資料結構，在Python要怎麼表達呢?
建立一個空的陣列
最簡單也最直接的寫法就是
array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
題目敘述 Merge Nodes in Between Zeros
給定一個鏈結串列，合併非零區間的節點(以加總的方式合併)，輸出合併後的鏈結串列。
給定一個Linked list鏈結串列的Head node，
請判斷這條Linked list是否存在環路(Cycle)?
如果有環路，回傳True。
如果沒有，回傳False。
這篇文章，會帶著大家複習以前學過的遞回框架，
並且鏈結串列的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
遞回框架
尋找共通模式(common pattern)，對應到演算法的General case
確立初始條件(initial conditio
題目敘述
題目會給定一個鏈結串列 Linked List的頭部結點，要求我們根據索引的奇偶數重新排列。奇數索引的在前，偶數索引的在後。數的時候，從Head節點的索引=1開始數。
例如:
1 -> 2 -> 3 -> 4 -> 5
重新排列為
1 -> 3 -> 5 -> 2 -> 4
題目敘述
題目會給我們一個鏈結串列的頭部結點Head node，要求我們計算鏈結串列中的Twin sum最大值是多少？
註: Twin Sum的定義就是頭尾結點相對位置相同的，互相配對加總在一起的值。
例如 給定串列= 1 -> 3 -> 2 -> 5 -> 100 -> 8
1, 8 一組
題目敘述
題目會給定我們一條鏈結串列Linked list的起始節點，要求我們刪除Linked List正中央的節點。
註:
正中央的節點，題目定義為索引為floor( 串列長度 / 2 ) 的節點，索引從零(Head Node)出發開始數。
例如
1 -> 2 -> 3 -> 4
鏈結
本文介紹了串列運算式的應用，以及與Lambda匿名函式方法的比較，並提供了程式範例。串列運算式提供了一種簡潔的語法，用於創建、轉換和過濾列表。lambda函式用於創建匿名函式，通常用於簡單的操作。建議在比較複雜的情況下使用一般for迴圈加if來表示。