当前课程知识点：数据结构 > 第2章 线性表 > 2.3 线性表的链式实现——链表 > 讲解（中）
现在，我们来看如何得到链表的表长
得到链表L的表长
将它放到第2个参数length里面
大家要知道
我们没有为链表设置一个表示表长的成员
所以，无法直接得到表长
那怎么办呢
我们从表头开始，去遍历、去循环链表当中
每一个结点
如果有下一个结点
我们将一个初值为零的计数器自增1
直至到达表尾
首先
我们设了一个指针变量
p
它的初值是L
也就是指向头结点
然后，一个计数器length
它的初值是0，注意，length的初值
往往跟指针的初值是相关的
因为，这时候p指向的是头结点
还没有开始统计a1这个结点
所以，length的值是0。这个while循环
它的条件是p->next
大家要习惯于这种写法
后面很多算法都是采用类似的写法
因为，C语言当中，只有0表示假
如果这个while条件要为真
它必须不等于零
也就是，不等于空
所以，p->next等价于p->next != NULL
如果p->next != NULL
length++，p是指向头结点的，p->next指向a1
a1是存在的
所以，length自增1
然后，我们应该让p指向当前结点的下一个结点，也就是p后移，怎么让p后移呢
大家看到C语言
中的赋值表达式，应该先看=的右边
因为，它是把=右边表达式的值赋给左边
p->next指向的是a1
那么，就将a1的指针赋给p
所以，p这时候指向a1
那么，相对于之前的头结点
这时候，p实际上是后移了
然后，回到循环
因为，p->next指向的a2是存在的
所以
循环要继续执行，length再加1
然后，p再后移，p->next指向
a2
再赋给p，p指向a2
继续往后
p指向a3，length等于3
然后，p再后移
length等于4，这时候，回到while循环，p->next是为空的
这时候，循环就结束了
循环结束，整个算法就结束了
这时候的length值就是4
正好是元素的个数
它的时间复杂度，很简单
这个while循环执行的次数，其实就是表中元素的个数
所以，就是O(n)
再来看
下一个算法，得到链表的第i个元素
我们得到链表L的第i个元素
把它放到第3个参数e里面
因为，无法直接得到表长
所以
我们没法像前面的顺序表得到第i个元素
那样，去判断i的合法性
另外
由于链表不支持随机存取
我们也没法像前面那样，直接通过i-1下标，得到第i个元素
我们依然要在遍历的过程当中，去得到第i个元素
具体来说
是从表头开始，依次取得下一个元素
直到找到了第i个元素或者到达表尾
我们设了一个指针变量p
它的初值跟刚才有点不一样
它指向了L->next，L->next实际上是指向a1的
所以，p的初值
是指向a1的
这里的计数器
它的初值也是1
刚才我们说过
计数器的初值往往是跟这个指针的初值相关的
因为，p已经指向a1了
所以，计数器的初值j，就是第1个结点
这个wile循环
它有两个条件
一个是p
一个是j p就等价于p不等于NULL 这两个条件分别代表什么意思呢 仔细思考一下 我们会发现，因为，在循环体当中 跟刚才类似，我们也是不断地 让p后移，那么，不断地后移，p总会为空，也就是遍历完所有的结点，都没有找到第i个元素 那我们必须在没有遍历完所有的结点的时候，才继续执行这个循环 所以，第一个条件p 表示的是，未到达表尾 那第二个条件，又是什么呢 计数器j 还没有找到第i个结点 这时候，j的值是小于i的，在这两个条件 同时成立的情况下 我们继续往后找 计数器加1，p后移 这个while循环结束的时候 实际上有三种情况 前面我们讲过，A && B 不成立了，循环退出了 那么，它的补集 是等价于 A不成立 || B不成立 A不成立 那就是p为空；B不成立 那就是j>=i，我们把大于等于再分为两种情况：大于和等于 先来看第一种情况 当p等于空的时候 也就是!p，!p要为真，那么，p要为假，也就是p等于空 p等于空，p一直向后、一直向后 最后，p已经等于空了 说明，我们还没有找到第i个结点 这时候，说明i值太大了 已经超过了表长 比如，在表长为4的链表当中，去找第5个结点 这时候，j没有机会到达i 在到达i之前，p已经为空了 所以，这时候i太大了 再看第二种情况 如果j>i j>i，说明i值太小了 正常情况下 因为，前面有一个 条件在限定 按理说 j是没有机会大于i的 但是它却大于i了，说明给定的i值太小了 小于它能到的最小值1 因为，i值最小，就是找链表的第1个元素 假设i值给的是0，甚至负数 这时候，j一开始就大于i了 所以 我们用第二个if语句来判断 i太小的情况 第三种情况 就是j等于i 这种情况，才是正常的情况 第i个元素是存在的 这时候，直接将p所指向的data赋值给第3个参数e 然后，返回0，就可以了 因为，这个算法在设计的时候，是返回int型 返回 算法它的执行状态 我们用-1、-2、0这3种值，来标识3种状态 -1表示 i太大；-2表示i太小 0表示 正常，找到了第i个元素 它的时间复杂度 我们就看这个while循环就行了 这个while循环 j从1开始，j能取到的最大值是i-1 那么，一共执行了i-1次 而这个i 它的取值最坏情况下，是能够到达n的 所以，我们就认为这个算法的时间复杂度是O(n) 现在，我们来看链表的插入算法 我们在链表L的第i个元素之前，插入e 为此 我们先需要找到第i-1个结点 原因在于，大家看这个图 我们要在a(i-1)和ai之间，插入一个结点 或者说在ai之前，插入一个结点 我们先申请一个结点 将这个结点的数据域赋值成e，同时 我们要修改两个指针 第一个 是将新申请结点的next成员，修改成ai 然后，再将ai原来的前驱a(i-1) 它的next，修改成新申请的结点 大家要注意，这两个指针的修改是有先后顺序的 如果找到了 第i-1个结点的指针 你先修改它的后继 那么，这个指向关系就不存在了 你就没法找到ai了 你没法找到ai 就无法让新申请结点的后继指向ai 所以，你得先 改这个指针 然后，再去改这个指针。ai的指针 实际上就是p->next 所以，我们只需要找到p 也就是a(i-1)这个结点 它的指针就可以了 我们来看具体的算法实现 同样，将p初始化成L，j初始化成0 两个条件，跟我们前面讲的，得到链表的第i个元素算法类似 只不过是i变成了i-1 因为，我们现在要找第i-1个结点 同样，while循环结束之后 我们判断一下 如果!P成立，或者是j大于i-1 说明i值要么太小 要么太大 正常的情况 我们申请一个新结点，是用malloc 前面我们讲过 malloc是C语言的一个动态内存分配函数 它的参数单位是字节 跟Java里面的new 调用构造方法是类似的 我们新申请了一个结点，malloc的返回值赋值给node，用node来指向新申请的这个结点 紧接着，我们要修改两个指针 刚才说过，要先修改这个指针 如何修改这个指针呢？无非就是将node->next修改成p->next 也就是将p->next赋值给node->next 大家要学会看这样的表达式 有些同学甚至以为，左右两边都有next，是不是能约掉，等价于p赋给node 完全不是这样 我们一定要先看右边，p->next 实际上是指向ai的 将ai的地址赋值给node->next 实际上是修改它 让它指向ai 第一个指针修改完了，修改第二个指针，将p->next，也就是这个成员，修改成新申请的结点 node 它的时间复杂度与之前类似 因为，j的取值从0到i-2 一共i-1次 i又是跟n相关的，最大值能取到n 所以，我们认为这个算法的时间复杂度是O(n) 再来看 删除算法，删除链表L的第i个元素 我们把删除的这个元素放在e里面 那删除算法呢 大家看这个图，我们要删除这个结点 无非就是让它的前驱a(i-1) 这个指针，跨过ai直接到ai的后继 a(i+1) 也就是跨过原来的ai 那么，将来从 头结点开始，找到a(i-1)之后，继续往后，就直接到a(i+1)了 我们还可以释放掉ai所占的内存 同样，因为要去修改ai的前驱a(i-1) 的后继指针 所以，我们也需要找到第i-1个结点 然后，修改p的后继指针 使其指向第i+1个结点 最后，再释放第i个结点所占的内存 如果是用C语言 最好手动地调用一下相关的API，去释放内存 如果是用Java这样的具有自动垃圾回收功能的语言 那么不需要这样做 运行环境会自动释放那些不再被使用的内存单元 来看 算法实现 这些代码跟前面都差不多 我们看最后的代码，找到了第i-1个结点 它的指针p，之后呢 我们先把p->next暂存到q里面 也就是让一个临时的变量q，先指向p->next，也就是ai 因为，将来要去释放ai这个结点 得知道它的指针 然后，将q->next赋值给p->next，q->next 就是a(i+1)，将a(i+1)的地址赋值给 p的next这个成员 实际上，就是红色的这个箭头，修改这个指针 这地方也可以写成 p的next 再next 赋值给p->next 因为，p是指向a(i-1)的 它的next再next 就是a(i+1)，赋值给p->next 因为，前面我们已经将p->next暂存到q里面了 所以，这边就等价于q->next 我们用第三个参数，来接收被删除的ai 它的值 最后，再释放ai所占的内存，free 是C语言当中的一个释放内存的函数 它的参数 给出你要释放的那个内存 的地址，就可以了 这个算法，它的时间复杂度也是O(n)
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
