带头结点 的单链表插入方法（头插法与尾插法）

带头结点的单链表插入方法（头插法与尾插法）

在单链表的操作中，插入是最常见的操作之一，本文介绍 带头结点的单链表 如何实现 后插法 和 前插法（包括 插入法 和 后插数据交换法），并提供完整的 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++链表的学习！