---
# System prepended metadata

title: 【考試向】資料結構筆記（鏈結串列）
tags: [資料結構, 程式設計, 電腦]

---

# 【考試向】資料結構筆記（鏈結串列）

[TOC]

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

## 單向鏈結串列（Singly Linked list）

一般的陣列會在**連續**的記憶體空間中儲存資料。

鏈結串列可將資料儲存在**不連續**（non-contiguous）的記憶體空間中。

連續的壞處：

- 在中間插入需要將後面的元素各移動一格。
- 做刪除操作也要將後面元素往前補上去。

而在鏈結串列只需要改變指標指向就可以做到插入、刪除的操作。

在存取元素方面，陣列只需 $O(1)$ ，因為有 index，而鏈結串列需要 $O(n)$ ，因為要從頭一個一個找。

### 陣列 v.s. 鏈結串列

|  | 陣列（Array） | 鏈結串列（Linked-list） |
| -------- | -------- | -------- |
| 記憶體空間 | 連續 | 不連續 |
| 大小 | 固定 | 動態 |
| 插入/刪除操作 | 慢（要移動後面的所有資料） | 快（只需改變指標指向） |
| 讀取資料 | $O(1)$ | $O(n)$ |

### 組成的基本要素

鏈結串列由數個節點（node）組成，一個節點又由以下兩者組成：

- 資料（data）
- 指標（pointer / next）

每一個節點都由指標做串聯。

而節點可以寫成如下程式碼：

```c=
struct Node{
    int data;
    struct Node* next;
};
```

![singly linked list](https://hackmd.io/_uploads/Sk5s24Y4Zl.png)

Image Source：[Advantages and Disadvantages of Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/advantages-and-disadvantages-of-linked-list/)

圖中的文字解釋：

- Head（頭指標）：指向**第一個**節點的位址，通常這個節點不會放資料。
- Null（空）：**最後一個**節點的指標指向 NULL（或 nullptr），表示後面沒有任何節點，這裡是終點。

### C 程式實作：建立基本鏈結串列

`#include <stdlib.h>` 用於 `malloc()` 以及 `free()`。

在大家非常熟悉的 C++ 是用 `new` 做動態記憶體配置，但在 C 語言裡面呢，用的是 `malloc()`（英文全名：Memory Allocation）來做配置。

而 C++ 釋放記憶體用 `delete`，在 C 就變成 `free()`。

- `void *malloc(size_t size);`
    - 回傳新空間第一個位元組的記憶體位址，配置的空間處於尚未初始化的狀態。
- `void free(void *ptr);`
    - 用於釋放先前用 `malloc()` 配置的記憶體。

以下程式碼有一行 `(struct Node*)malloc(sizeof(struct Node));`。

首先看 `sizeof(struct Node)`，這行主要是要先知道 Node 佔了多少 bytes，知道後給 `malloc()` 去配置這些 bytes 的記憶體。

`(struct Node*)` 是顯式型態轉換，因為 `malloc()` 回傳的型態是 `void*`，要把他轉成 `(struct Node*)`。

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node* next;
};

