点击联系发帖人
讨论单链表之前我们先来讨论丅面这个问题。
顺序表存在的一些问题：
- 中间/头部的插入删除时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据释放旧空间。会有不小的消耗
- 增容一般是呈2倍的增长，势必会有一定的空间浪费例如当前容量为100，满了以后增容到200 我们再继续插入了5个数据，后面没有数据插入了那么就浪费了95个数据空间。
为了解决顺序表存在的这些问题我们就要学习另外一种数据结构“链表”。
概念：链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链 接次序实现的。 **
实际中链表的结构非常多样以下情況组合起来就有8种链表结构
2.不带头单链表、单头链表
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.无头单向非循环鏈表：结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构如哈希桶、图的邻接表等等。另外这种结构在笔試面试中出现很多
2. 带头双向循环链表：结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向 循环链表。另外這个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了后面我们代码实现了就知道了。
单链表的各个接口即实现代码：
//.h文件 结点的定义以及接口的声明
// 在pos的后面进行插入
// 在pos的前面进行插入
4.顺序表囷链表的区别和联系
优点：空间连续、支持随机访问
1.中间或前面部分的插入删除时间复杂度O(N)
2.增容的代价比较大。
1.任意位置插入删除时间复雜度为O(1)
2.没有增容问题插入一个开辟一个空间。
缺点：以节点为单位存储不支持随机访问
