00:00
下面我们来看一个双向链表的应用实例,前面我们讲的这些案例都是单链表的形式,那单链表存在一些什么问题呢?我们先来做一个分析。先来做一个分析,同学们看啊。单向链表呢,他查找的方向只能是一个方向,哪一个方向啊,就是它只比如说我要查找一个节点,我只能是从害的节点开始,一个一个的便利,是这意思吧,就是一个一个的便利,这是它的第一个问题。第二个问题,大家有没有注意到?对于单向链表而言,当我要去删除其中一个节点的时候,比如说我要删除。节点五就是数据为五的这么一个节点,那么我是找到这一个待删除节点的前一个节点,然后再删除的,也就是说单向链表呢,不能够实现自我删除,是这样一个问题吧,所以说你看我在这写了单向链表查找的方向只能是一个。
01:07
而双向链表呢,可以向前或者向后查找。第二个单向链表不能自我删除,需要考辅助节点。而双线列表呢,能够自我删除,所以前面我们的单向链表删除节电时,我们总是说找到temp的前就说找到待删除的,应该这样写啊,我们是通过temp总是找到temp。而temp的是什么呢?Temp是temp。Temp。是待删除。待删除节点的前一个。前前一个节点。是这样子的吧,同学们,哎,所以说这一点呢,大家要注意体会,待删除节点的前一个节点。
02:02
是通过这个方式来删除的。那么同学们现在我想。完成一个双向链表,首先我们还是老规矩,既然我要把前面的单链表升级为双向链表,我们先画一个示意图,帮助同学们理解双向链表和单向链表有什么不一样的地方,来吧。好,我们还是以这个链表为例来进行分析,好吧?我们以这个链表为例来进行分析。同学们往下拉。往下拉。好,同学们来看一看啊。如果我们是双向链表,那么它会怎么生成呢?它会怎么生成呢?我们来看一下,我们来看一下,首先对于这个双向链表而言,它的节点是可以这样生成的,大家看。
03:03
就是你它一个节点除了有一个NEX之外呢,它还有一个P。我把这个往上拉一拉。往上拉一拉。哦,这个next next呢,它是指向下一个节点的。下一个节点,而这个P呢,它是指向指向,注意听啊,指向前一个。指向前一个。一个节点,那也就是说我的双向链表,它形成过后呢,每一个每一个节点里面都有一个P。这个也有一个pre能理解啊,这有一个pray,这边呢,仍然也有一个P。那它在形成这个双向链表以后,它有一个指向下一个节点的next,还有一个P,那。这个地方为什么看不到了。
04:00
往这边再往上提一提好吧,这样大家就看的比较清晰,好,我们把这个向前指的这条线呢,也给它关联上。对不对,也给它关联上,好把这个线稍微放粗一点,同样同样同学们这个节点呢,也有一个指向前一个节点的一个P这个域,Pray这个域,好,那pre呢,是指向前一个节点的,我们同样这个第三个节点也有一个指向前一个节点的pre,那同学们看何为双向链表,大家看清楚没有,它可以从这个方向去查找,也可以像这样去查找。这就是所谓的双向链表,因为可以向前,也可以向后。那么既然有了这个双向链表,我们来分析一下,分析一下双向链表。链表的这个就是它的这个便利。
05:01
遍历添加。修改。修改。还有删除的一个操作。好,我们先来分析,把这个思路分析一下啊,它的操作的一个思路。思路分析完了,我们再去实现,好吧,我们先分析思路,再说代码实现。首先呢,我们来先来分析一下双向链表的这个便利。便利便利,同学们看到便利的话呢,它可以从前往后对不对,诶那当然你还是找到害的节点,然后往这边便利的,只是说他找到一个节点过后呢,可以找这个节点的前一个和后一个是吧,所以说便利的这个方式。方式和单向链表、单链表、单链表一样,只是只是可以向前查找。向前。
06:00
向前也可以,也可以向后。向后查找。是这意思吧,查找好第二个,我们再来分析它的这一个添加,我们看看它的添加。那么同学们,当我们去呃,形成一个双线列表,添加一个节点的时候,我们看看这个思路应该怎么走。假如我现在呢,有一个新的节点是20,我要把这个节点加在这个年表的最后,假如我们现在添加是默,呃,默认是添加到添加到链表的最后是双向。啊,双向链表,链表的最后,那么我们这个步骤应该怎么走呢,同学们看。同学们分析一下这个思路,是不是你应该这么做,首先呢,你还是要找到通过这个便利,先找到最后这个节点。因为你要听到最后嘛,所以说你肯定有一个辅助节点,先走到屁股后边。
07:04
是不是先?先我们先把思路分析,先找到双向,双向链表的最后这个节点。这个没有问题吧,第二步我们应该怎么样呢?第二步找到以后,找到以后我们就这样做,假如这个这个这个节点是temp节点,假设这个是temp节点啊,那么就应该连接起来,先让这个temp.next指向我们这个新的节点。实际上这个新的节点就是在加入的节点,我写成new hero load没问题吧,Hero load。那除了这个动作以外呢,你还得有一条线,什么线呢?就是要让这个新节点的,因为你这条线连过去,还要让这条线指反向指向它吗?所以说还得有一个动作,就是6HERO no.pre要反向指向我们这个temp。
08:04
这大家能理解吧,也就是说这两个动作才会导致这个这条线。先挂起来。是不是先把这个线挂起来,然后呢,你下面这句话,让这个P再指向它的前一个节点,这样不就是一个双向的连接吗。好,添加思路,就这样子的,我们再来分析一下它的修改。同学们修改双向链表的修改其实和单项列表一样,因为你也是找到找到这个节点过后把数据进行替换,所以说修改的操作思路和原来的我们分析到这里啊,和原来的单向单向链表。啊,单项链表一样,不需要再做特别的改动,好最后我们再来分析一下删除。我们分析一下双向链表的删除,比如说我要删除。
09:04
打个比方,我要删除这个数据节点,数据为五的这个节点,比如说这个节点我要删掉,我换成一个不同的颜色啊,同学们跟上我的思路,假如我现在要删除的是这个节点。假如我删除的是这个节点,那么如果要删除这个节点,我怎么办呢?同学们看,首先因为现在现在是双向链表,所以说你可以直接找到这个待删除节点,而不需要去找到待删除节点的前一个节点,为什么?因为它是一个双向的,所以说你没有必要像以前那么麻烦了,因此呢,我们要分析出来第一点。因为。因为注意听啊,因为是双向链表这样写双向。链表,而因此,因此我们可以实现实现自我删除,自我删除某个节点。
10:01
某个节点,那既然如此,因为你可以实现自我删除,所以说我们在找这个删除节点的时候,直接找到这个待删除节点就可以了,不需要像原先那样,还要找到它的前一个节点,比较麻烦,所以说这个呢,我们可以这样做,直接找到。啊,直接找到找到要删除的这个节点。节点。比如是temp。啊,比如是temp,假如说现在是temp,那么找到这个节点,你怎么把它删掉呢,同学们。你怎么把它删掉呢?其实非常的简单,你找到它过后,你这样做就可以把它干掉,注意听啊,看我的第一个动作,首先呢,我们写这样一句话,大家看能不能理解,就是让碰破,比如这个就是要被要被删除的啊。这个就是要被删除的,不再是要删除节点的前一个节点了,这个temp就是要删除的,那temp的什么呢?它的p.next等于temp.next。
11:06
大家看我这句话什么意思,就是这个节点。Pre它吗?它的next就它指向哪里呢?指向temp的下一个节点,也就是说这条线。便到这里来了。大看能看懂什么意思吧?能看懂意思吧,就是刚才我这句话就会导致我这个要删除节点的它的next。它的next的指向这个位置。大家能看懂吗?我觉得应该不是很难吧,诶诶这这这先说这。还还不如刚才呢,啊,我这个改造,哎,这样子就可以了,大家大家能理解啊,能理解好,然后呢,我们再加一句话,再加一句话,因为你现在还没有让这个节点。就是要删除这个节点的下一个节点的pre指向要删除节点的前一个节点。
12:02
我说的清楚吗?有点绕是不是?那就这句话应该怎么写呢?就是temp,注意听啊,temp.next点等于temp点,能绕过来吗?同学们。Pre啊,Pre,那这句话会导致什么发生呢?Temp的pre。是他吧,是这条线。指向哪里呢?臀部的pre,那就说这条线指向这了。能看懂吗?哎,能看懂啊,应该那同学们看,一旦这样做完了以后,同学们琢磨琢磨这事,当我们再去便利的时候,比如说我便利到第一个节点,再遍历下一个节点,是不是直接。到这来了,然后再到这来了,反向变历也是一样的,你看啊,假如我从这开始走,我先便利到这个节点,再便利这个节点的前一个节点,是不是直接。就到这来了,能看懂吗,同学们。能看懂吗?没问题吧,好,那么这就是我们的。
13:04
一个双向链表的遍历的一个分析,然后呢,添加的一个分析,注意啊,我现在分析的添加是以添加到双向列表最后来演示的,如果要添加到双向链表的中间会有稍微的变化。那么还给大家分析了修改的一个思路,双线链表的修改思路,还有一个删除的思路,我都分析的比较清晰了,同学们看看,呃,老师讲的这个增便利添加修改删除双向链表的有没有明白?有没有明白?好,如果说这块大家明白了,那么思路分析就完成,待会儿呢,我们下一个章节就把双向链表的这几个操作用代码予以实现。英语实现OK,那这一讲我们先讲到这里。
我来说两句