数据结构基础：单向链表实现与原理

链表基础

链表是线性表的一种，表中的数据不必按顺序存储，而是在每一个节点里面存储下一个节点指针的数据结构。即物理位置非连续，逻辑位置连续。

由于物理位置非连续，无法通过寻常指针由第一个值直接到达第二个值，所以在单向链表的定义中，需要一个数据值和指针值，将一个个元素串起来。

1. 确定节点类型

确定完节点类型之后就可以定义单向链表了。

2. 定义链表结构体

为什么要使用 typedef？

如果不用 typedef，后续定义这个结构体的变量时，必须写完整的 struct Mynode：

// 不用 typedef 的写法（繁琐）
struct Mynode node1;

用了 typedef + NODE 之后，代码可以简化：

// 用 typedef 后的写法（简洁）
NODE node1;

对于链表的基本操作，我们需要明确以下几点：

3. 创建链表节点

4. 初始化链表

5. 销毁链表

先明确：这段代码的目标是彻底销毁链表。 需要做两件事：

1. 逐个释放链表中所有的节点（NODE）；
2. 释放链表的'管理结构体'（LL类型的变量），并将其置空。

逐行解析 while 循环里的操作

代码里的 (*pList)->pHead 是链表的头节点指针，while 循环的逻辑是逐个释放节点：

while ((*pList)->pHead) // 只要头节点不为空，就继续销毁 {
    pTemp = (*pList)->pHead; // 1. 先用 pTemp 保存'当前头节点'
    (*pList)->pHead = (*pList)->pHead->pNext; // 2. 把'头节点指针'往后移
    free(pTemp); // 3. 释放刚才保存的'原头节点'
}

• 如果写反（先 free 再移动头指针），会导致'释放后再访问节点的 pNext'，触发野指针错误；
• 现在的顺序是'先保存→再移指针→最后释放'，既保证能遍历所有节点，又不会访问已释放的内存。

循环后的操作（收尾）

free(*pList); // 释放链表的管理结构体（LL 类型）
*pList = NULL; // 把链表指针置空，避免野指针

pTemp和'当前节点'指向的是同一块内存，所以 free(pTemp) 本质是释放'这块内存'。

用'门牌号'的类比讲透：

• 链表的每个节点，都是一块'内存空间'（相当于一个'房子'）；
• 指针（比如 (*pList)->pHead、pTemp），相当于'房子的门牌号'，存的是房子的地址；
• 当执行 pTemp = (*pList)->pHead 时，相当于'把当前头节点（房子）的门牌号，复制了一份给 pTemp'——此时 pTemp 和 (*pList)->pHead 拿着同一个门牌号（指向同一块内存）。

而 free(指针) 的逻辑是：根据指针里存的'门牌号'，找到对应的'房子'，把房子拆掉（释放内存）。所以不管用哪个指针（pTemp 还是 (*pList)->pHead）调用 free，只要它存的是'当前节点的地址'，都会释放这个节点对应的内存。

至于这里的二阶指针 LL** pList，它的作用是让函数能修改外部传入的链表指针（比如最后 *pList = NULL），和'释放节点'本身没有关系。

6. 链表插入操作

A：尾部添加

有下标的插入：

想理解链表中间插入时节点连接的顺序问题，以及节点之间的变迁逻辑，这是链表操作的核心难点。我们先明确关键角色，再通过'错误顺序的坑'和'正确顺序的变迁'两步讲清楚，最后用形象比喻辅助理解。

一、先明确 3 个核心节点

在中间插入场景中，有 3 个关键节点（先固定它们的定义，避免混淆）：

1. temp2：前驱节点（插入位置的前一个节点，已经在链表中存在）
2. temp：新节点（我们要插入的节点，刚创建好，还未加入链表）
3. 后继节点：temp2->pnext（插入位置的后一个节点，原本跟在 temp2 后面，是链表的一部分）

初始状态（插入前）的节点关系：temp2 → 后继节点（temp 独立在链表外）。我们的目标：temp2 → temp → 后继节点（形成完整链路，不丢失任何节点）。

二、先看：颠倒顺序会发生什么

如果先执行 temp2->pnext = temp，再执行 temp->pnext = temp2->pnext，会直接破坏链路，形成环。

步骤 1：先执行 temp2->pnext = temp

• 操作含义：把 temp2 的'下一个节点'从'原本的后继节点'改成 temp。
• 节点变迁：① 原本 temp2→后继节点 的链路被切断；② 现在 temp2→temp；③ 关键问题：原本的'后继节点'彻底丢失了！因为没有任何指针指向它了，我们再也找不到这个节点的位置。

步骤 2：再执行 temp->pnext = temp2->pnext