int main(){
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    
    if (head == NULL || second == NULL || third == NULL){
        return 1;
    }
    
    head -> data = 10;
    second -> data = 20;
    third -> data = 30;
    
    head -> next = second;
    second -> next = third;
    third -> next = NULL;
    
    struct Node* curr = head; // 用於讀取跟遍歷用
    
    printf("Linked list content : ");
    while (curr != NULL){
        printf("%d -> ", curr -> data);
        curr = curr -> next; // 指向下一個節點
    }
    printf("NULL\n");
    
    // 最後記得釋放記憶體
    // 否則會 leak memory 非常的危險
    free(head);
    free(second);
    free(third);
    
    return 0;
}
```

### 插入操作

預設以下三樣操作的初始圖都長這樣：

![singly linked list initalization](https://hackmd.io/_uploads/ryZk0rKVZx.png)

三個節點下面那個節點是新節點，準備要插入的。

#### 插入至最前面

建立了新節點 D 準備插入至最前面。

讓 D 節點指向 A 節點：

![singly linked list join 1](https://hackmd.io/_uploads/SJmckLY4bg.png)

接著把 Head 移到 D 上即可：

![singly linked list join 2](https://hackmd.io/_uploads/SJdpkUtEZx.png)

#### 插入至最後

建立了新節點 D 準備插入至最後面，由於是末端，因此 D 需要指向 NULL，如圖：

![singly linked list join 3](https://hackmd.io/_uploads/S1h3eUtN-l.png)

接著把 C 從原本指向 NULL 改成指向 D：

![singly linked list join 4](https://hackmd.io/_uploads/ByqJ-IFV-l.png)

#### 插入至某節點後方

假設要將新建立的 D 節點插入在 A 節點後方，首先要將 D 節點指向 B：

![singly linked list join 5](https://hackmd.io/_uploads/BJIoZUtNWg.png)

接著把 A 節點改指向 D：

![singly linked list join 6](https://hackmd.io/_uploads/Skd5MLYEWg.png)

就完成插入了。

### 刪除操作

假設接下來的三個操作的初始圖都是：

![singly linked list initialization for delete operation](https://hackmd.io/_uploads/BJGMQUYEbx.png)

#### 刪除最前面

先用一個臨時指標 `temp` 指向 A 節點，因為等下 Head 要移走，怕找不到 A 來釋放。

![singly linked list delete 1](https://hackmd.io/_uploads/HybF7ItNWg.png)

之後將 Head 指向 B 節點：

![singly linked list delete 2](https://hackmd.io/_uploads/HkbEBLtNWg.png)

最後釋放 temp 指向的記憶體，即可完成。

#### 刪除尾端

首先用 `temp` 臨時指標，指向最後一個節點，以便後續做釋放。

![singly linked list delete 3](https://hackmd.io/_uploads/r1dsgDK4-x.png)

接著在倒數第二個節點 B，改指向 NULL：

![singly linked list delete 4](https://hackmd.io/_uploads/HJg0xvtEWl.png)

最後釋放掉 temp，即將 C 給刪除了。

#### 刪除特定節點

假設要刪除節點 B，一樣先用 `temp` 臨時指標指向要刪除的節點 B。

![singly linked list delete 5](https://hackmd.io/_uploads/SJ34-PF4Zx.png)

接著將節點 A 的指標指向節點 C：

![singly linked list delete 6](https://hackmd.io/_uploads/Hyw5ZvKEbx.png)

最後釋放掉 `temp`，就會順便把 B 給刪了。

### C 程式實作：插入操作

以下程式實作出三種插入操作：插入到最前面、最後面、某節點後面。

當中 `struct Node** head` 是為了要修改 `head` 本身，如果只用一顆星 `struct Node* head`，傳進去的只是副本，沒有辦法改到函式外的那個 `head`。

`struct Node** head` 是把 `head` 指標的地址傳進去，讓函式可以直接修改外面的 `head` 變數。

`struct Node* createNode(int data)` 是為了把建立節點麻煩的步驟包裝成一個函式，以便後續操作。

注意到 `push_front(&head, data)` 跟 `push_back(&head, data)` 這兩個都用 `head` 的位址傳進去。

如果不傳位址進去，函式裡面的 `head` 換成了新節點，但 main 函式裡的 `head` 還指著舊的 `head`。

而 `push_back(&head, data)` 的考量是假設鏈結串列是空的（`NULL`），此時頭尾都一樣，需要修改到 `head`。

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = data;
    newNode -> next = NULL;
    return newNode;
}

void push_front(struct Node** head_ref, int new_data){
    struct Node* new_node = createNode(new_data);
    new_node -> next = (*head_ref);
    (*head_ref) = new_node;
}

void push_back(struct Node** head_ref, int new_data){
    struct Node* new_node = createNode(new_data);
    
    if (*head_ref == NULL){
        *head_ref = new_node;
        return;
    }
    
    struct Node* last = *head_ref;
    while (last->next != NULL){
        last = last->next;
    }
    last->next = new_node;
}


void insert_after(struct Node* prev_node, int new_data){
    if (prev_node == NULL) {
        printf("error : 指定的前一個節點是 NULL\n");
        return;
    }
    
    struct Node* new_node = createNode(new_data);
    
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main(){
    struct Node* head = NULL;
    
    push_back(&head, 10);
    printList(head);
    
    push_back(&head, 20);
    printList(head);
    
    push_front(&head, 5);
    printList(head);
    
    insert_after(head->next, 15);
    printList(head);
    
    return 0;
}
```

Output：

```
10 -> NULL
10 -> 20 -> NULL
5 -> 10 -> 20 -> NULL
5 -> 10 -> 15 -> 20 -> NULL
```

三種插入操作時間複雜度：

1. 插入至最前面： $O(1)$
2. 插入至最後面： $O(n)$（無尾指標，需慢慢找） / $O(1)$（有尾指標）
3. 插入至特定節點後方： $O(1)$ （已知節點） / $O(n)$ （未知節點，要先找）

### C 程式實作：刪除操作

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = data;
    newNode -> next = NULL;
    return newNode;
}

