数据结构之【链表简介】
1.引入
上一期我们了解到，在顺序表中，
(1)单个数据的头部或者中间插入，时间复杂度为O(N)
(2)realloc申请空间时，如果原数据量较大，异地扩容的成本较高
(拷贝数据，释放空间……）
(3)扩容一般是呈2倍的增长，难免造成空间浪费
原来200个存储单元，扩容至400个
如果只用205个，那浪费就很大了
链表就可以很好的解决上述问题
2.概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
物理存储结构 是指 现实情况中，数据存储的真实结构
逻辑顺序 则是 为了方便理解，想象出来的
(1)链表由一系列节点(Node)组成，
每个节点包含数据部分(data)和指向下一个节点的指针(next)等.
(2)节点就是一个结构体
(3)节点一般是从堆上申请出来的
两次申请的空间可能连续，也可能不连续
如上图，
(1)上图链表一共由4个节点组成
(2)指针 plist 存储着头节点的地址
即， plist 指向链表的头节点
(3)头节点存储着第二个节点的地址
头节点就可以找到第二个节点
以此类推，找到节点，就可以找到它所存储的数据
(4)尾节点的标志就是
该节点不会存储下一个节点的地址
next = NULL
3.链表的分类
链表的分类如上图，这可以有很多组合，但最常用的是下面两种：
1.无头单向非循环链表 ：
(1)结构简单，一般不会单独存储数据
(2)多作为其他数据结构的子结构，如哈希桶、图的邻接表等
(3)在笔试面试中出现很多
2.带头双向循环链表：
(1)结构最复杂，一般用在单独存储数据
(2)结构虽然复杂，实现却很简单