数据结构-单链表专题
上期我们介绍了顺序表的应用，我们知道了，顺序表的底层是数组。其中，动态顺序表比静态顺序表更方便。但是，针对顺序表的问题：中间头部插入效率低下，增容影响运行效率，增容造成空间浪费。如何解决？这就要介绍本章的内容：链表
1.链表的概念
1.1概念
链表也是线性表的一种~
- 线性表：物理结构：不一定连续；逻辑结构：一定是连续的
- 链表：物理结构：不是线性的；逻辑结构：是线性的
2.链表的结构
2.1结构
可以拿火车车厢举例：
火车由一节节车厢相连组成，每节车厢都是通过钩锁连接起来的，是独立的个体。
类比：
火车是由一节节车厢组成的，
链表就是由一节节的节点组成。
2.2节点的结构
节点由什么组成呢？
数据+指向下一个节点的指针
当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
由此可知，我们只要弄清楚节点的结构，就弄清了链表的结构。那么，程序中如何定义链表的节点的结构呢？
//定义节点的结构
//数据+指向下一个节点的指针
typedef int SLTDataType;
typedef struct SListNode{
SLTDataType data;
struct SListNode* next;//指向下一个节点的指针
}SLTNode;
当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
3.单链表的实现
3.1打印
实现链表的打印功能前，我们需要先创建一个链表。而链表是由一个个节点组成，因此我们可以先创建几个节点，在连接起来就成了链表。
链表物理结构不是线性的，逻辑结构是线性的。
SList.c
//链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while(pcur)//pcur!=NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
test.c
//测试 链表的打印
void SListTest01()
{
//链表是有一个个节点组成
//创建几个节点
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2= (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;
//将四个节点连接起来
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
//调用链表的打印
SLTNode* plist = node1;
SLTPrint(plist);
}
在上述测试案例中，我们手动创建了几个节点并把他们连接起来，到后面，我们会学习头插尾插，更方便一些~
3.2尾插
实现尾插的思路：找到尾节点，将尾节点跟新的要插入的节点连接起来。
//尾插代码实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//*pphead就是指向第一个节点的指针
//SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* newnode = SLTBuyNode(x);
//空链表和非空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else {
//找尾
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;//继续往下走
}
//pail指向的就是尾节点
ptail->next = newnode;
}
}
分析：
step1:SLTBuyNode()函数即创建一个新节点存储要尾插的数据x，然后开始找尾，先让ptail也指向第一个节点，往后递进，当ptail->next为NULL时，就找到了尾，最后将新节点与ptail->next连接即可。
step2:但是当链表为空链表时呢？ptail就变成了空指针，那么ptail->next对空指针进行解引用，代码一定会报错！因此，需要分别讨论：空链表与非空链表。
step3:当为非空链表时，即phead==NULL,插入一个新节点newnode,只需将newnode变为首节点，即令phead=newnode
step4：为什么要传地址&plist，用二级指针**pphead? 这步也是最关键的一步！！！
-
在单链表中，头指针（pphead）指向链表的第一个节点。
-
如果链表为空（pphead 为 NULL），插入新节点时，需要将头指针指向新节点。
-
如果链表不为空，插入新节点时，头指针不需要修改，但需要找到尾节点并修改尾节点的 next 指针。
-
如果头指针需要被修改（例如链表为空时），必须通过传递头指针的地址来实现。
-
在 C 语言中，函数参数是按值传递的，即函数内部对参数的修改不会影响外部的变量。
-
如果直接传递头指针（SLTNode* pphead），函数内部对 pphead 的修改（例如 pphead = newnode）只会影响函数内的局部变量，而不会影响外部的头指针。
-
通过传递头指针的地址（SLTNode** pphead），函数可以通过解引用修改外部的头指针。
总结：
- 传递地址是为了让函数能够修改外部的头指针。
- 如果链表为空，头指针需要被修改为指向新节点。
- C 语言的按值传递机制决定了必须通过传递指针的地址来实现对指针本身的修改。
到这里为止，尾插所有的坑咱们已经踩完啦！！！
3.3头插
//头插代码实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//连接
newnode->next = *pphead;
*pphead = newnode;
}
3.4尾删
step1:确保传入的 pphead 不是 NULL，且链表不为空，即
（*pphead 不是 NULL），assert(pphead&&*pphead)
step2:实现尾删我们可能想的是：将最后一个节点释放free掉就完事了，但是，这样的话倒数第二个节点的指针就指向了NULL，成了野指针。因此，我们要在free掉尾节点之后将尾节点的指针ptail置空，同时将倒数第二个节点的指针prev置空。
step3:如果链表只有一个节点，直接free掉，并将ptail置空即可
step4:如果链表有多个节点，则进行找尾节点并free掉后，将尾指针ptail和其前驱节点prev->next都置空即可。
总结：
- 二级指针的作用：通过 SLTNode** pphead 可以修改链表头指针本身，适用于头删操作。
- 内存管理：使用 free 释放头节点的内存，避免内存泄漏。
- 边界条件：如果链表只有一个节点，删除后链表为空，头指针 *pphead 被置为 NULL。
- 通过二级指针和保存下一个节点，实现了对头节点的删除和头指针的更新。
3.5头删
头删就很简单了，首先得保存头节点的下一个节点 SLTNode* next = (*pphead)->next，因为如果没保存直接删除头节点的话，就直接与后边的节点失去了联系，找不到了; 然后删除头节点；最后更新头指针，指向新的节点。
//头删
void SLTPopFront(SLTNode** pphead)
{
// 1. 检查链表是否为空
assert(pphead && *pphead);
// 2. 保存头节点的下一个节点
SLTNode* next = (*pphead)->next;
// 3. 释放当前头节点
free(*pphead);
// 4. 更新头指针，指向新的头节点
*pphead = next;
}
好了，以上就是单链表的有关内容，是不是比较简单呀？弄清了尾删部分的代码原理，我相信很快就能理解全部内容啦！制作不易，烦请一键三连哦~