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

發表於2026-01-08|更新於2026-01-19|資料結構

|總字數:7.1k|閱讀時間:31分鐘|瀏覽量:|評論數:

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

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

最後更新日期：

單向鏈結串列（Singly Linked list）

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

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

連續的壞處：

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

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

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

陣列 v.s. 鏈結串列

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

組成的基本要素

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

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

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

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

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

singly linked list

Image Source：Advantages and Disadvantages of Linked List - GeeksforGeeks

圖中的文字解釋：

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*)。

#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

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

插入至最前面

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

讓 D 節點指向 A 節點：

singly linked list join 1

接著把 Head 移到 D 上即可：

singly linked list join 2

插入至最後

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

singly linked list join 3

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

singly linked list join 4

插入至某節點後方

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

singly linked list join 5

接著把 A 節點改指向 D：

singly linked list join 6

就完成插入了。

刪除操作

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

singly linked list initialization for delete operation

刪除最前面

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

singly linked list delete 1

之後將 Head 指向 B 節點：

singly linked list delete 2

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

刪除尾端

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

singly linked list delete 3

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

singly linked list delete 4

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

刪除特定節點

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

singly linked list delete 5

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

singly linked list delete 6

最後釋放掉 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。

#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

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

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

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

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

singly linked list concatenate 2

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

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

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

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

#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 開始。

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

接著以此類推。

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

Image Source：Operations of Doubly Linked List with Implementation - GeeksforGeeks

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

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

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

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

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

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

刪除最後面

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

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

Image Source：Deletion in a Doubly Linked List - GeeksforGeeks

刪除特定節點

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

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

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

Image Source：Deletion in a Doubly Linked List - GeeksforGeeks

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：

1
2
3

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

時間複雜度：

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

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

Image Source：Circular Linked List Implementation in Java - GeeksforGeeks

組成的基本要素

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

類型

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

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 操作

將新資料放入堆疊頂端。

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

Pop 操作

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

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

存取頂端（peek）

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

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 操作

將資料加入佇列尾端。

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

dequeue 操作

將佇列頭端的資料移除。

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

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）。

文章作者: LukeTseng

文章連結: https://luketsengtw.github.io/posts/ed071748

程式設計電腦資料結構