void delete_front(struct Node** head_ref){
    if (*head_ref == NULL){
        printf("串列為空，無法刪除\n");
        return;
    }
    
    struct Node* temp = *head_ref;
    
    *head_ref = (*head_ref) -> next;
    
    free(temp);
}

void delete_back(struct Node** head_ref){
    if (*head_ref == NULL){
        printf("串列為空，無法刪除\n");
        return;
    }
    // 假設只有一個節點
    if ((*head_ref)->next == NULL){
        free(*head_ref);
        *head_ref = NULL;
        return;
    }
    // 尋找倒數第二個節點
    struct Node* second_last = *head_ref;
    while (second_last->next->next != NULL){
        second_last = second_last->next;
    }
    
    free(second_last->next); // 釋放倒數第二節點的下一個
    second_last->next = NULL;
}


void delete_node(struct Node** head_ref, int key){
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;
    
    if (temp != NULL && temp->data == key){
        *head_ref = temp->next;
        free(temp);
        return;
    }
    
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) {
        printf("找不到數值 %d，刪除失敗\n", key);
        return;
    }
    
    prev->next = temp->next;
    
    free(temp);
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    head->next->next->next = createNode(40);
    
    printList(head);

    delete_front(&head);
    printList(head);

    delete_back(&head);
    printList(head);

    delete_node(&head, 20); 
    printList(head);
    
    delete_node(&head, 99);
    
    delete_node(&head, 30);
    printList(head);

    return 0;
}
```

Output：

```
10 -> 20 -> 30 -> 40 -> NULL
20 -> 30 -> 40 -> NULL
20 -> 30 -> NULL
30 -> NULL
找不到數值 99，刪除失敗
NULL
```

三種刪除操作時間複雜度：

- 刪除最前面： $O(1)$
- 刪除最後面： $O(n)$ （需尋找尾端）
- 刪除指定節點： $O(n)$ （需尋找欲刪除節點的前一個節點） / $O(1)$ （已知欲刪除節點的前一個節點）

### 兩單向鏈結串列串接

假設兩串列 A, B 長以下圖那樣：

![singly linked list concatenate 1](https://hackmd.io/_uploads/S12aQPo4We.png)

想要做 A + B 的串接的話，只需要將 A 的最後一個節點指向 B 的開頭即可。

![singly linked list concatenate 2](https://hackmd.io/_uploads/ryv44DsVWx.png)

### C 程式實作：兩單向鏈結串列串接

需要考慮 Edge Case（特殊情況）：

1. List A 是空的（NULL）：直接把 Head A 指向 Head B。
2. List B 是空的（NULL）：什麼都不用做。

串接操作：從 List A 的頭開始走，走到尾端後，把 A 的 .next 指向 B 的開頭即可。

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = data;
    newNode -> next = NULL;
    return newNode;
}

void concatenate(struct Node** headA_ref, struct Node* headB){
    if (*headA_ref == NULL){
        *headA_ref = headB;
        return;
    }
    if (headB == NULL){
        return;
    }
    
    struct Node* curr = *headA_ref;
    
    while (curr -> next != NULL){
        curr = curr -> next;
    }
    
    curr->next = headB;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* headA = NULL;
    struct Node* headB = NULL;

    headA = createNode(10);
    headA->next = createNode(20);

    headB = createNode(30);
    headB->next = createNode(40);

    printf("串接前 List A: ");
    printList(headA);
    printf("串接前 List B: ");
    printList(headB);

    concatenate(&headA, headB);

    printf("-----------------\n");
    printf("串接後 List A: ");
    printList(headA);

    return 0;
}
```

Output：

```
串接前 List A: 10 -> 20 -> NULL
串接前 List B: 30 -> 40 -> NULL
-----------------
串接後 List A: 10 -> 20 -> 30 -> 40 -> NULL
```

時間複雜度： $O(n)$ （需尋找 A 串列的尾端）

### 反轉單向鏈結串列：三指標法

需用到三個變數，可稱其為三指標：

- `curr`：表示當前節點。
- `prev`：表示前一個節點。
- `next`：表示下一個節點。

反轉原理：假設串列是：`10 -> 20 -> 30 -> NULL`，以第一輪迴圈 10 開始。

1. 做備份：用 `next` 記住 `20` 的位置。
2. 反轉：用 `10` 的 `next` 指向 `prev`（`NULL`），此時 `10 -> NULL`。
3. 前進：將所有節點往後一格，此時 `prev = 10`, `curr = 20`。

接著以此類推。

### C 程式實作：反轉單向鏈結串列

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = data;
    newNode -> next = NULL;
    return newNode;
}

