当前课程知识点：基于Linux的C++ > 第八讲 链表与程序抽象 > 8.6 链表（三） > LinuxCPP0806
现在想在这个链表中添加一个新的结点
它也有一些步骤
你必须严格地按照这个步骤来
我们会首先创建一个二维点的目标结构体
注意这都是new出来的
我们用一个point指针
来指向一个目标点的结构体
这首先是要完成一个最基本的构造
假设这个数据传进来了
我们首先要动态构造一个新的结点
让t指向我们动态构造出来的新的结点
它有data域 它有next域
我们要将它的data域
设成二维点的基地址
我们要让data域指向我们的二维点
然后让它的next域设为NULL
如果这个链表的head域为NULL
说明什么
说明我们这个链表一开始就是空的
这个时候单独处理
就把它的head域和tail域
同时都指向我们新构造出来的
这个结点就行了
这个结点一挂接进去
就将作为我们链表的唯一一个结点
让我们head和tail这两个指针
都指向我们这个结点就OK了
如果不是 我们要做的是
要将新创建的结点挂接到
这个链表的表尾结点上面去
我们要找到这个链表的原始表尾结点
然后让这个原始的表尾结点的next域
不再为NULL 而是指向我们新创建的结点
再然后 让tail这个指针指向新的结点
而不是指向原始的表尾结点
这样就完成结点的追加
你可以看到我们这个函数的实现
我们先构造t这样一个结点
先new一个结点 然后让t指向它
完成它的data字段和next字段
当这个链表的表头为空的时候
做最基本的处理 将这个结点
挂接为这个链表的唯一一个结点 否则的话
我们将这个链表尾指针的next域设成t
然后把链表的尾指针设成t
count++ 递增链表的元素个数
那还有一种情况
我想把这个结点插入到这个链表的中间
那我怎么去处理 你看我们这个图
我们这个图是将这个结点
插入到这个链表的表头
我首先还是需要动态地构造一个结点出来
用t这个指针来指向它
让t的data域指向我们的point
然后让它的next域啥也不指向
设为NULL 接下来
我们实际上要让t的next域
指向我们这个链表的表头结点
因为它将挂接到链表的表头
这样的话原始的表头
将不再是表头的结点了
而是表头结点的下一个结点
这是我们第三步要做的事情
第四步 我们要让head这个指针
来指向新构造的这个结点
这样的话就让新构造这个结点
作为我们这个链表的表头
我们递增链表的元素个数
注意这些步骤是有顺序的
你不能倒过来
你比如说第三步和第四步
你首先要将新构造的这个结点的next域
指向我们原始的表头结点
然后才能将这个链表的表头结点
指向我们新构造的这个结点
第三步和第四步是不能颠倒的
你一颠倒就完蛋了
你要颠倒的话
如果说第三步你让表头结点
指向我们新构造的这个结点
这就不是链表插入了
而事实上将这个链表替换了
就只包含了我们新构造的
一个唯一一个新结点
原始的这个链表中全部的元素
都被我搞丢了 所以在操作链表的时候
不管是结点的插入 还是删除
在任何时候都要维持链表的链接关系不变
这些操作是有明确顺序的
同学们在编程的时候一定要记住这一点
如果是在链表的中间进行插入呢
这个情况和链表的表头插入有一点点差别
它事实上是多一个额外的步骤
首先第一步还是一样
我们要构造一个新的链表的结点
然后让t指向它
第二步我们让这个链表结点的data域
指向我们的二维点
然后第三步找到链表结点的
插入位置的前一个位置
你比如讲 我这个原始结点
表头结点 我们算1号位
这个算2号位
我们现在要在链表的1号位和2号位中间
插入一个结点
那就意味着我新插入的结点将作为2号结点
原始2号结点将会变成3号结点
所以当我们说
要把这个结点插入到2号位的时候
那么必须保证能够找到这个1号位结点
为什么 因为我要将这个新的结点
要挂接到1号位的后边
我要设1号位的next域
所以必须能够找到
这个结点的插入位置的前一个位置
我们设这个指针是u
我们就从标头开始向后查找
它的待插入位置的前一个结点
然后让u来指向它 一旦我找到了之后
就让t的next域
指向u的next域所指向的结点
也就是说我们让t的next域
赋值为u的next域
让它和u的next指向同一个位置
也就是指向原始的2号结点
然后让u的next域指向
新构造出来的这个结点
然后我们要递增
所以LlInsert这个函数的实现
我们这里面传了一个list
传了一个point 传了一个pos 总共三个参数
但我们pos这个定义跟刚才不一样
这个链表结点的计数我们从0号位开始计的
最顶头的元素是0号位而不是1号位
所以如果pos是小于list->count
它是插入在表中间的
如果是pos是大于等于list->count
那实际上就是追加在表尾就ok了
那么如果是pos小于list->count
那么我们就要在表的中间 或者表头插入
所以如果是pos是等于等于0
那么我们实际上插入到表头
除此之外 都要把它插在表的中间
否则我们是追加的
插在表的中间的时候
就和我们表头的插入当然是不一样的
就是我刚才那个图例所展示的
你必须用一个for循环来找它的next域
来找到它的u结点
找到你的插入位置的前一个结点
pos如果插在4号位
那我必须找到它的3号位结点
让u指向3号位结点
我们这个for循环做的就是这个事
能够完成找到待插入位置的前一个结点
接下来的一个操作就是结点的删除
我们里面有三个结点
如果我们想删除这个表中间的一个结点
我们怎么办 如果我们删除这个表头结点
没有什么可说的
我们LlClear在内部已经实现了
如果是删除这个表中间的某一个特定结点
那怎么办呢 基本的删除操作
和我们表头结点删除操作是类似的
但是你还要记得
就像我们在表中间插入一样
你首先必须要能够找到
待删除结点的前一个结点
所以第一步我要找到这个结点
假设要删除的是1号位 那要找到0号位
因为我要挂接这个next域的
让它跳过被删除的结点 指向后面结点
这样才能维持链表的链条关系
所以必须要找它前一个结点
找到了我就用u指针指向它
t指针将会指向我们删除的这个结点
第三步 我将把这个被删除的这个结点
从这个链表中给抠出来
也就是让u的next域赋值为
u的next域的next域
也就是t的next域
跳过它 这是第三步
如果t的next域 它不再指向其它结点
它是我们最后一个结点
那这个时候就要维持这个链表关系
我们实际上就释放它就ok了
让这个链表尾指针指向我们的u
接下来第五步和第六步
我们分别销毁二维点的这个目标数据对象
和链表结点的数据对象
还跟前面几个图一样
有些操作在图上是没有表示的
比如说递减链表元素的个数
比如说这些特殊的if操作
如果某种特殊情况
我们做一些特定的处理
这个操作在我们图示上是没有包括的
我们销毁了这个待删除的这个结点之后
那么我们就递减链表的元素个数
这个就是结点的删除
你可以看到我们的函数代码实现
如果list->count等于等于0 没说的
这个是空链表 直接返回
否则如果pos为0
如果要删除的是表头的结点
那我们就按照表头结点的模式进行删除
如果是非表头结点
那么就按照表中间的结点进行删除
如果是刚好是表尾的话
我们做一个尾指针的设定
如果不是表尾就不需要改变尾指针
按照这样一个模式就完成结点的删除
-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 编程实践
-第十五讲 网络编程--编程实践提交入口
