## 資結筆記｜鏈結串列（linked list）

### 複習

上次提到了[陣列（array）](https://hackmd.io/@fooox0864/S19qO-681x)這個資料結構，如果還沒看或感興趣的讀者可以去看看唷！

<br/>

### 基本觀念

&emsp;&emsp;<font color="#0000FF">鏈結串列</font>（linked list）表面上也是一串數列，但與陣列不同的地方是，**陣列的資料元素是在記憶體的連續空間，鏈結串列的資料是散落在記憶體的各處**。而我們會將存放資料的地方稱為<font color="#0000FF">節點</font>，每個節點包含2個區塊，一個區塊是<font color="#0000FF">資料區</font>用來存放數據，另一個區塊是<font color="#0000FF">指標區</font>用來指向下一個節點元素。

&emsp;&emsp;下列是一個鏈結串列含有3個節點，要存放的內容為dog、cat、fish，我們來看看這個鏈結串列的外觀，如下圖，

&emsp;&emsp;而實際上，因為鏈結串列是分散在記憶體的各處，所以有可能不是連續排列的，如下圖。但透過指標，可以將分散在各處的資料連結在一起。


<br/>

### 資料讀取

&emsp;&emsp;鏈結串列讀取資料使用的是<font color="#0000FF">循序讀取</font>（sequential access），必須得從頭開始讀取資料。以上面的鏈結陣列舉例，假設要讀取FISH，得先經過DOG->CAT->FISH，按照順序才能取得FISH的資料，因為要跑完整個串列，所以時間複雜度為$O(n)$。

<br/>

### 新增＆刪除節點元素

&emsp;&emsp;在新增節點時，不需要搬動整個串列的資料，只需要將前一個元素的指標指向新元素，並將新元素的指標指向原本的下一個元素。例如我要將APPLE插入CAT和FISH中間，只要先將CAT指向APPLE(CAT->APPLE)，然後再將APPLE指向FISH(APPL->FISH)，即可形成DOG->CAT->APPLE->FISH，新的鏈結串列。

&emsp;&emsp;刪除節點也是同樣的道理，只要將欲刪除的節點的前一個節點的指標，指向下一個節點，讓這個鏈結串列無法走到想刪除的節點，就算完成刪除節點的動作了。

<br/>

### 循環鏈結串列

&emsp;&emsp;在鏈結串列中有頭尾的觀念，搜尋時必須從頭至尾，但如果我們將最尾端的節點指向第一個節點，使它成為一個循環，就稱為<font color="#0000FF">循環鏈結串列</font>。見下圖，這樣設計的好處是不管目前指標示指向哪一個節點，都可以搜尋整個串列，不會因為指到到尾巴而中止。


### 陣列與鏈結串列時間複雜度比較

<br/>

| 時間複雜度比較 | 陣列 | 鏈結串列 |
| ---------- | -------- | -------- |
| 讀取 | $O(1)$ | $O(n)$ |
| 插入 | $O(n)$ | $O(1)$ |
| 刪除 | $O(n)$ | $O(1)$ |

&emsp;&emsp;由上述表格可知，不同的資料結構有各自的優缺點，會影響不同操作的時間複雜度，因此未來在設計程式時，可以根據需求決定要使用哪一種資料結構。
<br/>

### 鏈結串列程式實作

&emsp;&emsp;推薦大家一個實作程式碼可以使用的工具[python tutor](https://pythontutor.com)，不用特別安裝可以及時修改，還可以看到視覺化的資料結構，推薦初學者使用。

<br/>

#### 建立鏈結串列

class Node():
    def __init__ (self, data=None):
        self.data = data                    #資料data
        self.next = None                    #指標pointer
        

p1 = Node(7)                                #節點1
p2 = Node(9)                                #節點2
p3 = Node(11)                               #節點3

p1.next = p2                                #節點1指向節點2
p2.next = p3                                #節點2指向節點3

# 設定頭節點
head = p1

# 輸出鏈結串列的內容
ptr = head
while ptr:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
print("None")                       #移動指標到下一個節點

&emsp;&emsp;可以從上面的程式碼看到Node類別有兩個屬性，data是用來儲存節點的資料，next是用來儲存指標，指標會指向下一個節點。第一個節點為頭節點用head設定，如果陣列結束了就指向None，執行結果如下圖，


<br/>

#### 插入新節點在開頭
&emsp;&emsp;假設我要將一筆資料5插入這個鏈結串列成為新的頭節點，只需要新增一個節點（p0）並指向原本的頭節點（p1），並將新建的節點（p0）指定為新的頭節點。

class Node:
    def __init__(self, data=None):
        self.data = data  # 節點儲存的資料
        self.next = None  # 下一個節點的指標（預設為 None）

# 創建初始的鏈結串列節點
p1 = Node(7)  # 節點1
p2 = Node(9)  # 節點2
p3 = Node(11) # 節點3

# 串接節點
p1.next = p2  # 節點1指向節點2
p2.next = p3  # 節點2指向節點3

# 新增節點到鏈結串列的最前面
p0 = Node(5)  # 新的節點
p0.next = p1  # 新節點指向原本的第一個節點

# 設定新的頭節點
head = p0

# 輸出鏈結串列的內容
ptr = head
while ptr:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
print("None")

執行結果如下圖，

<br/>

#### 插入新節點在中間

&emsp;&emsp;假設我要再新增一筆資料8在節點p1和p2中間，只需要新增一個節點（p4），將p1指向p4，再將p4指向P2則可以完成。

class Node:
    def __init__(self, data=None):
        self.data = data  # 節點儲存的資料
        self.next = None  # 下一個節點的指標（預設為 None）

# 創建初始的鏈結串列節點
p0 = Node(5) 
p1 = Node(7)  # 節點1
p2 = Node(9)  # 節點2
p3 = Node(11) # 節點3

# 新增節點在鏈結串列中間
p4 = Node(8)  # 節點4 

# 串接節點
p0.next = p1
p1.next = p4  # 節點1指向節點4
p2.next = p3  
p4.next = p2  # 節點4指向節點2


# 設定頭節點
head = p0

# 輸出鏈結串列的內容
ptr = head
while ptr:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
print("None")


<br/>

#### 建立循環鏈結串列

&emsp;&emsp;我們要建立一個循環連結只需將p3再指向p0即可，但輸出的時候要加入一個檢查機制，如果回到頭節點了則停止輸出，以避免無窮迴圈。

class Node:
    def __init__(self, data=None):
        self.data = data  # 節點儲存的資料
        self.next = None  # 下一個節點的指標（預設為 None）

# 創建初始的鏈結串列節點
p0 = Node(5)  # 節點0
p1 = Node(7)  # 節點1
p2 = Node(9)  # 節點2
p3 = Node(11) # 節點3

# 新增節點在鏈結串列中間
p4 = Node(8)  # 節點4

# 串接節點
p0.next = p1      # 節點0指向節點1
p1.next = p4      # 節點1指向節點4
p4.next = p2      # 節點4指向節點2
p2.next = p3      # 節點2指向節點3
p3.next = p0      # 節點3指向節點0，形成循環鏈結串列

# 設定頭節點
head = p0

# 輸出循環鏈結串列的內容

ptr = head
while True:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
    if ptr == head:  # 如果回到頭節點，停止遍歷
        break
print(ptr.data, "(回到頭節點)")

以下是輸出結果，