目录
1.链表的概念及结构
2.链表的分类
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
3.链表的实现
1.无头单向非循环链表
2.双向带头循环链表
4.顺序表和链表的区别
1.链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
现实中 数据结构中
注意：
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：
2.链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.单向或者双向
2.带头或者不带头
哨兵位：不存储有效数据。
优势：不用探空（空就是空指针的意思）
3.循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.无头单向循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据，实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3.链表的实现
1.无头单向非循环链表
SList.h
SList.c
2.双向带头循环链表
List.h
List.c
4.顺序表和链表的区别
1.存储空间：顺序表物理上一定连续；链表逻辑上连续，但物理上不一定连续。
2.随机访问：顺序表支持O（1）；链表不支持：O（N）
3.任意位置插入或者删除元素：顺序表可能需要搬移元素，效率低；链表只需要修改指针指向。
4.插入：顺序表动态顺序表，空间不够时需要扩容；链表没有容量的概念。
5.应用场景：顺序表元素高效存储+频繁访问；链表任意位置插入或删除频繁。
6.缓存利用率：顺序表高；链表低
备注：缓存利用率参考存储体系结构以及局部原理性。
如图：转载@亚撒西带师
