帶頭結點的單鏈表插入方法（頭插法與尾插法）

在單鏈表的操作中，插入是最常見的操作之一，本文介紹 帶頭結點的單鏈表 如何實現 后插法 和 前插法（包括 插入法 和 后插數據交換法），并提供完整的 C++ 代碼示例。

---

1. 鏈表的基本結構

在 帶頭結點 的單鏈表中，頭結點 L 僅作為占位符，不存儲數據，鏈表的數據從 L->next 開始。

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node, *List;

• data：存儲節點數據。
• next：指向下一個節點的指針。
• List：定義指向 Node 的指針類型，表示鏈表。

---

2. 鏈表初始化

bool Init(List &L) {L = (Node *)malloc(sizeof(Node));  // 創建頭結點L->next = NULL;return true;
}

• L 作為頭結點，僅占位，不存儲數據。
• L->next = NULL 表示鏈表為空。

---

3. 后插法（在指定位置后插入）

3.1 后插法介紹

后插法 是指在 某個指定位置 i 之后 插入新的節點，即：

原鏈表： A -> B -> C -> NULL
插入后： A -> B -> X -> C -> NULL （X 插入到 B 之后）

3.2 后插法代碼

bool Insert(List &L, int i, int value) {Node *p = L;  // p 指向頭節點int j = 0;// 找到 i-1 位置的節點while (p != NULL && j < i - 1) {  p = p->next;  j++;}if (p == NULL) { // 如果 i 超出鏈表長度，插入失敗return false;}// 創建新節點Node *s = (Node *)malloc(sizeof(Node));s->data = value;// 插入s->next = p->next;p->next = s;return true;
}

3.3 代碼解析

1. 找到 i-1 位置的節點：
   • 通過 while 循環找到第 i-1 個節點 p，使 p->next 指向新節點。
2. 創建新節點 s：
   • 分配內存，存入 value。
3. 新節點 s 指向 p->next：
   • s->next = p->next，讓新節點連接到 p 的下一個節點。
4. p 連接到 s：
   • p->next = s，完成插入。

3.4 運行示例

void PrintList(List L) {Node *p = L->next;  // 跳過頭節點while (p != NULL) {printf("%d -> ", p->data);p = p->next;}printf("NULL\n");
}int main() {List L;Init(L);Insert(L, 1, 10);Insert(L, 2, 20);Insert(L, 3, 30);PrintList(L);return 0;
}

運行結果

10 -> 20 -> 30 -> NULL

---

4. 后插法實現前插法（交換數據法）

4.1 介紹

前插法 是指在 某個指定位置 i 之前 插入新節點：

原鏈表： A -> B -> C -> NULL
插入后： A -> X -> B -> C -> NULL （X 插入到 B 之前）

如果我們仍然使用后插法，可以通過 交換數據 來模擬前插效果：

1. 找到 i 位置的節點 p。
2. 使用后插法 在 p 后面 插入一個新節點 s。
3. 交換 p 和 s 的 data，這樣 p 的數據變成新插入的數據，而 s 變成原 p 的數據。

當然 這里也可以使用 直接插入法 不過 需要從頭 遍歷鏈表 至其前驅結點 ，這里沒有實現

4.2 代碼

bool Insert(List &L, int i, int value) {if (i < 1) return false;Node *p = L;int j = 0;// 找到第 i 個位置的節點 pwhile (p->next != NULL && j < i - 1) {  p = p->next;j++;}if (p == NULL) return false;// 使用后插法創建新節點 sNode *s = (Node *)malloc(sizeof(Node));s->data = value;s->next = p->next;p->next = s;// **交換數據**，實現前插效果int temp = p->data;p->data = s->data;s->data = temp;return true;
}

4.3 運行示例

int main() {List L;Init(L);Insert(L, 1, 10);Insert(L, 2, 20);Insert(L, 3, 30);Insert(L, 2, 15); // 插入 15 到第 2 個位置PrintList(L);return 0;
}

輸出

10 -> 15 -> 20 -> 30 -> NULL

15 被正確插入到了 20 之前，達到了前插的效果。

---

5. 總結

	后插法	前插法（交換數據法）
插入方式	在 第 i 個節點 之后插入	在 第 i 個節點 之前插入
鏈表變化	A -> B -> X -> C	A -> X -> B -> C
i=1 時的情況	頭結點不變，只插入到 L->next 之后	頭結點改變，新節點變成 L
適用場景	常用于 順序插入，如尾插法	適用于 倒序插入，如頭插法
優點	邏輯清晰，適用于大多數情況	結構不變，適用于數據交換優化

兩種插入方式的使用場景不同，在 動態鏈表管理 中，后插法適合 正常數據流，前插法適合 逆序處理。

---

6. 參考代碼完整示例

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node, *List;bool Init(List &L) {L = (Node *)malloc(sizeof(Node));L->next = NULL;return true;
}bool Insert(List &L, int i, int value) {if (i < 1) return false;Node *p = L;int j = 0;while (p->next != NULL && j < i - 1) {  p = p->next;j++;}if (p == NULL) return false;Node *s = (Node *)malloc(sizeof(Node));s->data = value;s->next = p->next;p->next = s;int temp = p->data;p->data = s->data;s->data = temp;return true;
}

希望本文能幫助新手更好地學習C++鏈表的學習！