当前课程知识点：数据结构 > 第2章 线性表 > 2.3 线性表的链式实现——链表 > 讲解（下）
现在，我们来看链表的创建算法
创建链表L
创建的时候，需要一些已知数据
我们用第2个参数e，这个数组来存放已知的数据
同时，用第3个参数来标识这个数组的长度
我们要做的是
首先，初始化一个头结点
因为，无论创建什么样的链表
这个头结点总有一个
接着
开始读取e当中的每一个元素
每读取一个元素
就创建一个相应的结点
并且，把这个结点插到L的表头或者表尾的位置
实际上
创建算法有两种
一种是头插法
也就是，每次将新申请的结点，插入到头结点的后面
或者说
作为链表的第一个元素
这叫头插法；与之相对应的，还有尾插法
每次创建的结点，都插入到链表的最后
作为链表的最后一个元素
重复上面的步骤n次
最终，就会创建一个长度为n的链表
现在，我们来看算法的实现
在循环之前，申请一个新的结点L
L毫无疑问是头结点
将它的next置为空
紧接着，进入循环，循环n次
每次，先申请一个结点p
p是指向新申请的结点
然后，将它的数据域修改成e中
下标为i的元素
然后，将L->next赋值给p->next
L->next当前指向的是链表的表头元素
将表头元素赋值给新申请的结点的后继，意味着，将表头元素放到了新申请结点的后面
然后，将p赋值给L->next
从这行语句
我们更加能确认，L->next
修改成p，p是新申请的结点
L->next要指向表头元素
那说明，每次新申请的结点是作为表头元素的
所以，它确实是头插法
我们可以举几个具体的示例
比如，数组里面的元素是1、2、3、4
我们先执行这一行，申请了一个新的结点L
它指向新申请的这个结点——头结点
然后将它的next置为空
进入for循环，先读取第1个元素
申请一个新的结点p
将数组的第1个元素赋值给p的data，注意
这是新申请的结点
将L->next(为空)
赋值给p->next
那p->next为空
然后，将p赋值给L->next，那么，L->next指向它
再进入循环，再申请新的结点
p指向这个结点，将第2个值赋值给p->data
然后，将L->next赋值给p->next，L->next
是指向表头元素
将它赋值给p->next
那么，p->next指向它
然后，将p
赋值给L->next，原来L->next
的指向关系就不存在了
现在头指针L
指向了
数值为2的结点
然后，再指向数值为1的结点
所以，通过前面两个结点
我们就能发现
靠前的这些值
实际上是作为表尾元素的
而后面的值，是作为表头元素的
所以叫做头插法，头插法
会导致
输入数据的顺序，跟最终创建出来的链表的顺序是相反的
这个需要注意
我们再来看尾插法
前面都是类似的
不同之处在于，我们设了一个临时的变量tail，来指向最后一个结点
以方便将当前新申请的结点作为表尾元素来插入
for循环，新申请结点、赋值
然后，将p->next置为空
这一行，实际上就已经说明了问题
每次新申请的结点
它的next置为空
说明，我们是将这个结点作为表尾元素的
然后，将当前表尾元素
它的next，修改成p，原来的表尾不再是表尾了
因为，我们将它的next修改成了p——新申请的结点
然后，再将p赋值给tail
现在，tail指向新的表尾元素
同样，我们用1、2、3、4
先申请一个结点，作为头结点
然后
进入循环，第1个值赋值给它(新申请的结点p)，注意
在循环之前
tail指针指向的也是L
然后
将p->next置为空
然后，再将p赋值给tail->next，tail->next
原来是它，我们将原来为空的这个指针修改成p，再将p赋值给tail
现在，tail就指向它了
第2次进入循环，将2赋值给p指向的结点
然后，将p->next修改为空
再将p赋值给tail->next
tail->next原来是空，修改成p
再将p赋值给tail
tail指向新的表尾元素
通过前面两个结点
我们就能发现，尾插法
创建出来的链表的元素顺序，跟输入的顺序是一致的
这两个算法
它们的时间复杂度，毫无疑问都是O(n)，因为循环了n次
我们来总结一下单链表的优缺点
优点
无需占用连续的内存
按需申请内存
需要一个结点
就马上malloc
不会预分配若干元素
占的
存储空间——像顺序表那样
所以，链表
不会造成存储空间浪费
插入、删除的时候，是不需要移动元素的
看起来，时间复杂度是O(1)
因为，只需要修改1个或者2个指针
但是
由于在修改指针之前，需要找到
第i-1个结点，找第i-1个结点依然是要做循环的
因为，需要遍历整个链表
所以，尽管不需要移动元素
但链表的插入、删除的时间复杂度仍然是O(n)
缺点在于不支持随机存取
因为随机存取是顺序存储的特点
在链表当中
按位置来找链表当中的元素，需要遍历整个链表
它的时间复杂度是O(n)
仅支持单向的遍历
因为，每个结点只存放了当前结点的后继指针
所以
只能从表头到表尾的方向去找
不能反过来找，也就是说
无法找到当前结点的前驱
那可以改进一下前面的单链表
比如，我们现在介绍的单循环链表
很简单
它的结构
与单链表一致
但是，最后一个结点的后继不再是空了
而是指回到头结点，形成了一个封闭的环
它与单链表的
区别就在于
单链表为空的这个指针
最后一个结点为空的后继，指回到头结点
这是为空的单循环链表
那么
从任意结点出发
能够访问到其他的结点
不像单链表
从头向后找，是回不去的
现在，单循环链表
从任意一个结点出发
都能遍历到其他的结点
因为，整个链表形成了一个封闭的环
另外
在写相关算法的时候，需要注意，判断是否达到最后一个元素时
应该与头结点，而非NULL，进行比较
我们之前，都是判断p为NULL，或者p->next为NULL
现在，我们应该跟头结点的指针进行比较
而不是NULL
比如，我们要得到单循环
链表的长度
因为，在单循环链表当中
所有的后继指针都不是空
那么，我们必须判断它的next是否等于L
也就是说，是否回到了头结点，而不再是NULL，这个需要注意
再来看
第二种改进：双向链表。双向链表，顾名思义
每一个结点
除了存放后继指针
还有前驱指针，多了一个成员
每个结点包含两个指针
分别指向当前结点的前驱和后继
头结点的前驱
和最后一个结点的后继，都为空
因为，头结点没有前驱
最后一个结点没有后继
它支持双向遍历
在定义结构体的时候
多了一个指针
除此之外
它跟单链表是一致的
我们再看几个表达式
L->next->next->prior
L指向头结点
它的next是
这个绿色的指针，指向a1
然后，再next，指向a2
然后，再取前驱
那是这个指针，指回到a1
所以，这个表达式是指向a1结点的
再来看这个表达式
将p->next赋值给p->prior->next
假设，在执行之前，p指向a2
p->next是指向
a3的，这个绿色的指针，指向a3；p->prior是这个红色的指针
它指回到a1
然后，a1的next是这个指针，将这个指针修改成p->next
那实际上，是删除了a2
从a1直接到a3
再看最后一个表达式，p->prior赋值给p->next->prior
同样，假设
p是指向a2的
它的prior是这个红色的指针
它指回到a1，将a1的指针赋值给p->next->prior，p->next指向a3
a3的prior这个指针修改成p->prior
那是修改了这个指针
它跨过了a2
所以
这两个表达式
相当于删除了双向链表当中的a2结点
因为，在双向链表当中做删除
需要修改的指针数量
是对应的单链表
修改的指针数量的两倍，插入也是类似的
最后一种，双向循环链表
它的结构同双向链表
但是，最后一个结点的后继是头结点
头结点的前驱是最后一个结点
形成了两个封闭的环
我们可以把双向循环链表理解成两个单循环链表的叠加
也就是图当中
绿色的指针和红色的指针，分别构成的单循环链表
从头指针能够直接找到第一个元素
也就是L->next，这个指针
它能找到a1，找最后一个元素也很简单
L->prior
直接找到最后一个元素
那么，前面的单链表
以及双向链表
注意，是不带循环的双向链表
它们找最后一个元素，都需要去做循环
时间复杂度是O(n)
现在，双向的循环链表直接从头结点的prior指针，就能找到最后一个结点
所以，时间复杂度变成了O(1)
双向循环链表同时具有单循环链表和双向链表的特点
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