• 操作含义：把 temp 的'下一个节点'赋值为 temp2->pnext（此时 temp2->pnext 已经是 temp）。
• 节点变迁：temp→temp（temp 的 next 指向它自己），形成闭环（链表成环）。

最终结果：链表链路变成 temp2→temp→temp→temp... 无限循环，原本的后继节点丢失，链表结构彻底损坏。

三、再看：正确顺序的节点变迁

正确顺序是：先执行 temp->pnext = temp2->pnext，再执行 temp2->pnext = temp，核心目的是'先保存后继节点，再修改前驱节点的指向'。

步骤 1：先执行 temp->pnext = temp2->pnext

• 操作含义：把 temp 的'下一个节点'，设置为 temp2 原本的'后继节点'。
• 节点变迁：① temp2→后继节点 的原始链路保持不变；② temp→后继节点（新节点先和'后面的节点'挂好钩）。

步骤 2：再执行 temp2->pnext = temp

• 操作含义：把 temp2 的'下一个节点'，从'原本的后继节点'改成 temp。
• 节点变迁：① temp2→后继节点 的原始链路被切断（但此时 temp 已经和后继节点挂钩，不怕丢失）；② temp2→temp；③ 最终形成完整链路：temp2→temp→后继节点，插入完成。

四、形象比喻

把链表节点比作火车车厢：

• temp2：火车的第 N 节车厢（前驱）
• temp：要插入的新车厢（第 N+1 节）
• 后继节点：火车的第 N+1 节车厢（原本的，插入后变成第 N+2 节）

1. 错误顺序（先连前驱，再连后继）：先把第 N 节车厢挂钩新车厢，此时第 N 节和原本的第 N+1 节断开，再也找不到原本的第 N+1 节车厢，最后新车厢只能自己挂钩自己，火车原地打转（成环）。
2. 正确顺序（先连后继，再连前驱）：先把新车厢挂钩原本的第 N+1 节车厢（确保后车厢不丢），再把第 N 节车厢挂钩新车厢，完成插入，火车链路完整。

总结

1. 核心原则：链表插入时，先保存（连接）后继，再修改（连接）前驱，避免丢失原本的后继节点。
2. 顺序颠倒的危害：丢失后继节点，形成链表环，导致遍历无限循环或程序崩溃。
3. 节点变迁核心：先让新节点'找到下家'，再让前驱节点'找到新节点'，最终形成完整链路。

要完成'头插'，必须保证 2 件事：

1. 新节点能'接'到原链表的前面；
2. 原链表的节点不会丢失。

为什么要先执行 temp->pnext = p->head？

p->head 是原链表的头节点，这一步的作用是：让新节点 temp 的'下一个节点'指向原链表的头节点——相当于把新节点'挂'到原链表的最前面，保证原链表的所有节点不会因为插入新节点而丢失。

7. 查找节点

1. LL* temp = p 是指针浅拷贝，temp 和 p 指向同一块链表结构体内存，修改 temp->head 本质上就是修改 p->head；
2. 遍历后原链表的 p->head 会被移动到第 ip 个节点，原头节点永久丢失，后续打印、插入都会错乱；
3. 你的初衷是保护原链表，但选了错误的临时指针类型（应该用 NODE* 遍历节点，而非 LL* 操作链表结构体）。

• 修正方法：使用 NODE* 类型临时指针遍历节点，不触碰链表结构体的 head。

核心在于它们指向的对象不同，修改的是不同层级的内容——LL* temp 修改的是「链表结构体本身」，而 NODE* tempNode 修改的是「临时指针的指向」，不会触动原链表的核心结构。

一、先分析你的写法：LL* temp = p 为什么会修改原链表

1. 第一步：LL* temp = p 是「指针浅拷贝」

• p 是 LL* 类型，指向一块链表结构体内存（里面存着 head、end、length 三个成员）；
• LL* temp = p 执行后，temp 和 p 是「两个不同的指针变量，但存储了同一个内存地址」（相当于两把钥匙，都能打开同一间房子）；
• 此时，temp 和 p 指向同一个链表结构体，修改 temp 的成员，就是修改 p 的成员。

2. 第二步：temp->head = temp->head->pnext 是「修改链表结构体的核心成员」

• temp->head 访问的是「链表结构体」中的 head 成员；
• 你给 temp->head 赋值，本质上是修改了这块链表结构体内存中 head 成员的值；
• 因为 temp 和 p 指向同一个结构体，所以 p->head（原链表的头指针）也会被同步修改。

二、再分析正确写法：NODE* tempNode = p->head 为什么不会修改原链表

1. 第一步：NODE* tempNode = p->head 是「复制节点的地址」

