🎈今日心语：你所看到的惊艳，都曾被平庸所历练。
前言：
继【数据结构基础】顺序表 ，我们来介绍链表的相关内容。
目录：
1、链表
- 顺序表(数组)的缺陷及思考
缺陷：
- 中间/头部插入删除，需要移动的元素很多，浪费算力，时间复杂度为O(N)，
- 扩容需要申请新空间（尤其是异地扩容）可能会有空间的浪费，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。而多次少量扩容，又会使程序复杂化。
由于数组的这些缺点，自然而然的就产生链表的思想了。
链表通过不连续的储存方式，自适应内存大小，以及指针的灵活使用，巧妙的简化了上述的内容。
1.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
- 数据构成：
数据域：存放数据本身的信息。
指针域：存放指向下个结点的地址（指向直接后继的指针）。
结点：数据元素的存储映像。由数据域和指针域两部分组成。
n个结点通过指针域相互链接，组成一个链表。
如图：
①头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。
②头结点：一个不存任何数据的空结点，通常作为链表的第一个结点，它的数据域一般不存放数据。（头结点不是必须的。）
③首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。
- 逻辑结构：
- 物理结构：
实际中，是没有上面的箭头的
如图，n1,n2,n3,n4是指针变量，接收了开辟的结点，现在要将结点链接起来，就要把n2给了n1的next，依次类推。
注意：
1、链式结构在逻辑上是连续的，但在物理上不一定连续
2、现实中的结点一般都是从堆上申请出来的
3、从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
1.3简单实现链表链接：
- 定义结点 ：
- 测试部分：
- BuySLTNode 开辟空间函数封装：
由于上面创建结点，n1,n2,n3,n4需要一个一个创建，比较复杂，故我们封装一个函数,使得可以创建n个结点：
- CreateSList创建结点函数封装
- 打印链表中的data和next指向的地址：
- 使用函数栈帧整体介绍：
phead和ptail存了第一个结点的地址，
phead为了方便返回，ptail为了方便链接
ptail->next指向下一个结点，存放该结点的地址，
然后ptail指向新的结点
最后，phead指向头结点，ptail指向尾结点
当CreateSList函数调用结束后,该函数的栈帧销毁，局部变量phead，ptail随之销毁
这样就找不到链表了，但是phead在销毁前，返回了，将指向的内容拷贝给了plist，这样plist就指向了链表的首结点，就可以找到链表了。
plist传参给新的phead，为了方便区分定义了一个指针变量cur，同样的SLPrint函数调用结束后，函数栈帧销毁，phead和cur随之一起销毁。
由此我们可以得出结论：
使用链表的时候一直保持一个指针指向头节点，链表的关键使头结点，顺序表的关键是结构。
结语：
这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。
希望以上内容对大家有所帮助👀，如有不足望指出🙏
前路漫漫！努力变强💪💪 吧！！