void reverse(struct Node** head_ref){
    struct Node* prev = NULL;
    struct Node* curr = *head_ref;
    struct Node* next = NULL;
    
    while (curr != NULL){
        next = curr->next;
        curr->next = prev;
        
        prev = curr;
        curr = next;
    }
    
    *head_ref = prev;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main(){
    struct Node* head = NULL;
    
    head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    head->next->next->next = createNode(40);
    
    printf("原串列:\n");
    printList(head);

    reverse(&head);

    printf("反轉後的串列:\n");
    printList(head);
    
    return 0;
}
```

時間複雜度： $O(n)$

## 雙向鏈結串列（Doubly Linked List）

與單向鏈結串列的差別是，單向只能往前走，不能往後走，而雙向可以在任意節點選擇要往前還是往後，如圖：

![Doubly Linked List](https://hackmd.io/_uploads/HJACHdoVZe.png)

Image Source：[Operations of Doubly Linked List with Implementation - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/doubly-linked-list-tutorial/)

在原有的基礎下，雙向鏈結串列的一個節點需要存以下這三個變數：

- `prev`（也稱 `llink` 左鏈結）：指向前一個節點的位址。
- `data`：存放資料。
- `next`（也稱 `rlink` 右鏈結）：指向下一個節點的位址。

### C 程式實作：雙向鏈結串列定義

註：僅片段程式碼，展示 `struct` 定義及 `createNode` 函數包裝。

在單向鏈結串列原有基礎下，新增 `struct Node* prev`。

```c=
struct Node{
    struct Node* prev;
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode -> data = data;
    
    newNode -> prev = NULL;
    newNode -> next = NULL;
    return newNode;
}
```

### 插入操作

需注意先後順序，文中敘述先講的操作如 `next` 要指向誰等等，就先會做。

#### 插入至最前端

假設有一新節點 D 想要插入到最前面，則將其 `next` 指標指向節點 A，`prev` 指向 `NULL`。

![image](https://hackmd.io/_uploads/S1YHjJnVZx.png)

這樣就換頭成功。

#### 插入至最尾端

假設有一新節點 D 想要插入到最後面，則將其 `next` 指標指向 `NULL`，`prev` 指向原本最後面的節點 C。

節點 C 要從指向 `NULL` 改指向 D。

![image](https://hackmd.io/_uploads/Bypxhk34Zg.png)

#### 插入至特定節點

假設有一新節點 D 想要插入在節點 B 的後方。

節點 D 需要將 `next` 指向 B 的下一個節點 C，`prev` 指向 B 節點。

接著節點 C 的 `prev` 指向 D。

最後節點 B 的 `next` 指向 D。

![image](https://hackmd.io/_uploads/BktmCJ2Nbl.png)

### 刪除操作

懶得畫圖了...

#### 刪除最前面

要刪除最前面的節點，則先將 Head 改指向其後方的節點。

接著把新的 Head 的 `prev` 改指向 `NULL`，因為原本還是指向舊的 Head。

![image](https://hackmd.io/_uploads/S1X-ee24Zl.png)

Image Source：[Deletion in a Doubly Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/delete-a-node-in-a-doubly-linked-list/)

#### 刪除最後面

首先找出倒數第二個節點。

把倒數第二個節點的 `next` 改指向 `NULL`，即可刪除最後一個節點。

![image](https://hackmd.io/_uploads/HJ_clgnVZx.png)

Image Source：[Deletion in a Doubly Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/delete-a-node-in-a-doubly-linked-list/)

#### 刪除特定節點

先看到第一個節點，將其 `next` 指向最後一個節點。

接著最後一個節點的 `prev` 指向第一個節點。

就可以刪掉中間那個節點了。

![image](https://hackmd.io/_uploads/S1YMbg3Ebe.png)

Image Source：[Deletion in a Doubly Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/delete-a-node-in-a-doubly-linked-list/)

### C 程式實作：插入操作

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    struct Node* prev;
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode -> data = data;
    
    newNode -> prev = NULL;
    newNode -> next = NULL;
    return newNode;
}

void push_front(struct Node** head_ref, int new_data){
    struct Node* new_node = createNode(new_data);
    
    new_node -> next = (*head_ref);
    
    // 判斷舊 head 是否存在
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    
    (*head_ref) = new_node;
}

void push_back(struct Node** head_ref, int new_data){
    // 由於 new_node 的 next 預設是 NULL
    // 所以不用特地寫 new_node -> next = NULL;
    struct Node* new_node = createNode(new_data);
    
    // 若串列為空
    // 則新節點即為 head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
    
    // 尋找最後一個節點
    struct Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }
    
    last->next = new_node;
    
    new_node->prev = last;
}

void insert_after(struct Node* prev_node, int new_data){
    // 檢驗前一個節點是否存在
    if (prev_node == NULL) {
        printf("error : 指定的前一個節點是 NULL\n");
        return;
    }
    
    struct Node* new_node = createNode(new_data);
    
    new_node->next = prev_node->next;
    new_node->prev = prev_node;
    
    if (new_node->next != NULL) {
        new_node->next->prev = new_node;
    }
    
    prev_node->next = new_node;
}

void printList(struct Node* node) {
    struct Node* last = NULL;
    printf("正向走訪: ");
    while (node != NULL) {
        printf("%d -> ", node->data);
        last = node;
        node = node->next;
    }
    printf("NULL\n");

    printf("反向走訪: ");
    while (last != NULL) {
        printf("%d -> ", last->data);
        last = last->prev;
    }
    printf("NULL\n");
    printf("--------------------------\n");
}

int main() {
    struct Node* head = NULL;

    push_back(&head, 10);
    push_back(&head, 20);
    push_back(&head, 30);
    
    push_front(&head, 5);

    insert_after(head->next, 15);
    
    printList(head);

    return 0;
}
```

Output：

```
正向走訪: 5 -> 10 -> 15 -> 20 -> 30 -> NULL
反向走訪: 30 -> 20 -> 15 -> 10 -> 5 -> NULL
--------------------------
```

時間複雜度：

- 插入至最前面： $O(1)$
- 插入至最後面： $O(n)$
- 插入至特定節點後方： $O(1)$ （已知該節點）

### C 程式實作：刪除操作

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node{
    struct Node* prev;
    int data;
    struct Node* next;
};

struct Node* createNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode -> data = data;
    
    newNode -> prev = NULL;
    newNode -> next = NULL;
    return newNode;
}

