C語言-鏈結串列 Linked List

2026.01.08 Munich, Germany

介紹完基本的指標後，在深入複雜的資料結構之前，我們必須先認識陣列。陣列是一種線性資料結構，它在電腦記憶體中佔用一塊連續的空間，用來儲存相同型別的資料。你可以把它想像成一排整齊編號的置物櫃，只要知道號碼(索引)，就能立刻拿到裡面的東西。

在 C 語言中，宣告和使用陣列非常直觀 ：

// C 語言陣列語法範例
#include <stdio.h>

int main() {
    // 宣告並初始化一個包含 5 個整數的陣列
    // 這會在記憶體中劃出一塊足以容納 5 個 int 的連續空間
    int numbers[5] = {10, 20, 30, 40, 50};

    // 2. 存取陣列元素 (透過索引 Index，從 0 開始)
    printf("第一個元素 (index 0): %d\n", numbers[0]); // 輸出 10
    printf("第三個元素 (index 2): %d\n", numbers[2]); // 輸出 30

    // 3. 修改元素值
    numbers[1] = 25; // 將原本的 20 改為 25

    return 0;
}

雖然陣列在存取資料上極其迅速，但它在面對動態變化的資料時，卻暴露出了嚴重的缺點。

首先，當你宣告 int numbers[5] 時，這個陣列的大小就固定了。如果程式執行時資料突然變成 6 個，你無法直接擴張它。你必須重新宣告一個更大的陣列，然後把舊資料全部搬過去。反之，如果你只用了 2 個位置，剩下的 3 個位置就白白浪費了記憶體。

其次，如果你想在一個長度為 1000 的陣列的最前端（index 0）插入一個新數字。為了騰出這個位置，你必須把原本在 index 0 到 999 的所有資料，通通往後挪動一格。刪除也是同理，需要把後面的資料往前補。這種「一動全動」的操作，在資料量大時非常耗時（時間複雜度為 O(n)）。

為了克服陣列的這些僵化特性，Linked List（鏈結串列） 應運而生。

不同於陣列要求「連續的記憶體」，Linked List 採用了完全不同的想法：離散儲存、指標串聯。它將資料分散在記憶體的各個角落，然後透過指標(Pointer)將這些離散的資料像接龍一樣串起來。也就是說，鏈結串列的美個節點都包含了(1).資料，我們要存的資訊 (2).指標，指向下一個節點。如下圖所示:

圖(一)：鏈結串列

在陣列當中，每個格子只存我們想要存的數值，但是在鏈結串列當中，每個格子除了存數值之外，還會存下一個節點的記憶體地址。在 C 語言中，我們用struct來定義它

struct Node {
    int data;           // 存放資料
    struct Node *next;  // 指向下一個節點的指標
};

這個結構有點像接龍，一直連到最後一個點時，它的指標則會指向null，代表這個節點是最後一站了。

這種做法和陣列的差別是，假設你在陣列 A,B,D,E,F 想要插入 C，你必須將 D,E,F 全部往後挪一格，然後把 C 放進去。但是假設你用 Linked List，你只需要先讓 C 的指標指向 D 的記憶體地址，再讓 B 的指標指向 C 的記憶體地址就行了。

我們拿三個數字來實作看看，首先定義節點結構，包含資料以及指向下一個節點的指標。

#include <stdio.h>

// 1. 定義節點結構
struct Node {
    int data;           // 存放資料
    struct Node *next;  // 指向下一個節點的指標
};

int main() {
    // 2. 宣告三個獨立的節點
    struct Node n1, n2, n3;

    // 3. 填入數值
    n1.data = 10;
    n2.data = 20;
    n3.data = 30;

    // 4. 開始設定指標指向
    n1.next = &n2;  // n1 的指標存入 n2 的地址
    n2.next = &n3;  // n2 的指標存入 n3 的地址
    n3.next = NULL; // n3 是最後一站，指標指向 NULL

    // 5. 從頭指標 (n1) 開始出發
    struct Node *ptr = &n1; 

    printf("開始：\n");
    while (ptr != NULL) {
        printf("目前節點資料: %d，地址: %p\n", ptr->data, (void *)ptr);

        // 關鍵動作：沿著指標走到下一站
        ptr = ptr->next; 
    }
    printf("抵達終點 (NULL)\n");

    return 0;
}

