现在想在这个链表中添加一个新的结点
它也有一些步骤
你必须严格地按照这个步骤来
我们会首先创建一个二维点的目标结构体
注意这都是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
如果要删除的是表头的结点
那我们就按照表头结点的模式进行删除
如果是非表头结点
那么就按照表中间的结点进行删除
如果是刚好是表尾的话
我们做一个尾指针的设定
如果不是表尾就不需要改变尾指针
按照这样一个模式就完成结点的删除