【Python基礎教學】鏈結串列【part-14】
===
目錄（Table of Contents）
[TOC]
---
哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。
本次教學繼續替各位補充演算法的相關基礎知識，接下來的實作當中對同學們也許會變得越來越難，而作者將這些基礎演算法的定位、定位在 Python 進階教學當中，主要是因為結合 Python 進行實作。
APCS 實作題中的鏈結串列、佇列、堆疊會比較常出現於觀念題當中，若對於 Python 實作這些資料結構感到不 ok 的同學，或許你也可以理解這些資料結構的概念即可，不過到了動態規劃、貪心演算法等這些實作上常用到的演算法，那麼同學你也就想跑也跑不掉了XD。
接下來，讓我們進入正題：
鏈結串列（linked list）
===
Image Source：[Applications of linked list data structure - GeeksforGeeks](https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/)
以上是鏈結串列（linked list）的結構圖，主要可分為 Head：開頭（or node：之後的都叫節點）、Data（資料區）、Next（or Pointer：指標區，用來指向下一個節點）。
註：一個節點包含資料區與指標區，最開始的節點稱為 Head。
至於最後面的 Null 的意思是空，因為箭頭後面就沒有節點可以讓它讀取了嘛，所以指向 Null，表示鏈結串列的最後一個節點。
那麼鏈結串列（linked list）表面上看起來它是一連串的數據，但其實列表內的數據可能是隨機散佈在記憶體的各個位置的。
而陣列（array）是在記憶體的「連續空間」，跟鏈結串列（linked list）不一樣，它可能散佈在記憶體的各個位置。
以上內容整理如下，應該會比較清晰：
1. 鏈結串列（Linked List）：
* 鏈結串列由一連串的節點（Node）組成，每個節點包含兩個部分：資料區（Data）和指標區（Next or Pointer）。資料區存儲具體的數據，而指標區指向下一個節點。
* 第一個節點稱為 Head，通常用來標記鏈結串列的起點。
* 最後一個節點的指標區指向 Null，表示鏈結串列的結尾，不再有後續的節點。
* 鏈結串列中的節點在記憶體中不是連續分佈的，表示鏈結串列可以散佈在記憶體的不同位置，節點之間的連接是透過指標區來實現的。
2. 陣列（Array）：
* 陣列中的元素在記憶體中是連續分佈的，每個元素在記憶體中的位置是固定的，由陣列的起始地址和元素的索引來計算。
* 陣列的連續分佈讓隨機存取陣列中的元素（透過索引）非常高效。
資料讀取
---
> 鏈結串列讀取資料是使用順序讀取（sequential access）。
例如，以上圖（最上面那個）做舉例：如果要取得 D 資料，則需要從 A 開始經過兩個地方（節點）：B、C 最後才能得到 D 資料。
如果要讀取鏈結串列資料，則需要從頭開始直到結束，時間複雜度為 O(n)。
新資料插入鏈結串列
---
> 在鏈結串列中，如果要在任意位置中新增節點元素，那麼只要將前一個節點指標指向新節點，再將新節點指向下一個節點即可。
同樣以上圖做舉例，如果一開始只有 A、B、C 節點，而 D 節點是作為新資料插入進來的節點。
而這個 D 節點可以由 A、B、C 節點任意接收，也就是 A、B、C 能夠各自指向 D 節點。在這邊比如說 D 節點要在 B、C 之間插入，那麼 B 節點就得指向 D 節點，D 節點再指向 C 節點。
刪除鏈結串列中的節點
---
在鏈結串列中，如果想要刪除某節點元素，那麼就使該節點無法被任意節點「抵達」。
Image Source：[Types of Linked List and Operation on Linked List](https://afteracademy.com/blog/types-of-linked-list-and-operation-on-linked-list/)
上圖是一個鏈結串列刪除某節點的圖示，假設要被刪除的是 15 這個節點，那麼就將前一個節點的連接打斷，節點 10 直接連接到 20 即刪除一個節點，雖然節點 15 還存在於記憶體位址當中。
因為不需要進行遍歷 n 個節點來刪除節點，所以執行時的時間複雜度為 O(1)。
循環鏈結串列（circle linked list）
---
Image Source：[Introduction to Circular Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/circular-linked-list/)
> 在鏈結串列中，具有頭尾觀念，要找尋一個節點必須從頭到尾搜尋，有一個鏈結串列在設計時是將末端節點的指標指向第一個節點。
總之，文字意思就如上圖。
雙向鏈結串列（doubly linked list）
---
如果我們將每個節點多加一個指標區，然後一個指標前後各指向前後的節點，即為一個雙向鏈結串列，如下圖：
Image Source：[Program to find size of Doubly Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/program-find-size-doubly-linked-list/)
這樣子的指標就能夠同時往前往後搜尋了。
陣列 vs. 鏈結串列時間複雜度
---
表格引用自書籍：演算法：圖解邏輯思維+ Python 程式實作王者歸來(第三版)
| 類別 | 陣列 | 鏈結串列 |
| -------- | -------- | -------- |
| 讀取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 刪除 | O(n) | O(1) |
兩種資料結構其實都各有其優缺點，這個就看在不同場合該如何使用了。
Python 實作：鏈結串列
---
首先讓我們建立一個鏈結串列：
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
```
以上是一個節點的各個元素，前面提及過，一個鏈結串列的節點有資料區、指標區，data 即資料區、next 即指標區，用於指向下一個節點。
而 next 由於我們尚未指向某節點時，預設為 None 即 NULL。
而此時我們就可以來定義一個節點了：
```python=
n1 = Node(5)
n2 = Node(10)
n3 = Node(15)
n1.next = n2
n2.next = n3
ptr = n1
while ptr:
print(ptr.data)
ptr = ptr.next
```
上面這段程式碼定義了三節點：n1、n2、n3，由於上面使用的是預設參數 data，所以如果不輸入值進去時 data 預設為 None。
但 n1、n2、n3 都有輸入值，分別為 5、10、15。
接下來就是 n1 指向 n2；n2 指向 n3 了。
而 ptr = n1 是將 ptr 這個指標設定為指向節點 n1，使我們可以透過 ptr 存取到 n1 的數據和下一個節點（即 n2）。
簡單來說，就是建立一個指標節點，以為了接下來存取 n1、n2、n3 的值並列印出來。
然後接下來我們就來建立一個鏈結串列類別，並且遍歷它吧！
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
class Linked_list():
def __init__(self):
self.head = None
def print_list(self):
ptr = self.head
while ptr:
print(ptr.data)
ptr = ptr.next
link = Linked_list()
link.head = Node(5)
n2 = Node(10)
n3 = Node(15)
link.head.next = n2
n2.next = n3
link.print_list()
```
執行結果與上一個例子是一樣的，只是這個印出的區塊被移動到我們新增的類別裡面的方法（print_list()）而已，這樣子的寫法井然有序。
### 插入新節點
---
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
class Linked_list():
def __init__(self):
self.head = None
def print_list(self):
ptr = self.head
while ptr:
print(ptr.data)
ptr = ptr.next
def first(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
link = Linked_list()
link.head = Node(5)
n2 = Node(10)
n3 = Node(15)
link.head.next = n2
n2.next = n3
link.print_list()
print("The new of linked list:")
link.first(100)
link.print_list()
```
以上程式碼在原有基礎下，在類別 Linked_list 新增一個方法名為 first(self, new_data)，作為插入節點的方法，但是這個方法是在開頭時將節點插入。
接下來讓我們看看在中間插入新節點的話該怎麼寫：
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
class Linked_list():
def __init__(self):
self.head = None
def print_list(self):
ptr = self.head
while ptr:
print(ptr.data)
ptr = ptr.next
def first(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def between(self, pre_node, new_data):
if pre_node == None:
return
new_node = Node(new_data)
new_node.next = pre_node.next
pre_node.next = new_node
link = Linked_list()
link.head = Node(5)
n2 = Node(10)
n3 = Node(15)
link.head.next = n2
n2.next = n3
link.print_list()
print("The new of linked list:")
link.between(n2, 100)
link.print_list()
```
以上程式碼同樣在原有基礎下的 Linked_list 類別新增一方法名為 between，裡面有兩參數 pre_node、new_data，pre_node 指的是要插入時的前一個節點。
假設有三節點，要插入 n2 ~ n3 之間，那麼插入後的前一個節點是不是就是 n2，pre_node 就是這個意思。
方法解釋：
首先如果 pre_node 為 None，那麼透過回傳 return 的特性，不回傳任何值但是後續插入動作就不會再繼續進行下去，退出函數。
如果不為 None，就繼續進行插入動作。
在類別 Node() 新增 new_node 節點，資料為 new_data，然後 next_node.next 的指向會是前一個節點 pre_node 所指向的節點，而 pre_node 的節點就改成指向 new_node。
既然有前面跟中間，那麼一定會有後面，所以接下來就是將資料插入到後面去：
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
class Linked_list():
def __init__(self):
self.head = None
def print_list(self):
ptr = self.head
while ptr:
print(ptr.data)
ptr = ptr.next
def first(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def between(self, pre_node, new_data):
if pre_node == None:
return
new_node = Node(new_data)
new_node.next = pre_node.next
pre_node.next = new_node
def tail(self, new_data):
new_node = Node(new_data)
if self.head == None:
self.head = new_node
return
last_ptr = self.head
while last_ptr.next:
last_ptr = last_ptr.next
last_ptr.next = new_node
link = Linked_list()
link.head = Node(5)
n2 = Node(10)
n3 = Node(15)
link.head.next = n2
n2.next = n3
link.print_list()
print("The new of linked list:")
link.tail(100)
link.print_list()
```
tail 方法解釋：
首先，我們創建了一個新節點 new_node，並將其值設定為 new_data。
接著檢查 self.head 是否為空節點（即 None）。如果是，則將 self.head 設定為 new_node，然後直接回傳，結束函數。
如果 self.head 不是空節點，則創建一個指標 last_ptr，並將其設定為 self.head。
然後使用 while 迴圈遍歷整個鏈結串列，直到 last_ptr.next 為空（即 last_ptr 是最後一個節點）。
在迴圈中，將 last_ptr 更新為下一個節點，直到找到最後一個節點。
最後，將最後一個節點的 next 屬性設定為指向 new_node，以將新節點插入到鏈結串列的尾端。
### 移除指定節點
---
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
class Linked_list():
def __init__(self):
self.head = None
def print_list(self):
ptr = self.head
while ptr:
print(ptr.data)
ptr = ptr.next
def first(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def between(self, pre_node, new_data):
if pre_node == None:
return
new_node = Node(new_data)
new_node.next = pre_node.next
pre_node.next = new_node
def tail(self, new_data):
new_node = Node(new_data)
if self.head == None:
self.head = new_node
return
last_ptr = self.head
while last_ptr.next:
last_ptr = last_ptr.next
last_ptr.next = new_node
def rm_node(self, rmkey):
ptr = self.head
if ptr:
if ptr.data == rmkey:
self.head = ptr.next
return
while ptr:
if ptr.data == rmkey:
break
prev = ptr
ptr = ptr.next
if ptr == None:
return
prev.next = ptr.next
link = Linked_list()
link.tail(5)
link.tail(10)
link.tail(15)
link.print_list()
print("The new of linked list:")
link.rm_node(15)
link.print_list()
```
以上程式碼新增了一個方法為 rm_node（remove_node），作用為刪除節點元素。
內部首先創建一個暫時指標 ptr = self.head 指向第一個節點，接下來判斷內判斷 ptr.data == rmkey，是的話就將第一個指標指向下一個節點。（因為一開始要刪除的資料就是 self.head，將 self.head 斷開連結就代表在鏈結串列中刪除資料）
不是的話繼續進到 while 迴圈，看到 prev = ptr 的部分，代表設定暫時指標的前一節點指標，下一行則為將指標移動到下個節點。
為什麼是前一個指標，可以從上下順序看出來，因為在 Python 中是由上往下執行的，在 prev = ptr 這個動作執行完畢後，緊接著執行 ptr = ptr.next 指向下一個節點。而一次迴圈結束後，重新開始一個迴圈時會先進行判斷，才會再執行這兩個動作，所以 prev 可為暫時指標的前一個節點指標。
迴圈外，判斷如果 ptr == None，也就是走到最後為尾巴的地方，因為在走下去就已經沒了，所以就是 None。但不是 None 的話，那麼執行下一行，prev.next = ptr.next，將前一個節點指向下一個節點。
### 循環鏈結串列
---
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
n1 = Node(5)
n2 = Node(10)
n3 = Node(15)
n1.next = n2
n2.next = n3
n3.next = n1 # n3 指標指向 n1
ptr = n1
counter = 1
for i in range(6):
print(ptr.data)
ptr = ptr.next
```
註：循環鏈結串列就是頭接到尾後，尾再接回去到頭，形成一個迴路。
### 雙向鏈結串列
---
由於雙向鏈結串列必須要有向前的指標跟向後的，那麼在於 Node class 的定義，我們可以改成這樣：
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
```
然後接下來才是正題的開始：
```python=
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class Doubly_linked_list():
def __init__(self):
self.head = None
self.tail = None
def add_doubly_list(self, new_node):
if isinstance(new_node, Node):
if self.head == None:
self.head = new_node
new_node.prev = None
new_node.next = None
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
return
def print_list_from_head(self):
ptr = self.head
while ptr:
print(ptr.data)
ptr = ptr.next
def print_list_from_tail(self):
ptr = self.tail
while ptr:
print(ptr.data)
ptr = ptr.prev
doubly_link = Doubly_linked_list()
n1 = Node(5)
n2 = Node(10)
n3 = Node(15)
for n in [n1,n2,n3]:
doubly_link.add_doubly_list(n)
print("print from head:")
doubly_link.print_list_from_head()
print("print from tail:")
doubly_link.print_list_from_tail()
```
與單向鏈結串列不同的是，它除了定義 head 以外，還定義了 tail。新增一個方法名為 add_doubly_list(self, new_node)，裡面首先判斷 new_node 是否屬於 Node 類別的物件，是的話那麼就繼續判斷，判斷 self.head 是否為 None，是的話那麼就進行雙向鏈結串列的一些代碼。
不是 None，則將最後一個節點指向新節點，然後 new_node 的前一個節點指向最後一個節點（達成雙向鏈結串列），而最後一個節點再設置為 new_node。
而後續的方法就只是從頭、還是從尾開始列印而已，相信各位都能直接理解。
總結
===
鏈結串列（Linked list），是線性資料結構、是一連串的數據，但是串列中的數據有可能隨機散佈在記憶體空間裡面。
結構可分為多個節點，然後節點又可分為資料區跟指標區。而第一個節點通常被稱為 head，最後一個節點為 tail。指向「下一個」節點就是 next。
讀取資料：從頭（head）到尾搜尋。與陣列不同，鏈結串列並無隨機存取，用線性搜尋去讀資料，因此其讀取效率較低，平均情況下的時間複雜度為 O(n)。
插入到開頭：將新節點的指標指向當前的 Head，然後將 Head 指向新節點。
插入到結尾：遍歷鏈結串列找到最後一個節點，然後將最後一個節點的指標指向新節點。
插入到中間：找到插入位置前一個節點，調整該節點和新節點的指標。
刪除資料：資料雖然還會在記憶體當中存在，但在鏈結串列中視為被刪除的個體。具體刪除的步驟是將欲刪除資料的連結全部「打斷」，比如說欲刪除資料的前一個節點的指標取消跟當前資料連結，然後連接到當前資料的下一個節點，即為刪除。
循環鏈結串列：頭接尾完後，尾在接回去頭，形成一個迴路循環。
雙向鏈結串列：除了只有「去」，也能夠「回」，簡單來說多兩個箭頭可以互相指向。
好了，那以上是本篇的所有內容，以下是一些參考資料：
參考資料
===
書籍：演算法：圖解邏輯思維+ Python 程式實作王者歸來(第三版)
[Applications of linked list data structure - GeeksforGeeks](https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/)
[Types of Linked List and Operation on Linked List](https://afteracademy.com/blog/types-of-linked-list-and-operation-on-linked-list/)
[Introduction to Circular Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/circular-linked-list/)
[Program to find size of Doubly Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/program-find-size-doubly-linked-list/)
[基礎演算法系列 — 基礎資料結構 Linked-list 與 Array - Recording everything - Medium](https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E5%9F%BA%E7%A4%8E%E6%BC%94%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97-%E5%9F%BA%E7%A4%8E%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-linked-list-%E8%88%87-array-553cb926029f)
[用python實作linked-list. 最近開始重新了解資料結構，並且選擇python作為實作的語言，另外，除了實作出具… | by Tobby Kuo | Medium](https://medium.com/@tobby168/%E7%94%A8python%E5%AF%A6%E4%BD%9Clinked-list-524441133d4d)
Sign in with Wallet
Connect another wallet