上面的程式碼中容易讓人困惑的是struct Node *ptr = &n1;，這個的意思是我們定義了一個指標，它指向的是是一個資料型別為 struct Node的資料，而&n1就是這筆資料的記憶體地址。

那麼如果我們要取n1的data要怎麼寫呢? 我們可以寫 (*ptr).data，意思是取得ptr 裡面存的內容中的data，但是有另一種更簡潔的寫法ptr->data，這兩種寫法完全等價。

上面我們實作的是 Singly Linked List (單向鏈結串列)，每個節點只知道「下一站」。

但實務上還有一種 Doubly Linked List (雙向鏈結串列)，每個節點會多存一個 prev 指標指向「上一站」。雖然這讓它在處理某些問題(如：刪除節點、回溯)時更為強大，但也因此多占用了記憶體。

想像你在實作瀏覽器的「上一頁」與「下一頁」功能。如果是單向鏈結串列，你要回到上一頁必須從頭開始遍歷，效率極低；而雙向鏈結串列只需透過 prev 指標就能瞬間移動，這就是雙向鏈結串列存在的價值。

在 C 語言中，雙向鏈結串列的結構定義如下：

struct Node {
    int data;
    struct Node *prev; // 多了這條往回指的路
    struct Node *next;
};

反向鏈結串列

反向鏈結串列是很多問題的基礎，也是在學這個章節時的一個難點，它的目標就是把一個接好的鏈結串列反過來接。它的複雜之處在於，它很像一排人把手搭在前面的人的肩上，當你放開手往後轉改成搭後面的人的肩了，你就和原本搭肩的人斷了聯繫，這就導致整個鏈結串列斷掉。

因此，要達到轉身，我們必須有三個指標:

prev:代表在我之前的，我即將要指向的人(一開始是NULL) curr:代表目前正在處理的節點 nextTemp:代表下一站，也就是在轉身之前要先記錄原本指向的人

所以反向鏈結串列寫起來會像下面這樣

struct Node* reverseList(struct Node* head) {
    struct Node *prev = NULL;
    struct Node *curr = head;
    struct Node *nextTemp = NULL;

    while (curr != NULL) {
        nextTemp = curr->next; // 1. 救命繩：先記住原本的下一站
        curr->next = prev;     // 2. 轉頭：手轉向指回前面
        prev = curr;           // 3. 推進：前任往前走一步，變成現在的自己
        curr = nextTemp;       // 4. 推進：自己往前走一步，變成剛才記住的下一站
    }
    return prev; // 最後 prev 會停在原本的末端，也就是新鏈結串列的頭
}

虛擬節點

虛擬節點 (Dummy Node) 是一個我們常用的技巧。因為在操作鏈結串列時，第一個節點常常會變成特例，需要另外用 if-else 來處理。而虛擬節點就可以幫我們解決這個麻煩。

舉例來說，存在 A -> B -> C -> D 的關係，如果我們希望拿掉 B 或 C，那我們只要讓 B 或 C 的前一個節點改成直接指向 B 或 C 的後一個節點就好了。但如果我們要拿掉的是 A，就不存在所謂「A的前一個節點」了，所以我們就得專門為 A 的情況另外寫一個條件

// 沒有 Dummy Node 的寫法
struct Node* deleteNode(struct Node* head, int target) {
    // 特例 1：如果串列是空的
    if (head == NULL) return NULL;

    // 特例 2：如果要刪除的剛好是「第一個節點 (Head)」
    if (head->data == target) {
        struct Node* newHead = head->next; // 記住新的頭
        free(head);                        // 把舊的頭請走
        return newHead;                    // 回傳新的頭
    }

    // 正常情況：刪除中間的節點... (省略)
}

虛擬節點的想法就是，既然 A 的前面沒有人，那就自己造一個，然後讓它指像 A，這樣一來所有我們可能需要操作的節點就都有前後節點了。而這個虛擬節點的資料不重要，因為它的存在就是為了指向 A 而已。

