讲解（中）在线视频

现在，我们来看如何得到链表的表长

得到链表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)