当前课程知识点：数据结构 > 第2章 线性表 > 2.3 线性表的链式实现——链表 > 讲解（上）
现在，我们来学习线性表的第二种存储方式
链式实现，也称为链表
从图上，我们可以看出，4个元素
它们占据的内存并不连续
而且，相对位置也没有什么规律
我们之前曾经讲到过，在链式存储当中
元素所占的内存是任意
为了还原出元素
它们在真实世界当中的前驱、后继关系，除了元素自身信息之外
每个元素还需要附带一个指向
其后继元素的指针，也就是链，链表的名字也由此得来
需要注意的是
在纸上画指针的时候
跟我们前面
画的链式存储方式下的内存不太一样
比如
a1这个元素
它的后面应该是一个地址
是什么地址呢
应该是它的后继元素
a2
所在的存储单元的地址
假设，a2占据了若干个存储单元
因为，我们这里没有画出每个元素
具体占几个字节
我们也没必要画出
因为，对于
数据结构将来编程所使用的高级语言说呢
高级语言通常都不关心
除了首地址之外的其他字节的地址
所以，假设a2所占的若干个字节
它的第一个字节的地址，假设是1000H
那么，a1后面存的地址就是1000H
现在，为了方便，我们并不关心a1后面的这个地址到底是多少
我们也不关心
a2
到底存储在编号为多少的字节里面
总之
我们就用一个箭头
在a1后面
指向a2
箭尾端永远是画在格子里面的，表示
格子里面存放的是一个内存地址
比如，1000H；箭头端永远是指到格子的外面
表示箭尾端的这个地址对应着的存储单元
所以，在纸上画指针的时候
我们不关心指针
具体的值是多少
只需要用箭头，指向相应的内存就可以了
通过左边的这个图
如果用一个指针指向a1
也就是整个线性表的表头元素
这时候通过L
实际上就可以找到线性表当中所有的元素了
我们通过L，可以找到a1
然后通过a1后面的指针，又可以找到a2
一直往后，最后一直找到a4
表尾元素
它是没有后继的
所以，它后面的指针，我们用一个特殊的标记^，表示它是表的最后一个元素
它是没有后继的
当然
如果用编程语言
比如C语言
它就是
NULL
这样一个宏，它的值
我们前面讲过，就是0，C语言
把0这个值当作指针
那就表示空指针
如果是用Java
那么就是小写的
null
表示空对象
把它赋给a4
后面的指针
或引用，就可以了
知道了L，便能依次确定链表中的每一个元素
元素自身信息及其附带的指针合称为链表的结点
将来，我们在定义
每一个元素的时候
实际上包含两部分信息
一部分是元素自身的信息，也就是元素的值
紧接着的，是这个元素
它后继的指针，后继的存储地址
我们把这两部分信息合在一起
称为链表的结点
注意，链表L的称法并不真正代表整个链表
我们经常称链表L
这个L
实际上不能代表链表整体
也没有任何一个
语法结构能够代表链表整体
这个L只是说能找到链表的第一个元素
而知道了第一个元素，又能找到第二个，一直找到链表的所有的结点
所以，我们习惯上就称链表L
但你要知道，L的本质只是指向一个结点的指针
它并不真正地代表链表在内存当中的整体结构
接下来，我们来看单链表
所谓单链表
就是：每一个结点
只附带了其后继的指针
也就是说
我们只能从当前结点找到当前结点的后继
只能沿着一个方向找
只能向后找
所以，称为单向链表
简称为单链表
实际上，前面那个图
它就是一个单链表
因为，每个元素只存放了后继指针
将来，我们还会看到双向链表
这时候
每个结点包含两部分信息
一个是数据域
一个是后继指针域，名字分别叫data和next
将来，我们在定义结构体的时候
结构体也包含两个域
两个成员
我们来看一个非空链表
现在，我们
把那些没有用到的内存，都不画出来
同时
把内存结点横向地画，就变成了这样。L指向第1个元素
a1的后继指针指向a2
一直往后，最后一个结点a4
它的后继为空
如果链表为空
L这个指针也为空
会为我们编程带来一定的麻烦
所以
我们再介绍一种带头结点的单链表
为了编程方便
通常，在表头元素前人为地附设一个结点
这个结点的就叫头结点
指向头结点的指针，称为头指针
现在，L不再指向表头元素a1了
而是在a1前面，加一个结构与元素结点一致的结点
这个结点叫头结点
然后，拿一个指针指向头结点
那么，这个指针就是头指针
头结点的结构跟元素结点一致
也有两个成员
第一个成员是
元素自身的信息
也就是数据域
因为，它是我们人为附设的一个结点
它并不属于线性表的元素
所以它的数据域
我们不关心
我们也不去管它
也不会去初始化它
因为，根本就不会去访问它，不会用到
再来看第二个，指针域，头结点的指针域
毫无疑问是应该指向第1个元素
它应该指向a1这个表头元素
现在，非空链表就跟刚才不一样了
多出来了一个头结点
这个结点是我们人为附加的
原来指向a1的L
现在指向了头结点
头结点的后继指针指向了表头元素
它的数据域
这里用阴影表示
表示我们不初始化它
不关心它
再来看一下空链表，空链表跟刚才也很不一样
即使一个链表不包含任何的元素
但是这个指针L并不为空
除此之外
它还有什么好处呢
我们看这个非空链表
现在可以说
线性表L当中每一个元素都有一个前驱
我们之前讲线性表的逻辑特性的时候
曾经讲过，除了第一个元素结点没有前驱之外
其他结点有且仅有一个前驱
现在，我们加了头结点，每一个元素结点都有前驱
a1的前驱就是头结点
这样会我们编程带来一定的方便
特别是在做循环的时候
既然每一个元素结点都有前驱
那我们就可以一视同仁地
统一地处理
而不需要把表头元素或者表尾元素单独地拿出来处理
现在来看单链表的定义
同样，我们给已存在的类型
int，起一个别名，叫ElemType，以作为链表当中所有元素的类型
接着，我们定义了一个结构体
大家注意到，这个结构体跟我们之前定义的结构体不太一样
我们之前定义的结构体是没有类型名的
现在，在struct关键字后面，是有一个类型名的
而且，我故意把这个类型名起成_Node
是为了防止它跟
typedef定义的别名Node相冲突
刚才，我们介绍过，链表当中的结点
我们以a2
这个结点为例
第一个成员，是结点自身的信息
名字叫data
它的类型就是我们刚才定义的别名ElemType
第二个成员，是一个指针
大家注意到，这个指针指向的数据类型，是我们正在定义的这个结点
所以大家看到，为了能够描述指针next指向的数据类型
这地方必须要带名字
否则，第二个成员，struct就没法去引用
这个结构体
所以
这地方定义的结构体类型名_Node，它的作用完全是给第二个成员用的
然后，我们给这样一个结构体
用typedef起了两个别名
分别叫Node和LinkList
第一个别名很好理解
因为，现在定义的这个结构体
就是包含两个成员
包含两个成员的结构
我们刚才已经说过，叫结点
这是第一个别名Node
第二个别名
它实际上是一个指针型的别名
大家看到，在别名前面，带了一个*
为什么我们把这个别名起成链表呢
前面我们讲过
如果一个指针指向链表的头结点
根据这个指针，就能唯一确定链表当中所有的元素
既然这样
我们就把指向这个结构体的指针的别名，定义成链表
LinkList
我们来看几个表达式
第一个表达式，声明了
一个LinkList类型的变量L
注意，这时候，L已经是一个指针类型了
千万不要在L前面，再加一个*
如果加了，L会变成一个双指针
因为，LinkList就是指针型的别名
用它声明的变量L
即使不加星号
也是一个指针
当然，这种写法
与我们采用第一种别名的写法是等价的
这时候
L就要加*了
因为，Node这个别名就是一个普通的别名
声明的变量，如果是要指向结构体的指针
那么，必须加*
学习C语言的时候
我们知道
如果
通过指针去访问一个结构体的成员
这时候是不能用.的
必须用->
也就是所谓的箭头
这里不能用.
因为，L是指向一个结构体的指针
而不是一个结构体
我们去访问它的next成员
因为，L指向是头结点，头结点的next
指向的是表头元素
是a1
所以
这个表达式指向a1结点
注意，它是一个指针，指向了a1结点
我们再去通过箭头，访问L的next的data
这时候，访问到的，才是a1
这个值
如果我们访问L的next
的next，L的next是a1
a1的next实际上指向a2
第二个元素
如果我们不是以C语言
而是以现在一些热门的面向对象编程语言
比如Java，来定义单链表，又如何定义呢
毕竟，Java是不支持指针的
尽管Java不支持指针
但是Java的引用，它的本质
就是指针
所以，我们首先要定义一个类
这个类名
我起成LinkListNode，代表链表的结点
它包含两个字段
第一个字段，整型的data；第二个字段
大家看到
虽然Java不支持指针
但是这里第二个成员next，它的类型
next这个引用，它的类型就是LinkListNode，就是我们当前定义的这个类
所以，Java的引用，在内存上来说，本质也是指针
出于安全考虑
我们通常把字段设成私有的
然后通过字段的get、set方法，来控制字段的可见性
当然，get、set方法
直接可以拿IDE的辅助工具去生成
不需要你自己手写
现在，我们来看相关的几个表达式
在这里
我们声明了一个LinkListNode类型的变量L
将来，在后面
你可能是通过new
构造方法
LinkListNode()
来初始化一个结点
后面的代码，我们就不写了
L.getNext()访问的是
L的next字段，就等价于刚才C语言当中的L->next
这没什么好说的
它指向的是a1
L.getNext().setData(6)
是修改a1的数据域
把它修改成6
L.getNext().getNext()
就等价于刚才的L->next->next
上面这一行，就等价于L->next->data
修改成6
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
