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

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

在单链表的操作中，插入是最常见的操作之一，本文介绍 带头结点的单链表 如何实现 后插法 和 前插法（包括 插入法 和 后插数据交换法），并提供完整的 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 个位置的节点 p
    while (p->next != NULL && j < i - 1) {  
        p = p->next;
        j++;
    }

    if (p == NULL) return false;

    // 使用后插法创建新节点 s
    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;
}

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. 总结

两种插入方式的使用场景不同，在 动态链表管理 中，后插法适合 正常数据流，前插法适合 逆序处理。

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++链表的学习！