【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
🔥引言
本篇将深入解析单链表:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。
🌈个人主页：是店小二呀 🌈C语言笔记专栏：C语言笔记 🌈C++笔记专栏： C++笔记 🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
一、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
二、链表的分类
我们重点需要关注以下两个链表:
1.无头单向非循环链表
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。虽然结构复杂，但是使用代码实现，以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
链表是通过一个个结点链接起来的数据结构，多个结点链接形成下列结构(箭头是不存在，是为了方便理解)
下列图片会简化结点间的链接过程：
【注意】:
从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间。是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
四、实现无头单向非循环链表的相关接口(SLTlist.h)
五、知识铺垫
1.实现部分接口需要通过二级指针接受实参
原因在于我们需要可以修改实参，而是实参为一级指针时(同样是传递地址)，需要使用二级指针进行接受，否则获得临时拷贝，不会影响到实参。修改实参的情况，比如一开始为空，在插入时需将头指针存储在有效结点的的地址上，需要改变实参的值
2.单链表的初始化
这里实现链表，没有必要进行初始化，初始化对于一开始就要开辟的空间有初始化的需求，表是多个节点通过地址链接在一起，那么只需要开辟新节点的时候，初始化下就行了(有哨兵位需要初始化)
3.二级指针断言
二级指针存放的是头节点的地址，头节点的地址为空，那么还有什么意义呢?
当我们有所了解链表的结构，接下来是实现链表的相关接口，比如增删查改
六、正式开始模拟实现单链表
6.1 创建链表中的节点
在插入中需要先创建一块结点空间，再通过上一个结点通过当前结点的地址指向当前结点的位置。这是因为结点是通过地址访问的，结点里面存储着下一个节点的地址，理解为当前结点(通过下一个结点地址)指向下一个结点
SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode==NULL) { perror("malloc fail!!!"); return (-1); } newnode->next = NULL; newnode->val = x; return newnode; } 123456789101112这里需要注意的是:申请到的空间交给什么类型去维护，为结点(结构体)申请空间，就需要交给结构体指针维护，同时需要注意开辟空间可能会失败，比如开辟空间多大，无法提供空间。对新结点设置了指向下一个结点为空
6.2 单链表的插入节点
插入分为三类:头插\尾插\任意位置插入(其中任意位置插入，在实现查找功能先放着)
6.2.1 单链表的尾插 void SLTPushBack(SLNode** phead,SLNDataType x) { assert(phead); SLNode* newnode = CreateNode(x);//值已经有了,创建一个新节点 if (*phead == NULL)//这里需要二级指针去改变了，外的头了 { *phead = newnode; } else { //找尾 SLNode* cur =*phead;//拷贝一份 while (cur->next != NULL) { cur = cur->next; } cur->next = newnode;//newnode已经搞下一次是空了 } }
这里需要注意的是:while语句cur需要到达尾，再进行尾插的操作
。同时需要考虑到特殊情况，这里我们通过if判断语句对于* pphead为空的情况，将*pphead存储在第一个结点地址。
这里需要注意的是:将*pphead移动到新节点的位置，再 * pphead指向cur(在原来的头节点位置)。同样的需要考虑到特殊情况，这里使用if判断语句对于* pphead为空的情况，将*pphead设为存储第一个结点地址。 
6.3 单链表的删除
删除分为三类：头删\尾删\任意位置删除(其中任意位置删除，在实现查找功能先放着)
提前说明:空链表无法进行删除数据，需要在删除操作之前进行断言检查assert(*pphead)
6.3.1 单链表的尾删 void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead);//空的时候 //一个节点和多个节点 //这里不创建一个cur变量，当只有一个节点的时候，直接pphead SLNode* cur = *pphead; if (cur->next == NULL) { *pphead = NULL; free(cur); cur = NULL; } else { while (cur->next->next!= NULL) { cur = cur->next;//上一个节点 } free(cur->next); cur->next = NULL; } }这里需要注意的是
:删除需要分为两种情况存在一个节点和多个节点的处理。需要利用while循环找到删除节点的上一个节点，将上一个节点指向空，最后不要忘记free(cur->next)，释放当前节点空间。
6.3.2 单链表的头删
void SLTPopFront(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
SLNode* cur = *pphead;
if (cur->next == NULL)
{
*pphead = NULL;
free(cur);
cur = NULL;
}
else
{
*pphead = cur->next;
free(cur);
cur = NULL;
}
}
这里需要注意的是:删除需要分为两种情况存在一个节点和多个节点的处理。cur保存当头节点位置，*pphead移动到下一个节点的位置，再free(cur)
6.4 查找单链表中数据
SLNode* SLTFind(SLNode* pphead, SLNDataType x) { SLNode* cur = pphead; while (cur!=NULL) { if (cur->val == x) return cur; else cur = cur->next; } return NULL; } 123456789101112这里需要注意的是:遍历链表，找到返回当前节点，没有找到继续向下遍历
6.5 关于单链表的任意位置插入和删除
6.5.1 单链表的pos指定前插入 void SLTInsert(SLNode** pphead,SLNode *pos,SLNDataType x)//pos指定之前插入 { assert(pphead); assert(*pphead); if (pos == NULL)//没有节点 { SLTPushFront(pphead, x); } if (*pphead == pos)//一个节点 { SLTPushFront(pphead, x); } else//多个节点 { SLNode* newnode = CreateNode(x); SLNode* cur = *pphead; while (cur->next != pos)//上面避免了pos等于cur { cur = cur->next; } cur->next = newnode; newnode->next = pos; } }这里需要注意的是
:需要分为三种情况，空节点，一个节点，多个节点就行处理。空节点调用尾插或者头插都可以，一个节点(在pos前插入)那么可以调用头插
6.5.2 单链表的删除pos当前结点
void SLTEeara(SLNode** pphead, SLNode* pos)
{
assert(pphead);//防止用户传个空指针
assert(*pphead);
assert(pos);
SLNode* next = pos->next;
SLNode* cur = *pphead;
if (cur==pos)
*pphead = NULL;
free(cur);
cur = NULL;
else
{
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = next;
free(pos);
pos = NULL;
}
}
这里需要注意的是：分为两种情况，存在一个节点和多个节点的处理。如果使用三个变量，需要使用到的地址不会丢失，就不需要担心先后顺序问题
。结点是一块块的独立空间，其链接方式也是较灵活的，这里跟上面方法是类似的。
如果不想在pos之前插入\删除，可以改动逻辑在pos之后进行插入、删除。
6.5.3 单链表的pos之后插入 void SLTInsertAfter(SLNode **pphead,SLNode* pos, SLNDataType x) { assert(pphead); assert(*pphead); if (pos == NULL)//没有节点 { SLTPushFront(pphead, x); } if (*pphead == pos)//一个节点 { SLTPushBack(pphead, x); } else//多个节点 { SLNode* newnode = CreateNode(x); SLNode* back = pos->next; newnode->next = back; pos->next = newnode; } }上面的两个接口实现过程跟SLTInsert、SLTEeara实现类似的，看看代码就能理解
在完成了单链表的核心接口，我们需要继续完善剩下的接口，使实现的单链表功能更加丰富起来。
6.6 单链表的打印
void SLTPrint(SLNode** pphead)//二级指针改变外的结构体指针类型 { assert(pphead); SLNode* cur = *pphead; while (cur!= NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); } 1234567891011这里需要注意的是：当cur==NULL时，没有进去循环，需要额外打印NULL，最后不要忘记单链表的销毁
void SLTDestroy(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); //这里cur不要赋空，还需要使用的 cur = next; } *pphead = NULL; } 12345678910111213这里需要注意的是：链表是通过多个节点链接而成的，同时也是一块块独立空间，通过cur去访问每一个空间和释放每一块空间。其中free指针跟指针变身是没有关系的，释放的是指针所指向的那一块动态空间
七、顺序表和链表的区别
不管是哪一种数据结构都有他的优点和缺点，对此在使用数据结构中应该知道它的优缺点是什么，加以合理地利用解决实际中的问题。
Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！