void delete_front(struct Node** head_ref){
    if (*head_ref == NULL){
        printf("串列為空無法刪除\n");
        return;
    }
    
    struct Node* temp = *head_ref;
    
    *head_ref = temp -> next;
    
    if (*head_ref != NULL){
        (*head_ref) -> prev = NULL;
    }
    
    free(temp);
}

void delete_end(struct Node** head_ref){
    if (*head_ref == NULL){
        printf("串列為空無法刪除\n");
        return;
    }
    
    struct Node* last = *head_ref;
    
    if (last->next == NULL){
        *head_ref = NULL;
        free(last);
        printf("已刪除尾部節點 (原串列僅剩一個)\n");
        return;
    }
    
    while (last->next != NULL){
        last = last -> next;
    }
    
    last -> prev -> next = NULL;
    
    free(last);
}

void delete_node(struct Node** head_ref, int key){
    if (*head_ref == NULL) return;
    
    struct Node* curr = *head_ref;
    while (curr != NULL && curr -> data != key){
        curr = curr -> next;
    }
    
    if (curr == NULL){
        printf("error : 找不到數值 %d\n", key);
        return;
    }
    
    if (*head_ref == curr){
        *head_ref = curr -> next;
    }
    
    if (curr -> prev != NULL){
        curr -> prev -> next = curr -> next;
    }
    
    if (curr -> next != NULL){
        curr -> next -> prev = curr -> prev;
    }
    
    free(curr);
}

void printList(struct Node* node) {
    struct Node* last = NULL;
    printf("正向走訪: ");
    while (node != NULL) {
        printf("%d -> ", node->data);
        last = node;
        node = node->next;
    }
    printf("NULL\n");

    printf("反向走訪: ");
    while (last != NULL) {
        printf("%d -> ", last->data);
        last = last->prev;
    }
    printf("NULL\n");
    printf("--------------------------\n");
}

