@TOC(目錄)
引言：整齊的代價
在上一篇文章中，我們一起探索了數據結構大家族的第一位成員——順序表。我們了解到，順序表作為一種線性結構，其最大的特點在于邏輯順序與物理順序的一致性，即元素之間不僅存在邏輯上的前后關系，在物理存儲空間中也以連續的方式存放。
這種“整齊”帶來了顯而易見的好處，比如我們可以通過索引值快速定位到任何一個元素，就像報出房間號就能立刻找到人一樣。但是，凡事有利也有弊。這種對連續空間近乎苛刻的要求，也給它帶來了麻煩。
如圖1，左邊是我們的內存空間，右邊是待存儲的順序表。雖然內存空閑的總空間綽綽有余，但我們卻找不到一塊足夠大且連續的區域來放置這個順序表。這就是順序表的局限性之一：對連續空間要求高，容易導致空間浪費。
那么，有沒有一種方法，可以解決這個問題呢？我們很容易就能想到：如果我們能讓數據元素“見縫插針”，不考慮相鄰位置，哪里有空位就插一個，這樣不就能充分利用空間了嗎？然后用一根“線”把它們按邏輯串起來，不就能完美解決這個問題了嗎？
至此，我們已經初窺鏈表，相比起順序表，它的組織形式更加靈活、自由。
一、溫故知新：順序表的“雙刃劍”
在探討鏈表之前，我們再總結一下“順序表”的優缺點。
核心優點
- 隨機訪問效率高: 存儲空間連續，可以通過索引直接定位元素，時間復雜度為
O(1)。 - 緩存友好: 連續的內存布局對CPU緩存更友好，遍歷速度通常更快。
核心痛點
- 操作成本高（時間維度）: 為了維持物理上的連續性，在中間插入或刪除一個元素后，需要移動大量后續元素，時間復雜度為
O(n)。這就像隊伍中間插進一個人，后面所有人都得挪一步。且數據量越大，成本就越高。 - 空間限制大（空間維度）:
- 必須預分配: 數組通常需要預先分配固定大小的空間。如果空間小了，需要經歷一個“申請新空間 -> 復制全部數據 -> 釋放舊空間”的昂貴擴容過程。
- 容易浪費或失敗: 如果空間大了，則造成內存浪費。更糟糕的是，如引言所述，在內存碎片化的情況下，即使總空間足夠，也可能因找不到足夠大的連續塊而申請失敗。
二、鏈式存儲結構：一次聰明的“解耦”
既然順序表的“物理連續”帶來了諸多不便，我們何不換個思路？那便是將元素的‘邏輯順序’與它們的‘物理位置’徹底解耦。這正是鏈表設計的核心思想：它放棄了對物理連續的執著，轉而選擇利用物理上不連續的空間，來表示邏輯上的連續。
1.鏈表的“細胞”——節點
與順序結構不同，鏈式結構中引入了它的基本單元——節點。每個節點除了要存儲數據元素信息外，還要存儲它的后繼元素的存儲地址。它的節點包含兩部分：
- 數據域：存儲數據元素信息。
- 指針域：存儲下一個節點的內存地址。
這里給出鏈表節點結構的定義：
typedef int Element_t;typedef struct _node {Element_t val; // 數據域struct _node *next; // 指針域
} node_t;
2.”節點“成“鏈”
有了節點這個基本單元，我們就可以把它們串聯起來了。將所有節點鏈結成一個鏈表，這就是線性表的鏈式存儲結構，因為此鏈表的每個節點只包含一個指針域，所以叫做單鏈表。
對于線性表來說，它一定有頭也有尾。一般而言，我們會設定一個特殊的指針，它永遠指向鏈表的第一個節點，我們叫它頭指針。有時為了方便，我們會在單鏈表的第一個節點前添加一個節點，稱為頭節點。使用頭節點的情況下，頭指針指向的就是這個頭節點，而不是第一個實際存儲數據的節點。頭節點的指針域存儲指向第一個節點的指針，數據域可以不存儲信息，也可以存儲如線性表長度等附加信息。單鏈表的最后一個節點，指針域通常指向NULL或者None，也就是“空”。
3.頭指針 vs 頭結點
| 特性 | 頭指針 | 頭節點 |
|---|---|---|
| 本質 | 一個指針變量 | 一個實際的節點對象 |
| 空表示 | head == NULL | head->next == NULL |
| 用途 | 標識鏈表的起始位置 | 簡化插入/刪除操作 |
| 插入/刪除 | 對第一個節點的操作是特殊的，需改動頭指針本身 | 所有位置的操作邏輯完全統一 |
| 優點 | 節省一個節點的內存 | 代碼邏輯更簡單、健壯，不易出錯 |
| 缺點 | 增刪邏輯復雜，需特殊判斷 | 增加了一個節點的內存開銷 |
| 是否必要 | 是 | 否 |
結論：在工程實踐中，為了代碼的簡潔和魯棒性，強烈推薦使用帶頭結點的鏈表。這點微小的空間犧牲是完全值得的。接下來的所有操作，我們都將基于帶頭結點的鏈表進行。
為了更好地管理鏈表，我們通常會再封裝一個結構體來代表整個鏈表：
// 定義鏈表頭結構
typedef struct {node_t head; // 頭節點int count; // 當前鏈表中有效數據節點的數量
} LinkList_t;
三、鏈表的基本功：核心操作詳解
現在，讓我們基于帶頭結點的鏈表 LinkList_t，來實現它的核心功能。
1.定義鏈表結構
鏈表的結構在第二部分已有說明，這里給出完整版：
typedef int Element_t;
// 1.定義鏈表節點結構
typedef struct _node {Element_t val;struct _node *next;
} node_t;// 2。定義鏈表頭結構
typedef struct {node_t head;int count;
} LinkList_t;
2.創建鏈表
首先，我們需要一個函數來創建一個空的鏈表。這包括為 LinkList_t 結構體分配內存，并初始化其內部的頭結點和計數器。
LinkList_t *createLinkList()
{// 1. 聲明一個指向LinkList_t的指針變量table，并初始化為NULL，防止野指針。LinkList_t *table = NULL;// 2. 在堆上申請一塊大小為`sizeof(LinkList_t)`的內存空間，將內存地址賦值給`table`。table = malloc(sizeof(LinkList_t));if (table == NULL) {return NULL; }// 3. 初始化鏈表結構體成員table->head.val = 0;table->head.next = NULL;table->count = 0;return table;
}
3.遍歷鏈表
由于鏈表物理上不連續，我們無法隨機訪問。唯一的辦法就是“順藤摸瓜”：從頭節點開始，沿著next指針一路走下去，直到遇到NULL。
void showLinkList(const LinkList_t* table)
{node_t *p = table->head.next; // 頭節點的下一個節點，也就是鏈表中第一個有效數據節點的指針，將p初始化為這個節點，作為遍歷的起點printf("link list:%d\n",table->count);while (p) {printf("%d\n",p->val); // 訪問當前節點的數據p = p->next; // 更新p為后繼節點}printf("\n"); // 打印換行符，使輸出更整潔
}
4.插入節點
插入新節點有四個步驟：
- 引入一個輔助指針
*p，p找到待插入位置的前一個位置的節點。 - 創建新節點。
- 更新新節點。
- 最后更新老節點。
插入操作詳解
頭插入（時間復雜度 O(1)）
-
頭指針
- 新節點直接指向原頭節點 x1
- 更新頭指針 x1 指向新節點
new_node->next = x1;
x1 = new_node;
-
頭節點
- 新節點指向頭節點的下一個節點
- 頭節點指向新節點
new_node->next = p->next;
p->next = new_node;
優勢： 頭插入是最高效的操作，時間復雜度恒為 O(1)，無需遍歷鏈表
任意位置插入（時間復雜度 O(n)）
這個指針修改動作本身是O(1)的，這正是鏈表效率高的原因。當然，找到這個p節點需要遍歷，耗時 O(n)。鏈表插入的精髓就在于這兩句指針操作：
new_node->next = p->next;
p->next = new_node;
這兩句代碼的順序是絕對不能調換的。
解讀這兩句代碼，可以看出是先把p的后繼節點改成新節點的后繼節點，再把新節點變成p的后繼節點。
如果把兩句代碼交換一下順序，會怎么樣？
第一句將p->next覆蓋成new_node的地址了。第二句new_node->next = p->next就相當于new_node->next = new_node，鏈表斷裂了。
尾插入（時間復雜度 O(n)）
p->next = new_node;
new_node->next = NULL;
C語言完整實現
頭插法
int insertLinkListHeader(LinkList_t* table, Element_t val)
{node_t *p = &table->head; // p指針指向頭節點node_t *new_node = malloc(sizeof(node_t)); // 創建新節點if (new_node == NULL)return -1;new_node->val = val;new_node->next = p->next;p->next = new_node;++table->count;return 0;
}
任意位置插入
int insertLinkListPos (LinkList* table, int pos, Element_t val)
{// 1.判斷邊界值if (pos < 0 || pos > table->count){printf("insert invalid!\n");return -1;}// 2.找到插入位置的前驅節點node_t *p = &table->head;int index = -1;while (index < pos - 1){p = p->next;index++;}if (p == NULL) {return -1;}// 3.創建新節點node_t *new_node = malloc(sizeof(node_t));new_node->val = val;// 4.插入新節點new_node->next = p->next;p->next = new_node;// 5.更新鏈表長度table->count++;return 0;
}
5.按值刪除節點
當我們要刪除某個節點時：
-
引入輔助指針p，p找到待刪除位置的前一個位置
-
引入輔助指針備份待刪除位置
tmp
tmp = p->next;
p->next = tmp->next;
free(tmp);
int deleteLinkListElement(LinkList_t* table, Element_t val)
{node_t *p = &table->head;while (p->next){if (p->next->val == val){break;}p = p->next;}if (p->next == NULL){printf("Not Found!\n");return -1;}node_t *tmp = p->next;p->next = tmp->next;free(tmp);table->count--;return 0;
}
6.銷毀鏈表
由于鏈表是節點和節點串聯起來的，當銷毀鏈表時，也需要逐個節點釋放內存，最后再釋放鏈表管理結構體本身的內存。
void releaseLinkList(LinkList_t* table)
{if (table){// 循環刪除每個節點node_t *p = &table->head;node_t *tmp; // 臨時保存要釋放的節點while (p->next){tmp = p->next;p->next = tmp->next;free(tmp);--table->count;}printf("LinkList have %d node!\n",table->count);free(table);}
}
四、順序表 vs. 單向鏈表
| 特性 | 順序表 | 單向鏈表 |
|---|---|---|
| 存儲方式 | 物理連續 | 物理離散 |
| 訪問方式 | 隨機訪問 (O(1)) | 順序訪問 (O(n)) |
| 插入/刪除 | 效率低，需移動元素 (O(n)) | 效率高，只需修改指針 (O(1)) (不含查找) |
| 空間管理 | 預分配，易浪費或需擴容 | 按需分配，靈活，但有指針額外開銷 |
| 適用場景 | 數據量固定，頻繁查找，很少增刪 | 數據量不固定，頻繁增刪，不關心隨機訪問 |
五、總結
今天，我們深入了解了單向鏈表。它通過犧牲隨機訪問的能力，換來了極其靈活的插入、刪除操作和高效的空間利用率。它與順序表并非“誰取代誰”的關系，不能簡單地說哪個好，哪個不好，需要根據實際情況來選擇。
掌握鏈表的關鍵，在于理解“指針”或“引用”如何將離散的內存串聯成一個邏輯整體。
但是，單向鏈表也并非完美。我們順著它只能一路向前，無法回頭，這在某些場景下非常不便。而且，它尾部節點的next指針永遠指向NULL，是不是有點“浪費”呢？
下一篇，我們將探索功能更強大的單向循環鏈表。同時，我們將嘗試僅使用頭指針來管理鏈表。