• p->head 是链表结构体中的成员，存储的是「头节点的内存地址」；
• NODE* tempNode = p->head 执行后，tempNode 存储了「头节点的地址」，它指向的是「节点内存」，而不是「链表结构体内存」。

2. 第二步：tempNode = tempNode->pnext 是「修改临时指针自身的指向」

• 这个操作只是修改了 tempNode 这个指针变量本身存储的地址；
• 它没有修改「链表结构体」中的任何成员（p->head 仍然存储着原来的头节点地址）。

三、核心区别总结

写法	指向的对象	操作的本质	是否修改原链表
LL* temp = p; temp->head = ...	原链表结构体（LL 类型）	修改链表结构体的 head 成员	是（破坏原链表）
NODE* tempNode = p->head; tempNode = ...	链表节点（NODE 类型）	仅修改临时指针自身的指向	否（保护原链表）

8. 链表扩展

双向链表

其实就是在有 next 的基础上多加一个 front，万变不离其宗，后面对应的函数封装自己可以根据需要来加 front，原则上只要保证链表的连接性完整就可以。

循环链表

head=end，这边不多做赘述。

9. 遍历与打印

利用 while 循环和 next 原理对链表中的数据进行打印：

以下是完整代码示例：

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

typedef struct Mynode {
    int data;
    struct Mynode* pnext;
} NODE;

// 链表节点的创建，一个值，一个用于连接节点的指针

typedef struct mylist {
    NODE* head;
    NODE* end;
    int length;
} LL;

// 这是我规定的一个单向链表，里面有头有尾，有长度

LL* create() {
    LL* p = (LL*)malloc(sizeof(LL));
    if (p == NULL) {
        printf("创建链表失败");
        return NULL;
    }
    p->head = NULL;
    p->end = NULL;
    p->length = 0;
    return p;
}

// 创建一个为空的链表

NODE* createnode(int data) {
    NODE* PN = (NODE*)malloc(sizeof(NODE));
    if (PN == NULL) {
        printf("为链表节点申请内存失败");
        return NULL;
    }
    PN->data = data;
    PN->pnext = NULL;
    return PN;
}

void destory(LL** p) {
    if (p == NULL) {
        printf("链表本身不存在，无需销毁");
    }
    NODE* temp = NULL;
    while ((*p)->head) {
        temp = (*p)->head;
        (*p)->head = (*p)->head->pnext;
        free(temp);
    }
    free(*p);
    *p = NULL;
}

void putlast(LL* p, int target) {
    if (NULL == p) {
        printf("链表不存在，无法添加");
        return;
    }
    NODE* temp = createnode(target);
    if (temp == NULL) {
        printf("为数值创建节点失败");
        return;
    }
    if (NULL == p->head) {
        p->head = p->end = temp;
    } else {
        p->end->pnext = temp;
        p->end = temp;
    }
    p->length++;
}

void putmid(LL* p, int ip, int target) {
    if (NULL == p) {
        printf("链表不存在，无法添加");
        return;
    }
    NODE* temp = createnode(target);
    NODE* temp2 = p->head;
    if (temp == NULL) {
        printf("为数值创建节点失败");
        return;
    }
    if (ip <= 0 || p->length == 0) {
        temp->pnext = p->head;
        p->head = temp;
        if (p->length == 0) {
            p->end = temp;
        }
    } else if (ip >= p->length) {
        p->end->pnext = temp;
        p->end = temp;
    } else {
        for (int i = 0; i < ip - 1; i++) {
            temp2 = temp2->pnext;
        }
        temp->pnext = temp2->pnext;
        temp2->pnext = temp;
    }
    p->length++;
}

NODE* found(LL* p, int ip) {
    if (NULL == p || p->length == 0) {
        printf("链表无法查找\n");
        return NULL;
    }
    if (ip < 0 || ip > p->length) {
        printf("查找位置非法（超出链表长度）\n");
        return NULL;
    }
    NODE* tempNode = p->head;
    for (int i = 0; i < ip - 1; i++) {
        tempNode = tempNode->pnext;
    }
    return tempNode;
}

void printd(LL* p) {
    if (p == NULL) {
        printf("链表本身不存在，无法打印");
        return;
    }
    if (p->length == 0) {
        printf("无法打印");
        return;
    }
    NODE* temp = p->head;
    while (temp != NULL) {
        printf("%d", temp->data);
        temp = temp->pnext;
    }
}

int main() {
    LL* p = create();
    putmid(p, 0, 1);
    putmid(p, 1, 2);
    putmid(p, 2, 3);
    NODE* s = found(p, 0);
    putlast(p, s->data);
    putmid(p, 2, s->data);
    // destory(&p);
    printd(p);
    return 0;
}