欢迎来到  大白话  数据结构专区   我是 

-1.复习一下 吧 顺序表的主要操作 是依靠数组底层的下标索引来，移动来增删查改运算    但是  链表  主要是体现链接   指针  起着重要作用通过指向下个节点的 来将所有节点串起来   合并成  一整个链表  

所以链表的运算  是通过唯一的指针指向的转变  存储 另一个节点的指针来实现的 

所以 链表不是连续的空间   是单独 独立的一个个节点  组合起来的  线性表   

线性   简单的理解：像“排队”

想象你在食堂排队买饭：

有序性：每个人都有一个固定的位置（第1个、第2个……）。

单一性：除了排头和排尾，你前面只有一个人，后面也只有一个人。

同类性：排队的通常都是人，不会排着排着中间插进一只大象（数据类型相同）。

 

为啥要用链表呢    有啥优势吗？ 那绝对有牛皮的地方哈

简单介绍一下

1. 插入和删除效率极高（不需要“大搬家”）

这是链表最大的杀手锏。

• 顺序表（数组）：如果你要在第 1 个位置插入一个数，后面所有的元素都要向后挪一位。如果数组有一万个元素，就要挪一万次。

• 链表：只需要修改指针的指向。就像你之前代码里写的，删掉头节点只需要让 *pphead 指向 next，其他节点动都不用动。

  • 效率对比：链表操作通常是 $O(1)，顺序表则是 $O(n)。

2. 内存利用更灵活（按需申请，不浪费）

• 顺序表：需要一块连续的内存空间。如果你申请了 100 个位置但只用了 10 个，剩下的 90 个就浪费了；如果你想存第 101 个，对不起，装不下了，必须整体搬迁。

• 链表：内存是“碎片化”利用的。哪里有空位就可以在哪里申请一个节点，每个节点通过指针串起来。

• 优势：没有固定容量限制，只要电脑还有内存，链表就能一直长下去。

3. 增容代价极小

顺序表：当空间满了需要增容时，系统通常要找一块更大的新地皮，把旧数据全部拷贝过去，再释放旧地皮。这个“整体搬迁”的过程非常耗时。

链表：每增加一个元素，就申请一个元素的空间，完全不存在拷贝旧数据的负担。

0.总所周知  插入可以 从头插入叫头插   尾部 最末尾插入叫做 尾插   区别

1  尾插  逻辑  通过在顺序表 （上图中）的学习和了解  在插入前必须判断是否顺序表的空间 为空 

那么在链表里  分为  空链表 和  非空链表 下面是代码的实现  

每一个节点都要单独去开辟 为何不写一个函数来简化 ，每次只要调用函数即可

SLTNode* CreateNewNode(SLTDataType x) 
{
    // 1. 向堆内存申请一个节点大小的空间
    SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
    
    // 2. 检查 malloc 是否成功（严谨的程序员必做）
    if (newNode == NULL) 
    {
        perror("malloc failed"); // 打印错误信息
        exit(-1);               // 终止程序
    }
    
    // 3. 初始化节点成员
    newNode->data = x;    // 存入数据
    newNode->next = NULL; // 新节点的 next 暂时指向空
    
    // 4. 返回这个新节点的地址
    return newNode;
}

该 函数 就是用来创建单个节点的 

尾插  需要先找到尾部的节点 将它的下个节点本来是空  换成 新的节点 重点是 特殊情况 比方说 

本来为空链表  就 直接把新开辟的节点 给最为新的头节点  

其他的就正常找尾部   主要是  循环条件   控制主要就是 利用最后一个节点的指向空  来判断结束 从而在循环结束后找到尾部  并将原本  指向 NULL的指针指向  新的节点   ---就是 将指针变量 存储的 值（地址 ） 修改  为新的节点的地址   

但是 要修改一级指针的值  需要传递地址  存储一级指针的地址的变量    就是 二级指针

之所以形参要用 **（二级指针），而不是你说的“直接用一级指针 * 接收地址”，核心原因在于要修改的目标本身就是一个指针，这受制于 C 语言严格的类型匹配原则。

我们可以这样一步步来捋：

1. 明确想要修改什么？

在链表操作中（比如头插、头删），我们需要修改的是头指针（也就是图里的 plist），让它指向新的节点或者下一个节点。

既然要修改 plist 这个变量，就必须把 plist 的真实物理地址传给函数。

2. C 语言的“套娃”类型规则

C 语言接收地址时，形参的星星数量 *，必须比原变量的类型多一颗。

• 普通变量： 假设有一个整数 int a = 10; 你要在函数里修改 a，必须传 a 的地址 &a。 接收 &a 的形参，类型得是 int*（一级指针）。

• 指针变量（这就是你的情况）： 的 plist 本身就是一个指针了，类型是 SLTNode*。 你要在函数里修改 plist，必须传 plist 的地址，也就是 &plist。 既然原类型是 SLTNode*，那么接收它地址的形参类型，自然就得多加一颗星，变成 SLTNode**（二级指针）。

2。头插  主要步骤就是  创建新节点

     1.将新节点    指向原来的头节点 特殊情况 原链表为空也是可以的）

  2.改成新的头节点    将 *pphead指向新的节点  

3.尾删    下图只是只是大部分情况适用 主要是循环找尾部的过程中  保留倒数第二个指针  释放掉原来最后一个节点 在将原来倒数第二个 （尾删后的倒数第一个） 指向 空 最为新的倒数第一个节点 

转折  这样就可以了嘛，你仔细想想如果只有单独的一个节点时，会出现什么情况？想不清楚就去画个图取看看效果，会出现问题的    

当只有一个节点的时候 ，此时 结合代码可知 根本就没进入循环  ptail ->next指针指向空  

不会进入循环 便将ptail  释放掉之后再置为空  但是  因为并没有进入循环所以说 ptail

并不会 改变   故 ptail  依旧 与  prve  == *pphead 相等   但是     

pre->next = NULL;这一行就会出bug  因为不能对空指针解引用的