前幾天學習陣列的插入與刪除時，我們發現一個麻煩：只要在中間加入或拿掉一筆資料，後面的元素通常都要跟著搬動。如果資料很多，搬動的成本也會增加。那麼，有沒有一種方法，可以不用把資料緊密排在一起，也能維持它們的前後順序？這就是今天要認識的鏈結串列（linked list）。

在進入鏈結串列之前，先認識有序串列（ordered list）：它就是一群有前後順序的資料，例如一年中的月份，或一天中的各個小時。這裡的「有序」只代表資料有先後順序，不一定是按照數值大小排列。

陣列會把資料一個接一個放在連續的記憶體空間中，這叫做循序映射；鏈結串列則使用非循序映射，資料不用放在一起，只要記住下一筆資料在哪裡，就能按照原本的順序找到它們。

鏈結串列由節點組成

鏈結串列是由一個個**節點（node）**連接而成。每個節點至少有兩個部分：

• 資料欄位：存放真正的資料。
• 鏈結欄位：記住下一個節點的位置。

一個簡單的單向鏈結串列可以畫成這樣：

head 是串列頭，它記住第一個節點的位置。每個節點再指向下一個節點，最後一個節點的鏈結欄位是 NULL，表示後面已經沒有資料。如果串列是空的，head 也會是 NULL。

節點在記憶體中不一定要排在一起。例如，假設三個節點分別放在下面的位置：

0x1000：資料 10，下一個節點在 0x4500
0x2200：資料 30，下一個節點是 NULL
0x4500：資料 20，下一個節點在 0x2200

雖然記憶體位址沒有照順序排列，但從 head = 0x1000 出發，仍然會得到：

head → 10 → 20 → 30 → NULL

這就像幾張紙條放在不同抽屜裡，每張紙條都寫著下一張在哪裡。紙條不用放在一起，只要照著提示尋找，仍然能依序讀完。

兩種實作方法

用陣列索引表示鏈結

鏈結欄位可以存放「下一個元素的陣列索引」。例如：

從 head = 0 出發，順序是 0 → 2 → 1 → -1，所以讀到的資料是：

10 → 20 → 30 → 結束

這種做法確實可以模擬鏈結串列，但比較少使用，主要是因為陣列容量通常要先決定，而且程式還要自己管理哪些位置是空的。它既有陣列容量固定的限制，又不能直接用索引找到邏輯上的第幾個節點。

不過，如果資料數量有明確上限，或程式不方便使用動態記憶體，陣列版仍然有它的用途。

用結構與指標表示鏈結

在 C 語言中，更常見的做法是用結構表示節點，再用指標記住下一個節點的位址：

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

data 用來存資料，next 則是指向下一個節點的指標。接著，我們可以建立三個節點並把它們串起來：

#include <stdio.h>

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

int main(void) {
    Node first = {10, NULL};
    Node second = {20, NULL};
    Node third = {30, NULL};

    first.next = &second;
    second.next = &third;

    Node *head = &first;
    Node *current = head;

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

    return 0;
}

輸出結果為：

10 -> 20 -> 30 -> NULL

程式先讓 first 指向 second，再讓 second 指向 third。head 指向 first，所以從 head 開始沿著 next 往後走，就能依序找到三個節點。third.next 保持為 NULL，代表串列結束。

這個例子先用三個固定的區域變數，讓我們專心看懂節點如何連接。之後要在程式執行期間新增節點時，才會用到動態記憶體配置。

鏈結串列的種類

根據節點的連接方式，鏈結串列可以分成：

• 單向鏈結串列：每個節點只記住下一個節點。
• 單向環狀鏈結串列：最後一個節點連回第一個節點。
• 雙向鏈結串列：每個節點同時記住前一個和下一個節點。
• 雙向環狀鏈結串列：可以往前、往後走，而且頭尾相連。

今天只要先認得這些名稱，後面再分別學習它們的操作方式。

陣列和鏈結串列怎麼選？

假設 n 代表資料筆數：

鏈結串列常被說成「插入、刪除很快」，但前提是已經找到操作位置。如果還要先從 head 開始尋找，尋找本身最壞仍然需要 O(n)。

小結

鏈結串列把資料拆成一個個節點，再利用鏈結欄位記住下一個節點的位置。節點不必連續排列，只要從 head 開始順著鏈結走，最後仍然能依序讀到所有資料。在 C 語言中，最常見的做法是用結構保存資料，再用指標連接節點。

今日重點：

• 一個節點至少包含資料欄位與鏈結欄位。
• head 指向第一個節點，最後一個節點指向 NULL。
• 陣列版用索引記住下一個位置；指標版用位址記住下一個節點。
• 鏈結串列不用搬動後面的資料，但尋找指定位置通常需要從頭開始。

下一篇將練習單向鏈結串列的走訪、插入與刪除，並逐步追蹤每一次指標變化。