【数据结构】单链表专题（详细代码及配图）
本文主要介绍了数据结构的单链表，内容全由作者原创（无AI），同时深度解析了单链表增删查改等功能，并带有配图帮助博友们更好的理解，点个关注不迷路，下面进入正文~~
前言：
学习了顺序表之后，我们发现顺序表存在以下问题：
1.中间/头部插入效率低下
2.增容降低运行效率
3.增容造成空间浪费
那么有什么办法可以解决这些问题？下面我们来介绍链表的概念
1.链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的顺序结构是通过链表中的指针链接次序实现的。
链表也是线性表的一种~
物理结构：不是线性的
逻辑结构：一定是线性的
那么链表具体是什么东西呢？
举一个具体的例子：
链表的结构跟火车很类似，如果是旺季，我们可以增加车厢；如果是淡季，我们可以减少车厢，每一节车厢都是独立的，添加或减少车厢不会影响其他车厢。
想象一下，假如每节车厢的车门都是上锁的，并且需要用不同的钥匙打开，每次只能携带一把钥匙的情况下如何从车头走到车尾？
最简单的做法，在每一节车厢都存放下一届节车厢的钥匙。
在链表里，每一节车厢是长什么样的？
每个车厢，我们称之为节点/结点
节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。
图中的指针变量plist保存的是第一个节点的地址，我们称plist此时指向第一个节点。如果我们希望plist指向第二个节点时，只需修改plist保存的内容为0x0012FFA0。
2.单链表的具体功能的实现
2.1单链表需要实现的功能
//打印链表
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);2.2打印链表
通过phead（第一个节点的指针）先访问数据，再移动到head->next（下一个节点的指针），知道phead为空才停止访问，最后打印NULL收尾。
我们习惯用临时变量pcur保存第一个节点的地址，这样做是为了方便我们后续找到第一个节点的地址。
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)//pcur != NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}2.3链表的的尾插
在实现尾插之前，我们先画个图帮助我们理解
思路：
1.创建新节点
为了方便后续创建新节点的使用，我们将创建新节点这一步骤定义为一个函数SLTBuyNode
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}2.创建尾节点的指针
我们要尾插一个节点，因此我们要找到尾节点的指针ptail，然后将ptail->next改为新创建节点的地址，因此找到尾节点是必要的。
我们可以先将ptail指向第一个节点，当ptail->nex不等于NULL时将ptail = ptail->next，直到ptail->next为NULL，此时就说明了我们找到尾节点的指针了。
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}3.将ptail->next指向新节点
ptail->next = newnode那我们不加思考地写出完整的代码
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* ptail = phead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
我们发现程序并没有像我们如期的一样打印1->NULL，这是为什么呢？
我们想想，如果我们的链表一开始为空链表，及plist=phead=ptail=NULL，那我们还能进行ptail->next吗？很显然不行，程序会报错。因此我们需要判断传入的phead是否为NULL，如果是，直接让phead指向新节点；如果不是，再进行后面的操作，新代码如下
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
//assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
if (phead == NULL)
{
phead = newnode;
}
else
{
SLTNode* ptail = phead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}我们再运行一下
我们发现这次程序成功输出了，但却只输出了NULL，并没有输出我们预想的1->NULL，这又是为什么呢？别急，我们调试一下
我们发现plist并没有指向新的节点，而是NULL，说明plist的值并没有发生改变
这是因为我们在函数传参的时候使用的是传值调用，形参的改变要影响实参，必须要传地址
第一个节点 *plist<------>**pphead
指向第一个节点的指针 plist<------->*pphead
指向第一个节点的指针的地址 &plist<------>pphead
那么我们要改变指向第一个节点的指针，就要传入指向第一个节点的指针的地址 &plist
同时不要断言pphead，assert(pphead)，防止传入了一个空指针NULL，下面是修改后正确的代码
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//*pphead 就是指向第一个节点的指针
//空链表和非空链表
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}我们运行一下代码
结果是1->NULL，结果没有任何问题
通过这个头插的代码，给了我们两个启发：
1.写代码的时候，要着重思考头和尾的特殊情况
2.当我们需要改变函数的实参，必须要传入实参的地址
2.4链表的头插
思路：
1.创建新节点
2.newnode->next=*pphead
3.*pphead=newnode
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}我们检查一下，当链表为空链表时，*pphead为NULL，newnode->next为NULL，*pphead被赋值为新创建节点的地址，没有任何问题
2.5链表的尾删
思路：
1.创建ptail找尾节点的地址
2.创建prev找到尾节点前一个节点的地址
3.将ptail指向的节点的空间释放掉，并置为NULL
4.prev->next=NULL;
5.断言*pphead和pphead，如果链表为空那就没有节点可以删除
根据这个思路，我们写出如下代码：
void SLTPopBack(SLTNode** pphead)
{
assert(pphead&&*pphead);
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}同样的，我们来思考一下，如果链表只有一个节点，代码可不可行？
ptail和prev都可以正常创建，ptail->next=NULL，不会进入循环，ptail指向的空间被释放掉，注意，ptail和prev指向的是同一块空间，因此prev此时是野指针，对野指针使用箭头操作符访问成员元素，编译器会直接报错，因此，如果链表只有一个节点，代码不可行
当只有一个节点时，不用创建prev和ptail变量，只需将*pphead指向的空间释放掉并置为NULL即可，更正后的代码如下：
void SLTPopBack(SLTNode** pphead)
{
//链表不能为空
assert(pphead&&*pphead);
//链表只有一个节点
if ((*pphead)->next == NULL)//->优先级高于*
{
free(*pphead);
*pphead = NULL;
}
//链表有多个节点
else
{
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}这里需要注意，->优先级高于*，因此需要用（ ）先对pphead进行解引用操作
2.6链表的头删
思路：
1.链表不能为空
2.创建next变量存储(*pphead)->next
3.free(*pphead)
4.*pphead=next
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;//-> 优先级高于*
free(*pphead);
*pphead = next;
}2.7链表的查找
如果找到了数据为x的节点，返回此节点的地址；如果没找到，返回空指针NULL
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}2.8在指定位置之前插入数据
思路：
1.创建新节点
2.找到pos的前一个节点prev
3.prev->next=newnode
4.newnode->next=pos
根据思路我们写出如下代码：
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}那么，当链表只有一个节点的时候，还能正常头插吗？
当链表只有一个节点的时候，*pphead=pos=prev，prev->next为NULL，prev->next!=pos条件为真，进入循环，prev被赋值为NULL。对为NULL的prev进行箭头访问数据时，编译器会报错，不能正常头插。
因此当*pphead=pos时，直接使用链表头插函数，正确的代码如下
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);
assert(pos);
//若pos == *pphead;说明是头插
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}2.9在指定位置之后插入数据
问一个问题：先红色后绿色可行吗？
答案：不可行！
当pos->next=newnode时，就无法通过pos->nest找到下一个节点了
正确代码如下
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}2.10删除pos节点
思路：
1.创建变量prev指向pos前一个节点
2.prev->next=pos->next
3.释放pos并置NULL
根据这个思路我们写出下面代码
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}如果链表中pos为头节点，还能正常删除吗？我们推测一下
如果pos为头节点，那么刚开始的时候*pphead=pos=prev，prev->next为NULL，prev->next!=pos条件为真，进入循环，prev被赋值为NULL。对为NULL的prev进行箭头访问数据时，编译器会报错，不能正常删除。
因此当*pphead=pos时，直接使用链表头删函数，正确的代码如下
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}2.11删除pos之后的节点
思路：
1.如果先将pos->next指向pos->next->next，那么将无法找到需要删除的数据并无法将其释放
如果先将pos->next释放掉，那么将无法通过pos->next找到pos->next->next
因此我们要先定义一个临时变量del记录pos->next
2.将pos->next指向pos->next->next
3.释放del并置零
需要注意pos不能为最后一个节点，所以需要对pos->next断言，下面为正确的代码
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}2.12销毁链表
思路：通过pcur遍历整个链表，用next记录pcur->nest即pcur的下一个节点的地址，将pcur所指向的空间释放掉后，再将pcur赋值为next。当pcur为NULL时停止循环。正确代码如下：
void SListDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
SLTNode* next = *pphead;
while (pcur)
{
next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}结语：
这篇文章全文由作者手写，图片由画图软件所制，无AI制作，希望各位博友能有所收获
，欢迎各位博友的讨论，觉得不错的小伙伴，别忘了点赞关注哦~
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
26
0- 0
已为社区贡献3条内容
所有评论(0)