带头结点单链表头插法核心逻辑总结（基于代码实操）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 数据元素类型（以int为例）
typedef int ElemType;

// 链表结点结构体定义
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;

// -------------------------- 头插法相关 --------------------------
// 初始化带头结点的链表（供头插法使用）
bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) return false;
    L->next = NULL;
    return true;
}

// 头插法：插入元素e到头结点之后
bool HeadInsert(LinkList& L, ElemType e) {
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = L->next;  // s指向原首元结点
    L->next = s;        // 头结点指向s（新首元结点）
    return true;
}

// -------------------------- 尾插法相关 --------------------------
// 初始化链表（含尾指针，供尾插法使用）
void InitListWithTail(LinkList& L, LNode*& r) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) exit(1);
    L->next = NULL;
    r = L;  // 尾指针初始指向头结点
}

// 尾插法：插入元素e到链表末尾（需传入尾指针r）
bool TailInsert(LinkList& L, LNode*& r, ElemType e) {
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = NULL;     // 新尾结点next必为NULL
    r->next = s;        // 原尾结点连接新结点
    r = s;              // 尾指针更新为s
    return true;
}

// -------------------------- 辅助函数 --------------------------
// 打印链表
void PrintList(LinkList L) {
    LNode* p = L->next;
    if (p == NULL) {
        printf("链表为空\n");
        return;
    }
    printf("链表元素：");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 销毁链表（释放内存）
void DestroyList(LinkList& L) {
    LNode* p = L;
    while (p != NULL) {
        LNode* q = p->next;
        free(p);
        p = q;
    }
    L = NULL;
}

// -------------------------- 测试主函数 --------------------------
int main() {
    // 1. 测试头插法（插入1、2、3，预期结果：3 2 1）
    LinkList L1;
    InitList(L1);
    HeadInsert(L1, 1);
    HeadInsert(L1, 2);
    HeadInsert(L1, 3);
    printf("头插法结果（插入1、2、3）：\n");
    PrintList(L1);  // 输出：3 2 1
    DestroyList(L1);

    // 2. 测试尾插法（插入1、2、3，预期结果：1 2 3）
    LinkList L2;
    LNode* r2;  // 尾指针
    InitListWithTail(L2, r2);
    TailInsert(L2, r2, 1);
    TailInsert(L2, r2, 2);
    TailInsert(L2, r2, 3);
    printf("\n尾插法结果（插入1、2、3）：\n");
    PrintList(L2);  // 输出：1 2 3
    DestroyList(L2);

    return 0;
}

一、核心前提

头插法是将新结点插入到「头结点与原首元结点之间」，让新结点成为新首元结点的操作，核心是通过两步指针调整，确保新结点接入链表且原链表不中断，依赖 L->next（头结点指针域）和 s->next（新结点指针域）的协作。

二、关键概念定义（避免混淆）

1. 头结点：L 指向的结点，不存有效数据，仅用于统一链表操作（初始化时通过 malloc 创建，整个链表仅 1 个）；
2. 首元结点：头结点 L->next 指向的结点，是链表中第一个存有效数据的结点；
3. 原首元结点：插入新结点前，L->next 原本指向的首元结点（记为 p）；
4. 新结点 s：每次插入时通过 malloc 新分配的结点，用于存储待插入的有效数据 e。

三、头插法三步核心操作（对应代码）

假设插入前链表状态：头结点 L → 原首元结点 p → 后续结点 q → NULL（若链表为空，则 L->next = NULL，p 不存在）。

1. 第一步：给新结点存数据（s->data = e）

• 作用：将待插入的有效数据 e 存入新结点 s 的数据域 data；
• 本质：为新结点 “填充内容”，否则新结点仅为空白内存，无法存储数据。

2. 第二步：新结点接住原首元结点（s->next = L->next）

• 作用：将 L->next中存储的原首元结点 p的地址，赋值给 s->next；
  • 若链表为空（L->next = NULL）：则 s->next = NULL，新结点后续后续无结点；
  • 若链表非空：则 s->next 指向 p，确保原链表的 p→q→... 部分不丢失（避免断链）。
• 注意：此时 s 未接入链表，仅通过 s->next 与原链表建立了关联（s 是 “游离结点”，链表入口 L->next 仍指向 p）。

3. 第三步：头结点接入新结点（L->next = s）

• 作用：将新结点 s 的地址赋值给 L->next，修改链表入口的指向；
• 本质：这是新结点 s 正式 “加入链表” 的关键一步 —— 此时 L->next 不再指向 p，而是指向 s，s 成为新的首元结点。

四、最终结果（链表结构变化）

操作阶段	链表结构（箭头表示指针指向）	核心变化
插入前	L（头结点）→ p（原首元）→ q → NULL	L->next 指向 p
执行 s->data = e	L→p→q→NULL；s（存 e）	s 有数据，未关联链表
执行 s->next = L->next	L→p→q→NULL；s→p	s 关联 p，仍游离
执行 L->next = s	L→s（新首元）→ p→q→NULL	s 接入链表，成为新首元

五、核心原则

1. 先接后断：必须先让 s->next 接住原首元结点（避免原链表丢失），再修改 L->next 指向 s（接入新结点），顺序不可反；
2. 动态内存：头结点仅初始化时 malloc 1 次，每次插入新数据都需重新 malloc 新结点 s（每个数据分配独立存储）；
3. 指针本质：L->next 和 s->next 是 “存储地址的变量”，操作的是 “地址传递”，而非结点本身的移动。

---

尾插法核心逻辑

前提：主函数中的调用代码（先明确外部变量）

首先看主函数里怎么调用这两个函数的，后续流程都围绕这几个变量展开：

void InitListWithTail(LinkList& L, LNode*& r) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) exit(1);
    L->next = NULL;
    r = L;  // 尾指针初始指向头结点
}