// 使用 Dummy Node 的寫法
struct Node* deleteNode(struct Node* head, int target) {
    // 1. 創造一個假人，並讓他的手搭在 Head 上
    struct Node dummy; 
    dummy.next = head;

    // 2. 指標 prev 從假人開始出發
    struct Node* prev = &dummy;

    // 3. 順著隊伍往下找
    while (prev->next != NULL) {
        if (prev->next->data == target) {
            // 找到了！不管是誰，前面的人 (prev) 直接改搭下下個人的肩膀
            struct Node* temp = prev->next;
            prev->next = temp->next;
            free(temp);
            break; // 刪完就收工
        }
        prev = prev->next; // 繼續往下走
    }

    // 4. 假人的下一位，永遠是「正確的新隊長」，直接回傳！
    return dummy.next; 
}

快慢指標

快慢指標 (Fast-Slow Pointers) 是一種演算法，特別在這邊介紹是因為筆者認為這個演算法很反直覺，必須要讀過才能在面試中回答或是在實作中使用。

這個題目是：假設存在一種鏈結串列，最後一個節點並非指向 NULL，而是指回了之前的某個節點，導致程式遍歷時陷入無限循環。那麼是否存在一種高明的方式，來快速判斷一個鍵結串列是否存在這種環? 你可以思考一下你的解題思路 (這題是 Leetcode 的第141 題)。

答案是，我們用兩個指標，第一個指標一次前進一步，第二個指標一次前進兩步，如果環存在的話，這兩個指標必定會在某個時刻相遇。

這個解法聰明的地方是，大部分的人的直覺是「記住走過的路」，也就是再加一個變數來記錄指標遍歷過的地方，但是這樣又需要更多的記憶體。而用快慢指標，我們就可以在花費更少額外空間的情況下，僅憑兩個指標的速度差得到結果。

結語

雖然這邊文章讀起來可能很輕鬆，但是鏈結串列的難點就在於，真的實作時的操作容易讓人頭昏眼花，所以建議讀完文章，有了基本概念後，應該再去寫點題目，才能真正熟悉這種資料結構以及指標的使用。

[embed]C語言-指標 Pointer 在 RAM 當中，記憶體是以位元組 (Byte) 為最小定址單位的，每一個位元組都會對應到一個唯一的記憶體地址 (Memory Address)。當我們在 C 語言中宣告一個變數時，編譯器與作業系統就會根據該變數的資料型態 (比如…medium.com

[embed]C語言-動態記憶體配置 Dynamic Memory Allocation 我們在前兩篇文章分別介紹了指標 (Pointer) 的使用以及鏈結串列 (Linked List)，這兩者都是寫程式的基礎。這篇文章要來解釋動態記憶體配置，這樣我們才能靈活地使用鏈結串列。medium.com

[embed]搞懂演算法的時間和空間複雜度 想像你是一個剛入職的軟體工程師，你老闆叫你寫一個功能，檢查今天的訂單裡面有沒有重複購買的客戶。於是聰明的你把第一筆訂單拿出來，和剩下的訂單比對；再把第二筆訂單拿出來，繼續和剩下的訂單比對，以此類推。你拿了100筆資料做測試，完美。於是程式碼…medium.com

[embed]C語言-雙重指標與函式指標 本文需要的先備知識為 (1). 指標 (2). 動態記憶體配置。在介紹指標的文章中我們介紹了指標最基本的知識。指標變數可以儲存變數的地址，然後我們可以再去讀這個地址當中的值，如下所示medium.com

[embed]C語言-堆疊 Stack 在介紹動態記憶體配置的文章中，我們解釋了 Stack 和 Heap，他們是記憶體空間的不同區域，並且在不同的時機使用。medium.com

[embed]歡迎來到 Ac Studio！第一次來請先讀這篇 大家好！為了幫助各位讀者快速找到自己需要的內容，我們製作了這張知識地圖。如圖所示，目前我們的技術文章主要分為 8 個大類。希望這張地圖能幫助你快速上手，找到需要的資源。medium.com