当前课程知识点：基于Linux的C++ > 第八讲 链表与程序抽象 > 8.4 链表（一） > LinuxCPP0804
接下来一节就是链表
链表是存取顺序访问的数据对象集
数据对象它所占用的存储空间
按照动态的分配方式来分配
用malloc和free或者是
new和delete来进行管理的
从定义的角度来讲
一个链表它是像这样一个元素序列
它的其中的每一个元素和前后的元素
是相互链接在一起的
也可能一个结点和后一个结点链接在一起
也可能是某一个结点和它的前一个结点
或后一个结点都链接在一起
这个我们就称它为链表
这里面最重要的概念就是我刚才讲的结点
它是指链表中的
某一个特定的元素 这叫结点
一个NODE 它包括两个字段（两个域）
一个叫数据域 一个叫做链接域
我们用data和next来表达
实际上你在设计这个链表的过程中
你的data这个字段是有可能是很多个域
你的数据可能很复杂
在这样的一个链表中
为了维持数据之间的关系
需要一个表头结点和一个表尾结点
我们用head和tail来表示
这样的一个表头或表尾
你当然可以使用链表中的
特定的结点来表达
但实际上没有必要
只需要使用一个指向链表的首结点的
一个指针来表达它就可以了
所以表头结点并没有data字段
表尾结点也一样
按照我们这样的设计
这个head和tail就是这个链表的
表头指针或表尾指针
它们分别指向链表的表头结点
和表尾结点
这样的话我们就可以通过head这个表头指针
来访问这个链表的头结点
然后访问链表的下一个结点
这个是通过表头结点的next域来达到的
然后按照这个链表的顺序依次地向后访问
一直到最后的结点
就完成整个链表的操作
这是链表的最基本的处理方式
而我们的表尾结点呢
将直接指向链表的最后一个元素
也就是链表的表尾结点
这样的话可以直接操纵链表的表尾的元素
头指针和尾指针将指向我们的表头和表尾
这样的两个结点
那么这样的链表数据结构
正常情况下面
如果要想符合数据封装和信息隐藏的
基本要求的话
那么我们就需要通过这样的两个域
data域和next域来分别描述
它的数据字段和链接字段
假设定义的这个链表是用来表达
刚才那个点结构体的
所以在这样的链表中
每一个结点它都会包括两个部分
我们刚才那个链表的那个图例
每一个结点的形状是一样的
每一个结点的存储表示都是一样的
一个data字段 一个next字段
每个next字段将指向它的下一个结点
那么这个结点类型是什么呢
和第一个结点类型是一样的
所以在设计的时候
我们就需要特别注意这一条
next这个字段 它的类型是PNODE
PNODE是什么呢
PNODE就是指向struct NODE的一个指针
你看我们这样一个定义你就明确了
我有一个struct NODE
一个结点的类型的一个声明
然后我们typedef struct NODE * PNODE
PNODE指向这个结构体
然后struct NODE具体的实现里
data 类型就是PPOINT
然后next域为指向NODE的一个指针
就是PNODE
这个就是我们链表结点的数据结构
它包含两个域
一个是结点数据域
还有一个链接指针域
注意在这个结构体类型的定义中
它里面有一个成员为指向结构体的指针
这是允许的
你如果让它的next字段为
struct NODE类型的成员
那么这样的定义就涉及到了
结构体的递归定义 这是不允许的
因为它没有办法决定
这个结构体的存储空间的大小
而如果是指向本结构体的一个指针
这就是合法的
因为每一个指针存储空间的大小
它都是固定的
不管它是指向别人还是指向它自身
尺寸是固定的
32位的体系结构 32位的编译器
那么这个指针就是4个字节 就是32位
如果是64位指针 它的尺寸就是64位
不管它是指向哪一个类型
尺寸都是固定的
所以它不影响struct NODE结构体的
内存的分配和管理
所以就可以用指向本结构体的指针
作为结构体的某一个特定成员类型
这个就是链表的结点的数据结构
要维持整个这个链表
仅有这个链表结点数据结构是不够的
所以我们还要为它定义整个链表的结构
来管理所有的结点
那么我们会定义一个struct LIST
然后typedef struct LIST * PLIST
一个指向我们的链表的一个指针PLIST
然后我们定义struct LIST
这个链表结构体 它包括三个字段
一个是count字段
然后有两个字段head和tail
分别指向链表的表头和表尾
它们的类型当然都是PNODE
有了前面这个定义
现在就能够看到链表的
一个完整的存储布局
首先这个链表的结构体
它包括三个字段count、head、tail
count表示这个链表结点的元素个数
head将会指向这个表头结点
表尾指针tail将会指向表尾结点
这个就是完整的链表的数据结构
当然在这个链表数据结构之外
我们仍然有一个指针指向LIST
这个就是标准的链表结构
那么在整个链表里面
所有的链表的结点
它都是动态分配内存的
所以这些链表的结点
在逻辑上它们是连续的
但是在物理上不一定是连续的
因为我没有办法规定malloc
没有办法规定new
它们分配出来的存储空间一定是连续的
你上来malloc一个 又malloc一个
或new一个结点 然后再new一个结点
这样分配出来的这两个结点
它们的存储布局在物理上你是没有办法
要求它们是连续分配的
逻辑上是顺序的 而物理上不一定
这是第一个要说明的地方
第二个 在访问和使用这个链表的过程中
要时刻注意这个链表的完整性
如果你在某一个特定的时刻
删除了这个链表中的某个结点
而你又没有维持这个链表完整性的话
那么链表的首结点
到链表的后续结点之间就会脱节
这个是一个完整的链条
你把其中某一个环给抠掉了
你又没有完整地将链表这个链接关系维持住
那么这个链条就断了
它会带来什么问题啊
这个问题是巨大的
因为他们在逻辑上是连续的
而物理上不连续的
所以一旦斩断了这个链条
那么后续的链表的结点都是无法访问的
需要特别去注意的
整个后续结点的数据全都会丢失掉
在链表实现过程中
我们当然可以实现很多种形状的链表
按照这样的图例的格式
这样实现的链表称之为单链表
也就是单向的链表
你看我们结点之间的关系
首结点 有个next域
然后指向它的下一个结点
下一个结点next域指向它下一个结点
这是一个单向的链条
你可能会说这些链表的结点域里面
不仅具有next字段 还有一个previous字段
这个链表的指向关系呢
将会返回去指向它的前一个结点
每个结点都如此的话
那么我们事实上就构造了一个双向的链表
不仅可以从前指向后 也可以从后指向前
这样的链表就叫一个双向的链表
如果我这个链表的最后一个结点（就是尾结点）
不是NULL值 不是空值
而是指向这个链表的表头
我就构成了一圈
就像我们自行车链条一样
这个就称它为循环链表
如果这个链表不仅是双向的
而且它还是循环的
那么我们就称它为双向循环链表
对于我们单向的链表来说
链表最后一个结点的next域
一般都设为NULL
我们图例实际上是画了一个接地的符号
表示它什么也不指向
-1.1 提纲
-1.2 程序设计的基本概念
-1.3 简单C/C++程序介绍
-1.4 程序设计的基本流程
-1.5 基本语法元素
-1.6 程序设计风格
-1.7 编程实践
-第一讲 C/C++基本语法元素--编程实践提交入口
-2.1 提纲
-2.2 结构化程序设计基础
-2.3 布尔数据
-2.4 分支结构
-2.5 break语句
-2.6 循环结构
-2.7 编程实践
-第二讲 程序控制结构--编程实践提交入口
-3.1 提纲
-3.2 函数声明、调用与定义
-3.3 函数调用栈框架
-3.4 编程实践
-第三讲 函数--编程实践提交入口
-4.1 提纲
-4.2 算法概念与特征
-4.3 算法描述
-4.4 算法设计与实现
-4.5 递归算法（一）
-4.6 递归算法（二）
-4.7 容错与计算复杂度
-4.8 编程实践
-第四讲 算法--编程实践提交入口
-5.1 提纲
-5.2 库与接口
-5.3 随机数库（一）
-5.4 随机数库（二）
-5.5 作用域与生存期
-5.6 典型软件开发流程（一）
-5.7 典型软件开发流程（二）
-5.8 编程实践
-第五讲 程序组织与开发方法--编程实践提交入口
-6.1 提纲
-6.2 字符
-6.3 数组（一）
-6.4 数组（二）
-6.5 结构体
-6.6 编程实践
-第六讲 复合数据类型--编程实践提交入口
-7.1 提纲
-7.2 指针基本概念
-7.3 指针与函数
-7.4 指针与复合数据类型（一）
-7.5 指针与复合数据类型（二）
-7.6 字符串
-7.7 动态存储管理（一）
-7.8 动态存储管理（二）
-7.9 引用
-7.10 编程实践
-第七讲 指针与引用--编程实践提交入口
-8.1 提纲
-8.2 数据抽象（一）
-8.3 数据抽象（二）
-8.4 链表（一）
-8.5 链表（二）
-8.6 链表（三）
-8.7 链表（四）
-8.8 函数指针（一）
-8.9 函数指针（二）
-8.10 抽象链表（一）
-8.11 抽象链表（二）
-8.12 编程实践
-第八讲 链表与程序抽象--编程实践提交入口
-9.1 提纲
-9.2 程序抽象与面向对象
-9.3 类类型
-9.4 对象（一）
-9.5 对象（二）
-9.6 类与对象的成员（一）
-9.7 类与对象的成员（二）
-9.8 类与对象的成员（三）
-9.9 继承（一）
-9.10 继承（二）
-9.11 继承（三）
-9.12 多态（一）
-9.13 多态（二）
-9.14 编程实践
-第九讲 类与对象--编程实践提交入口
-10.1 提纲
-10.2 四则运算符重载（一）
-10.3 四则运算符重载（二）
-10.4 关系与下标操作符重载
-10.5 赋值操作符重载（一）
-10.6 赋值操作符重载（二）
-10.7 赋值操作符重载（三）
-10.8 赋值操作符重载（四）
-10.9 赋值操作符重载（五）
-10.10 流操作符重载（一）
-10.11 流操作符重载（二）
-10.12 流操作符重载（三）
-10.13 操作符重载总结
-10.14 编程实践
-第十讲 操作符重载--编程实践提交入口
-11.1 提纲
-11.2 泛型编程概览
-11.3 异常处理机制（一）
-11.4 异常处理机制（二）
-11.5 运行期型式信息（一）
-11.6 运行期型式信息（二）
-11.7 模板与型式参数化
-11.8 题外话：术语翻译
-11.9 泛型编程实践（一）
-11.10 泛型编程实践（二）
-11.11 泛型编程实践（三）
-11.12 泛型编程实践（四）
-11.13 泛型编程实践（五）
-11.14 泛型编程实践（六）
-11.15 泛型编程实践（七）
-11.16 泛型编程实践（八）
-11.17 泛型编程实践（九）
-11.18 泛型编程实践（十）
-11.19 编程实践
-第十一讲 泛型编程--编程实践提交入口
-12.1 提纲
-12.2 程序执行环境（一）
-12.3 程序执行环境（二）
-12.4 程序执行环境（三）
-12.5 程序执行环境（四）
-12.6 输入输出（一）
-12.7 输入输出（二）
-12.8 文件系统
-12.9 设备
-12.10 库（一）
-12.11 库（二）
-12.12 makefile文件（一）
-12.13 makefile文件（二）
-12.14 makefile文件（三）
-12.15 编程实践
-第十二讲 Linux系统编程基础--编程实践提交入口
-13.01 提纲
-13.02 进程基本概念
-13.03 信号
-13.04 进程管理（一）
-13.05 进程管理（二）
-13.06 进程管理（三）
-13.07 进程间通信（一）
-13.08 进程间通信（二）
-13.09 进程间通信（三）
-13.10 进程间通信（四）
-13.11 进程池
-13.12 编程实践
-第十三讲 进程编程--编程实践提交入口
-14.1 提纲
-14.2 线程基本概念
-14.3 线程管理（一）
-14.4 线程管理（二）
-14.5 线程管理（三）
-14.6 线程管理（四）
-14.7 线程同步机制（一）
-14.8 线程同步机制（二）
-14.9 C++11线程库（一）
-14.10 C++11线程库（二）
-14.11 C++11线程库（三）
-14.12 C++11线程库（四）
-14.13 C++11线程库（五）
-14.14 编程实践
-第十四讲 线程编程--编程实践提交入口
-15.1 提纲
-15.2 Internet网络协议
-15.3 套接字（一）
-15.4 套接字（二）
-15.5 编程实践
-第十五讲 网络编程--编程实践提交入口