int main() {
    struct Node* head = NULL;

    // 建立測試資料 10 <-> 20 <-> 30 <-> 40 <-> 50
    head = createNode(10);
    struct Node* n2 = createNode(20);
    struct Node* n3 = createNode(30);
    struct Node* n4 = createNode(40);
    struct Node* n5 = createNode(50);

    // 手動串接
    head->next = n2; n2->prev = head;
    n2->next = n3;   n3->prev = n2;
    n3->next = n4;   n4->prev = n3;
    n4->next = n5;   n5->prev = n4;

    printf("初始狀態：\n");
    printList(head);

    delete_front(&head);
    printList(head); 

    delete_end(&head);
    printList(head); 
    
    delete_node(&head, 30);
    printList(head); 

    delete_node(&head, 20);
    delete_node(&head, 40);
    printList(head);

    return 0;
}
```

Output：

```
初始狀態：
正向走訪: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
反向走訪: 50 -> 40 -> 30 -> 20 -> 10 -> NULL
--------------------------
正向走訪: 20 -> 30 -> 40 -> 50 -> NULL
反向走訪: 50 -> 40 -> 30 -> 20 -> NULL
--------------------------
正向走訪: 20 -> 30 -> 40 -> NULL
反向走訪: 40 -> 30 -> 20 -> NULL
--------------------------
正向走訪: 20 -> 40 -> NULL
反向走訪: 40 -> 20 -> NULL
--------------------------
正向走訪: NULL
反向走訪: NULL
--------------------------
```

三種刪除操作時間複雜度：

- 刪除最前面：$O(1)$
- 刪除尾端：$O(n)$
- 刪除特定節點：$O(1)$ / $O(n)$

## 環狀鏈結串列（Circular Linked List）

與一般單向鏈結串列（Singly Linked list）不同的是，環狀鏈結串列是沒有終點的（最後一個節點**不**指向 NULL），最後一個節點會指向回到第一個節點，形成一個閉環，如圖：

![Circular Linked List](https://hackmd.io/_uploads/SyAz7doVWx.png)

Image Source：[Circular Linked List Implementation in Java - GeeksforGeeks](https://www.geeksforgeeks.org/java/circular-linked-list-java/)

### 組成的基本要素

- 首尾相連：最後一個節點的 `next` 指標指向 `Head`（頭節點）。
- 無 `NULL` 指標：只要串列不為空，整個串列中不會有任何節點指向 `NULL`。

### 類型

- 單向環狀鏈結串列（Circular Singly Linked List）：每個節點只有一個 `next` 指標，單向繞圈。
- 雙向環狀鏈結串列（Circular Doubly Linked List）：每個節點有 `next` 和 `prev`。最後一個節點的 `next` 指向頭，頭節點的 `prev` 指向最後一個節點。

### C 程式實作：單向環狀鏈結串列

以下程式在單向環狀鏈結串列中展示了以下這些操作：

- 插入至最前面
- 插入至最後面
- 刪除特定節點

```c=
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void push_back(struct Node** head_ref, int data) {
    struct Node* newNode = createNode(data);
    struct Node* last = *head_ref;

    // 串列為空
    if (*head_ref == NULL) {
        *head_ref = newNode;
        newNode->next = *head_ref; // 自己指回自己
        return;
    }

    // 串列不為空
    // 先找到最後一個節點
    while (last->next != *head_ref) {
        last = last->next;
    }

    // 調整指標
    last->next = newNode;
    newNode->next = *head_ref;
}

void push_front(struct Node** head_ref, int data) {
    struct Node* newNode = createNode(data);
    struct Node* last = *head_ref;

    // 串列為空
    if (*head_ref == NULL) {
        *head_ref = newNode;
        newNode->next = *head_ref;
        return;
    }

    // 找最後一個節點
    while (last->next != *head_ref) {
        last = last->next;
    }

    // 調整指標
    newNode->next = *head_ref; // 新節點指向舊頭
    last->next = newNode;      // 最後節點指向新節點
    *head_ref = newNode;       // 更新頭指標指向新節點
}

void deleteNode(struct Node** head_ref, int key) {
    if (*head_ref == NULL) return;

    struct Node *curr = *head_ref, *prev = NULL;

    // 要刪除的是頭節點
    if (curr->data == key) {
        // 串列中只有這一個節點
        if (curr->next == *head_ref) {
            *head_ref = NULL;
            free(curr);
            return;
        } 
        // 串列有多個節點
        // 需先找到最後一個節點來更新鏈結
        else {
            struct Node* last = *head_ref;
            while (last->next != *head_ref) {
                last = last->next;
            }
            // 更新最後節點指向新的頭 (head->next)
            last->next = curr->next;
            *head_ref = curr->next; // 移動 head 指標
            free(curr);
            return;
        }
    }

    // 要刪除的不是頭節點，遍歷尋找
    // 用 while 檢查是否繞回起點
    while (curr->next != *head_ref && curr->data != key) {
        prev = curr;
        curr = curr->next;
    }

    // 檢查是否找到了該節點
    if (curr->data == key) {
        prev->next = curr->next;
        free(curr);
    } else {
        printf("數值 %d 不在串列中。\n", key);
    }
}

void printList(struct Node* head) {
    struct Node* current = head;

    if (head == NULL) {
        printf("串列為空\n");
        return;
    }

    printf("環狀串列內容: ");
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("(回到 head: %d)\n", head->data);
}

