前言
数据结构入门 — 单链表详解*
关注博主，后期持续更新系列文章
*****感谢观看，希望对你有所帮助*****
系列文章
第一篇：数据结构入门 — 链表详解_单链表
第二篇：数据结构入门 — 链表详解_双向链表
第三篇：数据结构入门 — 链表详解_循环链表
文章目录
前言
系列文章
一、链表
1. 链表是什么
2. 优缺点
二、概念及结构
1. 概念
2. 结构
三、 链表的分类
1. 链表结构类型
2. 常用的两种链表结构
四、单链表接口实现（代码演示）
1. 动态申请一个结点
2. 单链表打印
3. 单链表增删查改
4. 单链表销毁
五、所有文件代码
1. Gitee链接
总结
一、链表
1. 链表是什么
链表是一种数据结构，由一系列节点组成，在每个节点中存储数据和指向下一个节点的指针。每个节点只包含指向下一个节点的指针，不像数组那样有预定义的大小。链表可以动态地增长和缩小，并且非常灵活，可以在任何位置插入或删除节点。链表主要分为单向链表、双向链表和循环链表等不同类型。
2. 优缺点
链表的优点：
- 灵活性：由于链表中每个节点都有指向下一个节点的指针，因此链表可以在任何位置添加或移除元素，使得链表非常灵活。
- 动态性：由于链表的大小不是固定的，当需要增加或删除元素时，内存中不需要重新分配空间，而是在链表中增加或删除一个结点。
- 无需占用连续的内存空间：相较于数组等数据结构，链表的每个元素之间并没有关联性，每个节点可以在内存中的任意位置，不需要占用连续的内存空间。
链表的缺点：
- 没有随机访问的能力：链表中的元素之间没有关联性，无法像数组那样通过下标直接访问某个元素，需要从头开始遍历整个链表才能找到需要的元素，这会导致链表的查找效率比数组低。
- 内存空间的额外开销：由于需要在每个节点中存储指向下一个节点的指针，链表内每个元素需要占用比其存储内容更多的内存空间，这会导致链表没有数组那么节省内存。
- 不支持常量时间内的随机访问：链表只能在头尾节点进行快速的插入和删除操作，但在其他位置插入和删除节点较为困难，需要先遍历找到要操作的位置，这会导致链表操作的时间复杂度较高。
二、概念及结构
1. 概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。
2. 结构
在现实的数据结构中，链表的结构
注意:
- 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
- 现实中的结点一般都是从堆上申请出来的
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
三、 链表的分类
1. 链表结构类型
链表可以分为单链表、双向链表和循环链表三种类型。
除了这三种基本类型，还有一些派生的链表结构，如带有头节点的链表、带有尾指针的链表、带有哨兵节点的链表等。如下图有8种链表结构
1. 单向或者双向
2. 带头或者不带头（哨兵位）
3. 循环或者不循环
2. 常用的两种链表结构
无头单向非循环链表：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。
四、单链表接口实现（代码演示）
无头+单向+非循环链表增删查改实现
1. 动态申请一个结点
SLTNode*BuySListNode(SLTDataTypex) { SLTNode*newnode= (SLTNode*)malloc(sizeof(SLTNode)); if (newnode==NULL) { perror("BuySListNode"); exit(-1); } newnode->data=x; newnode->next=NULL; returnnewnode; }
2. 单链表打印
voidSLTPrint(SLTNode*phead) { SLTNode*cur=phead; while(cur) { printf("%d->", cur->data); cur=cur->next; } printf("NULL\n"); }
3. 单链表增删查改
头插：
//头插voidSLTPushFront(SLTNode**pphead, SLTDataTypex) { assert(pphead); SLTNode*newnode=BuySListNode(x); newnode->next=*pphead; *pphead=newnode; }
尾插：
//尾插voidSLTPushBack(SLTNode**pphead, SLTDataTypex) { 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; } }
头删：
//头删voidSLTPopFront(SLTNode**pphead) { //空assert(pphead); assert(*pphead); //非空SLTNode*newnode= (*pphead)->next; free(*pphead); *pphead=newnode; }
尾删：
//尾删voidSLTPopBack(SLTNode**pphead) { assert(*pphead); assert(pphead); //一个节点if((*pphead)->next==NULL) { free(*pphead); *pphead=NULL; } else { SLTNode*tail=*pphead; SLTNode*tailPrev=NULL; while(tail->next!=NULL) { tailPrev=tail; tail=tail->next; } free(tail); tail=NULL; tailPrev->next=NULL; } }
查找：
//查找SLTNode*SLTFind(SLTNode*phead, SLTDataTypex) { SLTNode*cur=phead; while (cur) { if (cur->data==x) { returncur; } cur=cur->next; } returnNULL; }
在pos之前插入x：
// 在pos之前插入xvoidSLTInsert(SLTNode**pphead, SLTNode*pos, SLTDataTypex) { assert(pos); assert(pphead); if (pos==*pphead) { SLTPushFront(pphead,x); } else { SLTNode*prev=*pphead; while (prev->next!=pos) { prev=prev->next; } SLTNode*newnode=BuySListNode(x); prev->next=newnode; newnode->next=pos; } }
在pos以后插入x：
// 在pos以后插入xvoidSLTInsertAfter(SLTNode*pos, SLTDataTypex) { assert(pos); SLTNode*newnode=BuySListNode(x); newnode->next=pos->next; pos->next=newnode; }
删除pos位置：
// 删除pos位置voidSLTErase(SLTNode**pphead, SLTNode*pos) { assert(pos); assert(pphead); if (pos==*pphead) { SLTPopFront(pphead); } else { SLTNode*tail=*pphead; while (tail->next!=pos) { tail=tail->next; } tail->next=pos->next; free(pos); pos=NULL; } }
删除pos的后一个位置：
// 删除pos的后一个位置voidSLTEraseAfter(SLTNode*pos) { assert(pos); assert(pos->next); SLTNode*posNext=pos->next; pos->next=posNext->next; pos->next=posNext->next; free(posNext); posNext=NULL; }
4. 单链表销毁
voidDestory(SLTNode**pphead) { assert(pphead); SLTNode*cur=*pphead; while (cur) { SLTNode*del=cur->next; free(cur); cur=del; } *pphead==NULL; }
五、所有文件代码
1. Gitee链接
***查看所有代码***
点击右边蓝色文字 DuckBro Gitee 代码仓库
总结
单链表的重点包括：
- 定义：单链表是一种数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
- 插入操作：单链表的插入操作需要先找到要插入位置的前一个节点，然后将新节点插入到其后。
- 删除操作：单链表的删除操作需要先找到要删除的节点的前一个节点，然后将其指针指向下一个节点即可。
- 遍历操作：单链表需要从头节点开始依次遍历各个节点，获取其中存储的数据。
- 链表反转：单链表的反转操作是将链表中的节点从后往前连接，最后将原来的头节点变为尾节点。
- 快慢指针：快慢指针是单链表中常用的技巧，可以用于查找链表中的中间节点、判断是否有环等操作。
- 环形链表：有些单链表可能存在环形结构，即某个节点的指针指向之前的某个节点，使用快慢指针可以判断链表是否为环形。
- 链表排序：单链表可以使用排序算法进行排序，如冒泡排序、快速排序等。
- 链表的应用：单链表广泛应用于各种数据结构和算法中，如哈希表、图等。
如这篇博客对大家有帮助的话，希望 三连 支持一下 ！！！ 如果有错误感谢大佬的斧正 如有 其他见解发到评论区，一起学习 一起进步。