// 尾插法：插入元素e到链表末尾（需传入尾指针r）
bool TailInsert(LinkList& L, LNode*& r, ElemType e) {
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = NULL;     // 新尾结点next必为NULL
    r->next = s;        // 原尾结点连接新结点
    r = s;              // 尾指针更新为s
    return true;
}

前提：主函数里先定义两个空指针

• 定义 LinkList L2（等价于 LNode* L2）：此时 L2 没有指向任何内存（空指针）；
• 定义 LNode* r2：此时 r2 也没有指向任何内存（空指针）。

一、执行 InitListWithTail(L2, r2)（初始化，实参为 L2 和 r2）

1. L = (LNode*)malloc(sizeof(LNode));
   • 作用：给形参 L（L2 的引用，改 L 即改 L2）分配一块内存，用来存 “头结点”；
   • 变量变化：L2 从空指针，变为指向这块新内存（头结点）；
   • 链表内容：[头结点（刚分配，暂未设置 next）]（仅存在头结点，未形成完整链表）。
2. if (L == NULL) exit(1);
   • 作用：检查内存是否分配成功，失败则退出程序，成功则继续；
   • 变量变化：无（L2 仍指头头结点）；
   • 链表内容：不变（仍为 [头结点]）。
3. L->next = NULL;
   • 作用：操作 L2 指向的头结点，把它的 next 设为 NULL（表示头结点后暂无数据节点）；
   • 变量变化：头结点的 next 成员从随机值变为 NULL；
   • 链表内容：[头结点] → NULL（初始化完成，链表结构完整，无数据）。
4. r = L;
   • 作用：给形参 r（r2 的引用，改 r 即改 r2）赋值，让 r2 也指向头结点；
   • 变量变化：r2 从空指针，变为指向头结点（与 L2 指向同一位置）；
   • 链表内容：不变（仍为 [头结点] → NULL）。

二、执行 TailInsert(L2, r2, 1)（插入参数 1，实参为 L2、r2、1）

1. LNode* s = (LNode*)malloc(sizeof(LNode));
   • 作用：定义临时指针 s，分配新内存存 “要插的节点”；
   • 变量变化：s 指向这块新内存（暂未存数据）；
   • 链表内容：不变（仍为 [头结点] → NULL，新节点未接入）。
2. if (s == NULL) return false;
   • 作用：检查新节点内存是否成功，失败返回 false，成功继续；
   • 变量变化：无（s 仍指向新内存）；
   • 链表内容：不变（[头结点] → NULL）。