int main() {
    struct Node* head = NULL;

    push_back(&head, 10);
    push_back(&head, 20);
    push_back(&head, 30);
    printList(head);

    push_front(&head, 5);
    printList(head);
    
    deleteNode(&head, 5);
    printList(head);

    deleteNode(&head, 20);
    printList(head);

    deleteNode(&head, 10);
    deleteNode(&head, 30);
    printList(head);

    return 0;
}
```

Output：

```
環狀串列內容: 10 -> 20 -> 30 -> (回到 head: 10)
環狀串列內容: 5 -> 10 -> 20 -> 30 -> (回到 head: 5)
環狀串列內容: 10 -> 20 -> 30 -> (回到 head: 10)
環狀串列內容: 10 -> 30 -> (回到 head: 10)
串列為空
```

時間複雜度：

- 插入至最後面： $O(n)$
- 插入至最前面： $O(n)$
- 刪除特定節點： $O(n)$

## 鏈結串列的應用

### 用鏈結串列表示堆疊（Stack）

以單向鏈結串列實作，選擇將 Head 端當作 stack 的 top，若用尾端作為 top，時間複雜度會提升。

- 在 Head 操作： 插入和刪除節點只需要修改指標，時間複雜度為 $O(1)$ 。
- 在尾端操作：插入容易，但刪除（pop）時需要遍歷整個串列找到「倒數第二個節點」才能將其指向 Null，時間複雜度為 $O(n)$。

#### Push 操作

將新資料放入堆疊頂端。

1. 建立一個新節點 `newNode`。
2. 將 `newNode` 的 `next` 指標指向目前的 `top`。
3. 將 `top` 指標更新，使其指向 `newNode`。
4. 最後新節點成為了新的 `top`。

#### Pop 操作

將堆疊頂端的資料移除並回傳。

1. 檢查堆疊是否為空（`top == NULL`）。
2. 暫存目前的 `top` 節點到 `temp`（為了釋放記憶體）。
3. 將 `top` 指標往後移動（`top = top->next`）。
4. 刪除 `temp` 節點（釋放記憶體）。
5. 最後原第二個節點變成了新的 `top`。

#### 存取頂端（peek）

直接回傳 `top` 節點的資料即可：`top -> data`。

### C 程式實作：以鏈結串列實現堆疊

```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Stack {
    Node* top;
} Stack;

void initStack(Stack* s) {
    s->top = NULL;
}

bool isEmpty(Stack* s) {
    return s->top == NULL;
}

void push(Stack* s, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    
    if (newNode == NULL) {
        printf("記憶體配置失敗！\n");
        return;
    }

    newNode->data = val;
    newNode->next = s->top; // 新節點指向舊的 Top
    s->top = newNode; // 更新堆疊的 Top 為新節點
    
    printf("Pushed: %d\n", val);
}

void pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow! (堆疊已空)\n");
        return;
    }

    Node* temp = s->top; // 暫存目前的 Top 節點
    s->top = s->top->next; // 將 Top 指標往下移

    free(temp);
}

int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->top->data;
}

int main() {
    Stack myStack;
    initStack(&myStack); // 傳址 & 才可以改到 myStack

    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    printf("目前的 top 是: %d\n", peek(&myStack));

    pop(&myStack); 
    printf("pop 之後的 top 是: %d\n", peek(&myStack));

    pop(&myStack);
    pop(&myStack);
    pop(&myStack);

    return 0;
}
```

### 用鏈結串列表示佇列（Queue）

佇列的 Front 對應 Head，Rear 對應 Tail（鏈結串列尾端）。

Head 端用於刪除資料，Tail 端用於插入資料。

#### enqueue 操作

將資料加入佇列尾端。

1. 建立新節點 `newNode`。
2. 檢查佇列是否為空：
    - 是：`front` 和 `rear` 都指向 `newNode`。
    - 否：
        - 將目前 `rear` 的 `next` 指向 `newNode`。
        - 更新 `rear` 指標指向 `newNode`。

#### dequeue 操作

將佇列頭端的資料移除。

1. 檢查佇列是否為空（`front == NULL`）。
2. 暫存目前的 `front` 到 `temp`。
3. 將 `front` 往後移（`front = front->next`）。
4. 如果移完之後 `front = NULL`（代表剛刪掉的是最後一個節點），則必須把 `rear = NULL`，否則 `rear` 會變成懸空指標（Dangling Pointer）。
5. 釋放 `temp` 記憶體。

### C 程式實作：以鏈結串列實現佇列

```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

void initQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

