欢迎来到 Claffic 的博客 💞💞💞
“仅仅活着是不够的，还需要有阳光，自由和花的芬芳。”
前言：
在日常使用的网站和软件中，列表属于最常见的一种东西了，其实现形式有顺序表，链表等，主要功能有增删查改，那么链表具体是什么，如何实现？这篇博客为你解答。
注：
这篇博客属于数据结构内容，建议学习完C语言的小伙伴食用~
目录
🥰Part1: 何为链表
1.链表的概念
2.链表的结构
💗Part2: 链表的实现
1.开工准备
1.1创建项目
1.2建立结点
1.3动态申请结点
2.相关功能实现
2.1打印链表
2.2尾部插入
2.3头部插入
2.4尾部删除
2.5头部删除
2.6查找位置
2.7在pos位置之后插入
2.8删除pos之后的值
2.9pos之前插入
2.10删除pos结点
Part1: 何为链表
1.链表的概念
概念：链表是一种物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的指针链接 次序实现的 。
简单理解下这个概念，就是一个存储单元中有 存储的数据 和 下一个存储单元的地址 ，经过这个存储单元可利用地址找到下一个存储单元。
下面讲到结构就会更加明白：
2.链表的结构
一个简单链表的逻辑图
注意：
• 链式结构在逻辑上连续，在物理上不一定连续（存储的地址不连续）；
• 现实中的结点一般是从堆上申请出来的；
• 从堆上申请的空间，按照一定策略分配，两次申请的空间不一定连续。
Part2: 链表的实现
1.开工准备
1.1创建项目
按照惯例，在 Single linked list 解决方案中创建三个项：
SList.h：头文件，声明所有函数；
SList.c：源文件，实现各函数；
test.c： 源文件，主函数所在项，可调用各函数。
1.2建立结点
这里创建一个结点的结构体，包含要储存的数据和下一个结点的地址：
- typedef int SLTDateType;
- typedef struct SListNode
- {
- SLTDateType data;
- struct SListNode* next;//指向结构体的指针，可通过它找到下一个结构体
- }SLTNode;//将此结点简易命名，方便引用
1.3动态申请结点
关于为什么要动态申请：
动态申请按需分配内存，既不会空间多余，也不会浪费。
- SLTNode* BuySListNode(SLTDateType x)
- {
- //动态申请
- SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
- if (newnode == NULL)
- {
- perror("malloc failed");
- return;
- }
-
- //初始化
- newnode->data = x;
- newnode->next = NULL;
-
- return newnode;
- }
注意动态申请后要进行判断和初始化。
2.相关功能实现
2.1打印链表
我们打印的是一个结点中的数据；
- void SListPrint(SLTNode* phead)
- {
- SLTNode* cur = phead;
- while (cur)
- {
- printf("%d->", cur->data);
- cur = cur->next;//地址不一定连续，不可++；
- }
- printf("NULL\n");
- }
这里值得注意的是 遍历过程中是如何前进的：
因为地址不一定连续，所以要进行赋值，不可直接++，这一点很重要
2.2尾部插入
尾部插入，在申请一个新的结点后，要做的最重要的一点就是 末端节点 中的 结构体指针 要指向 新的结点
尾部插入有两种情况：
• phead 为NULL；
• phead 不为NULL。
我们一个个分析：
第一种情况 比较简单，phead 为空
要让 phead 指向 newnode 指向的结点 ，直接赋值即可
*pphead = newnode;//pphead 是指向 phead 的指针，后面会讲利用二级指针的原因第二种情况 就比较复杂，
因为要实现上下的链接
再寻找一个 tail 用来遍历整个链表，遇到 NULL 时停止。
- void SListPushBack(SLTNode** pphead, SLTDateType x)
- {
- assert(pphead);
- SLTNode* newnode = BuySListNode(x);
-
- if (*pphead == NULL)
- {
- *pphead = newnode;
- }
- else
- {
- //查找尾部
- SLTNode* tail = *pphead;
- while (tail->next != NULL)
- {
- tail = tail->next;
- }
- tail->next = newnode;//改变的是结构体成员，用结构体的指针当然可以
- }
- }
需要注意的是
形参的改变不影响实参，需要通过二级指针来改变 phead.
如要改变 int* ,就需要通过 int** 来改变。
2.3头部插入
头部插入，包括前后两个方向的链接：一是 phead 要指向新的结点 ，二是 新结点中的结构体指针 指向原链表的第一个结点
我是图示
- void SListPushFront(SLTNode** pphead, SLTDateType x)
- {
- assert(pphead);
- SLTNode* newnode = BuySListNode(x);
- newnode->next = *pphead;
- *pphead = newnode;
- }
2.4尾部删除
我的思路是找到倒数第二个结点，但还有只有一个结点的情况。
当只有一个结点时，不用查找，直接释放并置空该节点；
当有多个结点时，先找到倒数第二个结点，将该节点的下一个结点释放并置空即可。
- void SListPopBack(SLTNode** pphead)
- {
- assert(pphead);
- if ((*pphead)->next == NULL)
- {
- free(*pphead);
- *pphead = NULL;
- }
- else
- {
- SLTNode* tail = *pphead;
- while (tail->next->next != NULL)
- {
- tail = tail->next;
- }
- free(tail->next);
- tail->next = NULL;
- }
- }
2.5头部删除
要头部删除，令 phead 指向第二个结点后释放第一个结点即可。
- void SListPopFront(SLTNode** pphead)
- {
- assert(pphead);
- SLTNode* first = *pphead;
- *pphead = first->next;
- free(first);
- first = NULL;
- }
2.6查找位置
查找特定数值所在的位置，思路是通过头指针遍历，最多遍历一遍链表
- SLTNode* SListFind(SLTNode* plist, SLTDataType x)
- {
- SLTNode* cur = plist;
- while (cur)
- {
- if (cur->data == x)
- {
- return cur;
- }
- cur = cur->next;
- }
- return cur;
- }
最后返回的是 结构体指针 ，也就是数值所在结构体的地址。
2.7在pos位置之后插入
在创建 newnode 之后，改变指针指向即可
我是图示
- void SListInsertAfter(SLTNode* pos, SLTDataType x)
- {
- assert(pos);
- SLTNode* newnode = BuySListNode(x);
- newnode->next = pos->next;
- pos->next = newnode;
- }
注意：要先改变 newnode.next 的值，再改变 pos.next 的值，否则会被覆盖。
2.8删除pos之后的值
可以先找到要删除的结点，也就是pos的下一个结点，再将该节点释放置空
我是图示
- void SListEraseAfter(SLTNode* pos)
- {
- assert(pos);
- assert(pos->next);
- SLTNode* del = pos->next;
- pos = del->next;
- free(del);
- del = NULL;
- }
2.9pos之前插入
如果pos指向第一个结点，就相当于前插
其他情况下，需要找到pos的前一个，再进行修改。
我是图示
- void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
- {
- assert(pphead);
- assert(pos);
- if (pos == *pphead)
- {
- SListPushFront(pphead, x);
- }
- else
- {
- //查找pos前一个
- SLTNode* prev = *pphead;
- while (prev->next != pos)
- {
- prev = prev->next;
- }
- SLTNode* newnode = BuySListNode(x);
- prev->next = newnode;
- newnode->next = pos;
- }
- }
2.10删除pos结点
寻找pos的前一个，修改其指向，pos释放置空即可
我是图示
- void SLTErase(SLTNode** pphead, SLTNode* pos)
- {
- assert(pphead);
- assert(*pphead);
- assert(pos);
-
- //查找pos前一个
- SLTNode* prev = *pphead;
- while (prev->next != pos)
- {
- prev = prev->next;
- }
- prev->next = pos->next;
- free(pos);
- pos = NULL;
- }
代码已上传至我的 gitee，
拿走不谢~
总结：
这篇博客介绍了最简单的链表 -- 单链表的概念和结构，并进行了相关功能的实现，第一次接触可能会难很消化，建议充分理解结构后进行实现呐~
码文不易
如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦 💗💗💗