3. s->data = e;
   • 作用：把参数 e（即 1）存入 s 指向的新节点；
   • 变量变化：新节点的 data 成员变为 1；
   • 链表内容：不变（新节点存了 1，但未接入，仍为 [头结点] → NULL）。
4. s->next = NULL;
   • 作用：把新节点的 next 设为 NULL（它要当新末尾，末尾节点 next 必为 NULL）；
   • 变量变化：新节点的 next 成员变为 NULL；
   • 链表内容：不变（新节点结构完整，但未接入，仍为 [头结点] → NULL）。
5. r->next = s;
   • 作用：r 是 r2 的引用，当前 r2 指头结点，让头结点的 next 指向 s（新节点），把 1 接入链表；
   • 变量变化：头结点的 next 从 NULL 变为指向新节点（存 1 的节点）；
   • 链表内容：变化为 [头结点] → [1] → NULL（1 成功接在头结点后）。
6. r = s;
   • 作用：更新 r2，让 r2 从 “头结点” 改指向 s（存 1 的节点），使其成为新的末尾指针；
   • 变量变化：r2 指向从 “头结点” 变为 “存 1 的节点”；
   • 链表内容：不变（仍为 [头结点] → [1] → NULL）。
7. return true;
   • 作用：返回 true 表示插入成功；
   • 变量变化：无；
   • 链表内容：最终为 [头结点] → [1] → NULL。

三、执行 TailInsert(L2, r2, 2)（插入参数 2，实参为 L2、r2、2，此时 r2 指向存 1 的节点）

1. LNode* s = (LNode*)malloc(sizeof(LNode));
   • 作用：分配新内存存 “要插的节点”，s 指向它；
   • 变量变化：s 指向新内存；
   • 链表内容：不变（[头结点] → [1] → NULL）。
2. if (s == NULL) return false;
   • 作用：检查内存，成功继续；
   • 变量变化：无；
   • 链表内容：不变。
3. s->data = e;
   • 作用：把参数 2 存入 s 指向的新节点；
   • 变量变化：新节点 data 为 2；
   • 链表内容：不变。
4. s->next = NULL;
   • 作用：新节点 next 设为 NULL；
   • 变量变化：新节点 next 为 NULL；
   • 链表内容：不变。
5. r->next = s;
   • 作用：r 即 r2（指向存 1 的节点），让存 1 的节点 next 指向新节点（存 2）；
   • 变量变化：存 1 的节点 next 从 NULL 变为指向存 2 的节点；
   • 链表内容：变化为 [头结点] → [1] → [2] → NULL。
6. r = s;
   • 作用：r2 改指向存 2 的节点（新末尾）；
   • 变量变化：r2 指向存 2 的节点；
   • 链表内容：不变。
7. return true;
   • 作用：插入成功；
   • 链表内容：最终为 [头结点] → [1] → [2] → NULL。

四、执行 TailInsert(L2, r2, 3)（插入参数 3，实参为 L2、r2、3，此时 r2 指向存 2 的节点）

1. LNode* s = (LNode*)malloc(sizeof(LNode));
   • 作用：分配新内存存 “要插的节点”，s 指向它；
   • 变量变化：s 指向新内存；
   • 链表内容：不变（[头结点] → [1] → [2] → NULL）。
2. if (s == NULL) return false;
   • 作用：检查内存，成功继续；
   • 变量变化：无；
   • 链表内容：不变。
3. s->data = e;
   • 作用：把参数 3 存入 s 指向的新节点；
   • 变量变化：新节点 data 为 3；
   • 链表内容：不变。
4. s->next = NULL;
   • 作用：新节点 next 设为 NULL；
   • 变量变化：新节点 next 为 NULL；
   • 链表内容：不变。
5. r->next = s;
   • 作用：r 即 r2（指向存 2 的节点），让存 2 的节点 next 指向新节点（存 3）；
   • 变量变化：存 2 的节点 next 从 NULL 变为指向存 3 的节点；
   • 链表内容：变化为 [头结点] → [1] → [2] → [3] → NULL。
6. r = s;
   • 作用：r2 改指向存 3 的节点（新末尾）；
   • 变量变化：r2 指向存 3 的节点；
   • 链表内容：不变。
7. return true;
   • 作用：插入成功；
   • 链表内容：最终为 [头结点] → [1] → [2] → [3] → NULL。