# 【考試向】資料結構筆記（鏈結串列）
[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;
};
```
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;
}
```
### 插入操作
預設以下三樣操作的初始圖都長這樣：
三個節點下面那個節點是新節點，準備要插入的。
#### 插入至最前面
建立了新節點 D 準備插入至最前面。
讓 D 節點指向 A 節點：
接著把 Head 移到 D 上即可：
#### 插入至最後
建立了新節點 D 準備插入至最後面，由於是末端，因此 D 需要指向 NULL，如圖：
接著把 C 從原本指向 NULL 改成指向 D：
#### 插入至某節點後方
假設要將新建立的 D 節點插入在 A 節點後方，首先要將 D 節點指向 B：
接著把 A 節點改指向 D：
就完成插入了。
### 刪除操作
假設接下來的三個操作的初始圖都是：
#### 刪除最前面
先用一個臨時指標 `temp` 指向 A 節點，因為等下 Head 要移走，怕找不到 A 來釋放。
之後將 Head 指向 B 節點：
最後釋放 temp 指向的記憶體，即可完成。
#### 刪除尾端
首先用 `temp` 臨時指標，指向最後一個節點，以便後續做釋放。
接著在倒數第二個節點 B，改指向 NULL：
最後釋放掉 temp，即將 C 給刪除了。
#### 刪除特定節點
假設要刪除節點 B，一樣先用 `temp` 臨時指標指向要刪除的節點 B。
接著將節點 A 的指標指向節點 C：
最後釋放掉 `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 長以下圖那樣：
想要做 A + B 的串接的話，只需要將 A 的最後一個節點指向 B 的開頭即可。
### 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）
與單向鏈結串列的差別是，單向只能往前走，不能往後走，而雙向可以在任意節點選擇要往前還是往後，如圖：
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`。
這樣就換頭成功。
#### 插入至最尾端
假設有一新節點 D 想要插入到最後面，則將其 `next` 指標指向 `NULL`，`prev` 指向原本最後面的節點 C。
節點 C 要從指向 `NULL` 改指向 D。
#### 插入至特定節點
假設有一新節點 D 想要插入在節點 B 的後方。
節點 D 需要將 `next` 指向 B 的下一個節點 C，`prev` 指向 B 節點。
接著節點 C 的 `prev` 指向 D。
最後節點 B 的 `next` 指向 D。
### 刪除操作
懶得畫圖了...
#### 刪除最前面
要刪除最前面的節點，則先將 Head 改指向其後方的節點。
接著把新的 Head 的 `prev` 改指向 `NULL`，因為原本還是指向舊的 Head。
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 Source：[Deletion in a Doubly Linked List - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/delete-a-node-in-a-doubly-linked-list/)
#### 刪除特定節點
先看到第一個節點，將其 `next` 指向最後一個節點。
接著最後一個節點的 `prev` 指向第一個節點。
就可以刪掉中間那個節點了。
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），最後一個節點會指向回到第一個節點，形成一個閉環，如圖：
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）。
Sign in with Wallet
Connect another wallet