bool isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, int val) {
    // 將元素插入至尾端
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) return; // 記憶體不足
    
    newNode->data = val;
    newNode->next = NULL; // newNode 為最後一個節點

    // 如果佇列為空
    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } 
    // 佇列不為空
    else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Enqueued: %d\n", val);
}

void dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! (佇列已空)\n");
        return;
    }

    Node* temp = q->front;
    q->front = q->front->next; // 頭指標往後移

    // 如果佇列變空了，rear 也要歸零
    if (q->front == NULL) {
        q->rear = NULL;
    }

    printf("Dequeued: %d\n", temp->data);
    free(temp);
}

int peek(Queue* q) {
    if (isEmpty(q)) return -1;
    return q->front->data;
}

int main() {
    Queue myQueue;
    initQueue(&myQueue);

    enqueue(&myQueue, 10);
    enqueue(&myQueue, 20);
    enqueue(&myQueue, 30);

    dequeue(&myQueue);
    
    printf("Front element: %d\n", peek(&myQueue));
    
    dequeue(&myQueue);
    dequeue(&myQueue);
    dequeue(&myQueue);

    return 0;
}
```

## 總整理

### 陣列 v.s. 鏈結串列

- 陣列（Array）
    - 記憶體連續。
    - 隨機存取快： $O(1)$ 。
    - 插入、刪除慢：需搬移資料。
- 鏈結串列（Linked List）
    - 記憶體不連續。
    - 插入、刪除快：只改指標。
    - 存取慢：需逐節點走訪 $O(n)$ 。

陣列靠 index，鏈結串列靠指標。

### 單向鏈結串列（Singly Linked List）

#### 結構

節點包含：

- data
- next

最後一個節點 `next = NULL`。

#### 常見操作與時間複雜度

**插入**

| 操作      | 時間複雜度                     |
| ------- | ------------------------- |
| 插入最前面   | $O(1)$                    |
| 插入最後面   | $O(n)$（無尾指標）／ $O(1)$（有尾指標） |
| 插入特定節點後 | $O(1)$（已知節點）／ $O(n)$（需先找）  |

**刪除**

| 操作     | 時間複雜度                 |
| ------ | --------------------- |
| 刪除最前面  | $O(1)$                |
| 刪除最後面  | $O(n)$                |
| 刪除指定節點 | $O(n)$ ／ $O(1)$（已知前一節點） |

### 反轉單向鏈結串列（Three-Pointer Method）

使用三個指標：

- prev
- curr
- next

每次只做三件事：

- 記住下一個。
- 反轉指向。
- 指標前進。

時間複雜度： $O(n)$

空間複雜度： $O(1)$

### 雙向鏈結串列（Doubly Linked List）

#### 結構

節點包含：

- prev
- data
- next

#### 特點

- 可前後走訪。
- 插入、刪除更直覺。
- 記憶體成本較高（多一個指標）。

#### 常見操作與時間複雜度

**插入**

| 操作     | 時間複雜度         |
| ------ | ------------- |
| 插入最前面  | $O(1)$        |
| 插入最後面  | $O(n)$        |
| 插入特定節點 | $O(1)$        |

**刪除**

| 操作     | 時間複雜度         |
| ------ | ------------- |
| 刪除最前面  | $O(1)$        |
| 刪除最後面  | $O(n)$        |
| 刪除特定節點 | $O(1)$ ／ $O(n)$ |

### 環狀鏈結串列（Circular Linked List）

#### 特性

- 沒有 NULL
- 尾節點 next 指回 head
- 可無限循環

#### 類型

- 單向環狀
- 雙向環狀

#### 時間複雜度（單向環狀）

| 操作     | 時間複雜度  |
| ------ | ------ |
| 插入最前   | $O(n)$ |
| 插入最後   | $O(n)$ |
| 刪除指定節點 | $O(n)$ |

搭配尾指標，插入可優化至 $O(1)$ 。

### 鏈結串列的實際應用

#### 以鏈結串列實作堆疊（Stack）

- `top` 設在 `Head`。
- `Push` / `Pop` 都是 $O(1)$。

| 操作   | 對應行為     |
| ---- | -------- |
| push | 插入至 Head |
| pop  | 刪除 Head  |
| peek | 讀取 Head  |

若用尾端當 `top`，`pop` 會退化成 $O(n)$。

#### 以鏈結串列實作佇列（Queue）

- Head → Front（刪除）
- Tail → Rear（插入）

| 操作      | 時間複雜度  |
| ------- | ------ |
| Enqueue | `O(1)` |
| Dequeue | `O(1)` |

刪除最後一個節點時，rear 必須設為 NULL，避免懸空指標（Dangling Pointer）。

