上一篇認識了單向鏈結串列的結構：每個節點保存資料，並用 next 指向下一個節點。這一篇要練習三個基本操作：走訪、插入與刪除。

假設目前有一條串列：

head → 10 → 20 → 30 → NULL

鏈結串列的節點不必搬動；操作串列時，真正改變的是節點之間「誰指向誰」。

前半段的短程式碼是用來解釋單一操作的函式片段；可以直接編譯執行的版本放在後面的「完整程式」。

走訪：沿著 next 往後走

**走訪（traversal）**是從 head 開始，依序拜訪每個節點：

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

    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }

    printf("NULL\n");
}

若串列是 10 → 20 → 30 → NULL，current 會依序指向：

10 → 20 → 30 → NULL

到達 NULL 就代表走完整條串列。這裡另外使用 current，而不直接移動 head，是因為 head 是串列的入口；如果遺失它，之後就無法再從第一個節點開始存取資料。

假設串列中有 n 個節點，完整走訪需要拜訪每個節點，因此時間複雜度是 O(n)。

插入：先接後面，再接前面

先看最簡單的情況：把新節點 5 插入串列開頭。

插入前：head → 10 → 20 → 30 → NULL
插入後：head →  5 → 10 → 20 → 30 → NULL

操作順序是：

1. newNode->next = head：讓新節點指向原本的第一個節點。
2. head = newNode：讓 head 改為指向新節點。

因為函式內部可能改變串列頭，所以函式會傳回新的 head：

Node *insertAtHead(Node *head, int data) {
    Node *newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

呼叫時必須接住傳回值：

head = insertAtHead(head, 5);

在開頭插入不必走訪串列，只修改固定數量的指標，所以時間複雜度是 O(1)。

如果要把 25 插入節點 20 後方，則要先讓新節點接上節點 30，再改變節點 20 的指向：

插入前：10 → 20 → 30 → NULL
插入後：10 → 20 → 25 → 30 → NULL

newNode->next = previous->next;
previous->next = newNode;

這兩行的順序很重要。如果先改寫 previous->next，又沒有事先保存原本的位址，後半段串列就可能失去連線。

刪除：跨過目標節點

假設要刪除資料為 20 的節點：

刪除前：head → 10 → 20 → 30 → NULL
刪除後：head → 10 ─────→ 30 → NULL

尋找目標時需要兩個指標：

• current 指向目前檢查的節點。
• previous 指向 current 的前一個節點。

以 10 → 20 → 30 為例，要尋找 20 時，兩個指標會這樣移動：

剛開始：previous = NULL，current = 10
往後一步：previous = 10，  current = 20

此時 current 已經找到 20，而 previous 正好停在它前面的 10。接下來只要讓 10 跳過 20，直接指向 30：

previous->next = current->next;
free(current);

第一行讓前一個節點直接指向下一個節點；第二行釋放不再使用的節點。

不過，刪除第一個節點時沒有 previous，必須改為移動 head：

head = current->next;
free(current);

因此，刪除函式要分別處理三種結果：找不到目標、刪除第一個節點，以及刪除其他節點。依資料值尋找節點最壞需要檢查整條串列，所以時間複雜度是 O(n)。

完整程式

以下程式會建立 10 → 20 → 30，接著在開頭插入 5、刪除 20，最後釋放所有節點：

#include <stdio.h>
#include <stdlib.h>

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

Node *createNode(int data) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        fprintf(stderr, "記憶體配置失敗\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }

    printf("NULL\n");
}

Node *insertAtHead(Node *head, int data) {
    Node *newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

Node *deleteValue(Node *head, int target) {
    Node *current = head;
    Node *previous = NULL;

    // 尚未走到尾端，而且還沒找到目標時，繼續往後找
    while (current != NULL && current->data != target) {
        previous = current;
        current = current->next;
    }

    // current 是 NULL，表示串列裡沒有 target
    if (current == NULL) {
        return head;
    }

    // previous 是 NULL，表示要刪除的是第一個節點
    if (previous == NULL) {
        head = current->next;
    } else {
        // 讓前一個節點跳過 current
        previous->next = current->next;
    }

    free(current);
    return head;
}

void freeList(Node *head) {
    while (head != NULL) {
        Node *nextNode = head->next;
        free(head);
        head = nextNode;
    }
}

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

    head = insertAtHead(head, 30);
    head = insertAtHead(head, 20);
    head = insertAtHead(head, 10);
    printf("建立串列：");
    printList(head);

    head = insertAtHead(head, 5);
    printf("插入 5：");
    printList(head);

    head = deleteValue(head, 20);
    printf("刪除 20：");
    printList(head);

    freeList(head);
    head = NULL;

    return 0;
}

輸出結果為：

建立串列：10 -> 20 -> 30 -> NULL
插入 5：5 -> 10 -> 20 -> 30 -> NULL
刪除 20：5 -> 10 -> 30 -> NULL

malloc 配置的記憶體不會自動歸還，因此刪除節點時要呼叫 free。程式結束前，freeList 也會逐一釋放串列中剩下的節點。

在 freeList 裡，必須先用 nextNode 保存下一個節點，才能釋放目前節點：

Node *nextNode = head->next;
free(head);
head = nextNode;

如果先執行 free(head)，就不能再讀取 head->next，因為那塊記憶體已經被釋放。

常見錯誤

• 走訪時直接移動唯一的 head，導致串列入口遺失。
• 插入時先覆蓋原本的 next，使後半段串列失去連線。
• 刪除第一個節點時，忘記更新 head。
• 使用 malloc 建立節點後，忘記用 free 釋放記憶體。
• 呼叫插入或刪除函式時，忘記用 head = ... 接住新的串列頭。

小結

單向鏈結串列的操作，可以理解成沿線尋找、接上新線與拆掉舊線。走訪時用暫時指標沿著 next 前進；插入時先保住後方的連線；刪除時先讓前後節點重新接好，再釋放不再使用的節點。

今日重點：

• 走訪從 head 開始，遇到 NULL 時停止。
• 在開頭插入的時間複雜度是 O(1)。
• 插入節點時，要先讓新節點接上後方。
• 依資料值刪除節點的時間複雜度最壞是 O(n)。
• 動態配置的節點不再使用時，必須呼叫 free。

下一篇將比較單向、環狀與雙向鏈結串列，看看改變節點的連接方式後，走訪與操作方法有什麼不同。