00:00
好,我们先来看一看这段代码的,呃,一个改写的一个过程,首先呢,我先新建一个SC文件叫double。Double双向的就是指这么意思,Link的list DEMO。但是我可能有些地方我要粘贴拷贝不重写写了啊好,这是这么一段。那同样的道理,我这边呢,因为要管理这个英雄人物,所以说这个hide呢,我肯定是要拿过来用的,对不对,我把它拿过来没问题。好,我把为了,因为两个包下面都有这个文件,我肯定要把它改成HAD2。然后这面呢,我要加一个。这只有一个向后点,后面的一个节点啊,后指向后面的这个节点,那么我需要再加一个VRP。啊,P had这方也要改成二,这个没问题吧。好,等于no。那这面我写一个叫做pre默认默认注意听啊,默认也为这个no。
01:05
这点大家改进要看得出来,为什么会加一个pre呢?就是因为你这要多一个域,因为你有前后两个都值了吗?这个也很好理解对吧?好,那有了这个东西过后,下面呢,我们要写一个类叫class double,对吧,Doubleist。没问题,那首先我们还是按照这个图一步一步的走,首先这个头我们还是要要的。对吧,那这个投药药的话呢,我就直接从这边拿。我为什么不是整体拷拷贝过来啊,因为整体拷贝过来,这样大家更容易乱了,我一步一步的考。好,首先这一部分我仍然保留不变,但是这个呢要改成二。没问题,最后改成二,因为后面这两个默认为空,所说你也不需要做任何改变,这是第一个。就可以了,那么我们先来整一个添加,OK,那我们在做这个链表的一般是添加便历,一般是要写的,先写添加的方法,再写便利的方便历的方法。
02:07
啊,然后再写修改的方法啊,然后再写删除的方法。一般都是这样一个流程。好的,那现在我们先写添加,添加呢有两种方式,大家都知道,第一种呢,就是呃,不考虑排序,就是就是那样那样写就完了。那么我们先把这个添加拿过来用一用,好吧。但是肯定要变了,添加这个地方肯定要变,我们找到原先单向链表里边的第一个添加方法,最简单的就它来吧。拿过来哪个地方改,我们动动脑筋啊,各位同学们。大家都要动脑筋啊,OK,把这个呢拿过来好,Hide her load,当然这个应该变成二,这个能理解吧。是吧,然后因为头节点不能动,因此我们需要有一个临时节点作为辅助,这个添加时这样添加也没有问题。
03:00
因为添加你肯定是还是呃找到一个节点往加嘛,你肯定是找一个节点去加,好呃,我们这个地方第一种方法呢,还是沿用呃直接添加到链表的尾部,那这个时候怎么写呢?好这块找到尾部了,在这地方要加一个动作,加一个什么动作啊同学们。Hi,不点next型,它是这样子就不对了。就不能这样写了。因为这样一写的话,你的next节点就被就被破坏了,应该这么写啊,是不是应该这么写。因为你一旦找到了,就让hide是首先我们确定是不是它要加到痛的后边。说说他应该这么写点next。等于什么呀?Temple。哎,是什么呀,哦对对,写错了啊,不好意思,他是。呃,我们看看这个地方应该怎么写啊。呃,应该这样写。它是我们我们我们这样子找一个链,找一个具体的这样子好比较啊,比如说现在呢,我这有一个节点要加进去了。
04:07
假设是这样一个颜色。嗯,现在temp在哪里呢?Temp是不是在是在最后是吧,因为我这个逻辑是不是是考虑的加到最后的是不是这个意思,好,那这个时候temp temp现在是不是相当于指向这里了,各位同学这个能理解吗?Temp是指向这里的,因为我这个现在是加到最后,说到这里面只需要做一个动作什么呢?就是让这个temp.next指向它,然后让这个呃,新的节点的pre指向这个temp就可以了,是这意思吧,好,所以说这个没有什么太多要说的,这个地方不要变化,然后。Hero点。等于我们的temp。有问题吗?没有问题,因为现在我们考虑的是往后加。那当然有同学老师,如果我们是按照顺序来加,那这样写肯定就不对了,明白吧?
05:00
因为你如果是加到中间,你这样写肯定不对。你要比如你在加到中间,那这个temp,嗯,肯定要还要考虑,考虑的东西就更多了,因为你要把它连进去,它有四条线要连呢。是不是?好,我们说说为什么先找一个简单的,容易上手。好,这个写完了过后,我们爱的就第一种爱的方法就完事了,那紧接着呢,我们来把这个便利给同学们写一下。因为你加完了公就变力,变力这个方法同学们认为有变化吗?便利,是不是可以不用变化呀?因为我变历仍然是按照从前往后变,变历就行了嘛,这个方法其实是无需改变的,你看我还是判断是不是空,还是把这个head头交给他,然后一步写这个是不是不用变化。好,所以说这个这个便利不需要变化。便利,方法一样。好,现在我们可以来测一测了。啊,这样子双向链表肯定是可以出来的啊,我们先来跑一跑啊,那前面这段代码呢,我也拿来用一用。
06:10
哦,我拿来用用。好,这边。来走一个,我把这边拿过来用一下啊,看看链表遍历出来对不对,呃,HERO2这个节点。二。二好,然后呢,这有四个呃那个呃,Hero,然后呢,这边我们要把它改一下了,叫做double。Double的啊,这边呢,我也改一下。Double,诶,这个地方它。诶,这个地方,它为什么这个地方。改一下名字嘛,名字还是改一改吧,不然的话,你这个名字虽然不用改,但是实际上名字还是。意义不一样的,好,我们再显示它一下,显示的话呢,就double,然后我们list一下,看这个结果对不对,肯应该是对的啊。
07:03
走一个。好,我们双向链表跑起来。这个没有问题,但是你你怎么敢保证它是这样子的一个线呢。对吧。你怎么敢保证是这样一个线呢?不好测试呢。怎么能测出它这条线往这边线连起来了呢。是不是我可以这样子玩一把,就是我先便利到这个尾部,然后我反向便利是不是也可以啊啊实际上这个大家放心,肯定连起来,但是咱们没办法把这个内存拿出来给他看。因为你我每一步都是这样连的嘛,你想你来一个我就连一下,来一个这样连一下,它必然是一个双向链表。好,所以所以说这个双线列表肯定就形成了,这是我们的第一个这个这个便利方法一样啊,不用啊不用这个。啊,不用不用担心,那现在现在我们再来写下面一个方法,这个方法呢,我想留给同学们先思考一下,什么方法呢,就是。
08:07
现在有便秘了。我们修改。修改这个方法,大家觉得是不是也不需要改变啊?修改这个方法和前面这个方法有有什么不一样吗?大家觉得。如果是针对这个节点,是不是完全不需要有任何改变?因为我还是因为单向链表都能实现,我双向链表必然也能实现,所以说这个。修改这个方法呢,也不需要改变。我们先来测一下,修改这个方法我们拿到这里来。好。拿这个。修改这个方法,我们看把它改成漏端,下面都不需要变化。不需要变化,好我们来试试看这个能不能修改成功,修改成功好我们玩一下,那现在呢,假如我有一个新的节点了,来看一个。
09:03
我把二号节点改一下,比如说这是二号节点,我把它改成这个卢俊义。啊。俊逸好,然后这边是玉麒麟,我们把它改一下啊,玉麒麟。好的,那么这边这个hero呢,我把它改成五,我要进行一个修改,同学们看double。点update,然后呢,HERO5放进去,放进去过后,我们这打一个这个间隔线,打个间隔线过后呢,我们来走一下啊,我们叫叫list一下。看看这个二号宋江是不是变成了卢俊义,我们来看看代码有没有问题。好,跑一下。好,我们可以看到是没有任何问题的。没有任何问题,现在有一个事儿,就是要求大家来实现的。就是什么呢,删除。删除这个。
10:01
列表大家有思路吗?来,我们一起写一写,来动脑筋啊,这个要稍微麻烦一点了。因为双向链表的删除又跟原先不太一样了,我们来快速的走一下。删除。删除,我们还是这样写,把原先的代码拿过来用,但是呢,要改的地方我们改。删除这边代码我们是在哪写的呀,在上边。看一下。在上边儿这儿,诶,我找到了。同样,我反向的粘贴复制。好,我们来看看这段代码哪些地方需要修改。来,走一个。删除放这儿。好,首先你仍然给我一个no。我标记位不用改,还是因为这个删除呢,我们现在可以这样删除,我要使用自我删除。我要自我删除啊,就是我的思路是这样子的,注意听思路,因为。
11:04
因为这个双向链表,链表可以实现。可以实现自我删除什么意思?就是。比如我现在有一个我不看这个了,比如说我现在要删除的三号。比如说我要删除这个三号,我就让这个temp指向它,我把它干掉。所以我我想实现这个效果,因为找到这个节点,在干掉这个节点本身从逻辑上来说更容易理解。而我们原先为什么需要让这个temp指向前一个呢?是因为我们没有办法,而现在有双向链表的话,我就可以实现自我删除了。那现同学们看我们能不能实现呢?哪个地方改一下呢,首先。我们先来做一个判断,如果为空,我们不玩了,来做一个判断啊,判断这个当前链表是否为空,老规矩,If,如果我们的first,诶,这个head。
12:10
点next,它等于no,说明这个链表为空那。不可能做删除的操作,所以说这个就是什么呢?链表链表空,那就没法玩,直接return。OK。直接就完事了,那否则的话呢,我们自我删除,那就直接用next走。啊,直接用ma,为什么呢?因为我就可以直接让这个值跟它比较,那下面我就这样判断的,如果这个temp。等于no。如果这个temp等于我就break,然后这边我也不用next判断了,我就让他自己跟他自己让这个temp这个节点number和这个要删除number比好,如果找到就break。啊,这边这个地方后移没有变化,注意这这个地方仍然是,如果这个为真,说明的确有,如果为假,说明不存在。
13:09
但是这条线。要改了,好,现在我们来看一个图啊。同学们,我们。假如现在已经找到了要删,要删除这个三号这个节点,而temp本身就指向三号了。那么我们应该怎么删除呢?诶,是对同学们好,来,我们来看看。首先,同学们。N。我们关键是要把这个干掉,我们首先要把这条线连起来看啊,其实你要完成就是这条线。把这条线。紫香。他。好,我把这个标出标成一个,这个注意顺序也很重要。当然我就直接说这个正确的了,你看这条线,我要让原先那条线变成这条线,是不是很简单,我就这样写了啊,就是temp的。
14:09
Pre。点next。等于temp.next这个能理解吧,首先。你在这儿改变完了过后这条线才会断掉。就是你这样一改的话,原先这条小线就没有了啊。就是这条线就自然就没有了。一这个没问题,紧接着我们还要实现一个动作,就是这条线大家看。这条线。让它指向哪里呢?指向我们的这个节点,好,同样我用这个红线。那这条线怎么搭起来呢?这两样搭起来也很简单,就应该是temp。点next,点。等于temp.P而且你你你你能确定是这个P这条线其实没有动过是吧。
15:03
这条线你看你你动了吗?你没有动,是不是这条线还在这儿啊。只是他用完了过后他就没有用了。而且大家看这样一做完过后,这个节点其实也没有任何其他的节点指向他了,是不,他也是个垃圾了,也会被回收。你看一到这儿我便利到这儿一便利,啪到这来了,我反向便利呢,我一变反向变利,如果是这样一写,它就到这儿前区节点一下指到这儿,这个节点其实已经被抛弃了,对吧。好,那这样子的话,同学们,我们这个代码就写完了,我们来玩一把,看看这个代码对还是不对啊,各位同学来,我们先来看一下,我们来删一删吧。我们来算一算。嗯,现在代码我要准备删除。删除测试。没问题吧,那现在呢,我我要怎么删呢?好,我先删一个,我看一下目前是什么情况,目前是1342,我删一个中间的三号。
16:05
我先说一,三号来,同学们点鼎立。三号没问题吧,好删除删除完了过后,是不是我们也要测试一下呀,那这边我们打一个这个,呃,这个删除后吧。删除后。OK,然后呢,我们double double.list没问题吧,好,我们来看看这个三号有没有被干掉啊,注意听。好注意看啊,你看当我这样一执行过后,我发现。诶,三号是不是干掉了。但是有一个问题我说了,我们经常应该去判断它的边界是不是好,各位同学,我如果直接干掉二号,大家觉得有没有问题啊?有问题,问题还很严重,对不对,那么我们一执行他会干什么呀,他会抛出一个空置针。对不对。诶,为什么抛几个空指针呢。诶,你看这里,因为你想一想啊,你这种删除的逻辑,就这句话出了问题了,你你想一想,假如我们要删除的,我复原。
17:07
同学们,我复原。假如现在我要删除的就是这个节点。好,你看你的逻辑是怎么走的啊,你看你的逻辑,把你的这段代码拿过来注意听,因为咱们班每个同学基础不一样,所以说呢,每个同学都注意啊,我们先看第一句话有没有问题。Temp是在这里的。Temp是在这里temp.P但是它next好,就防到它,它去访问temp.next那实际上这个next变成了什么呀?空了,这能理解吗?好,这个是没有问题的,但是你下句出了问题了,你temp.next。喷不点next。不点next没有啊。你看temp不点temp点本身是个空的,空的怎么有前去节点呢?
18:02
实际上实际上如果我们针对这个最后这个节点,是不是只要这一句话就可以就可以了。大家能理解吗?因为你你这个只要把它的前去,就说你只要把它作为一个空,你置为空的话,从这边遍历都已然遍历不到它了嘛,是吧。所以说这个地方呢,其实可以这样加一个判断就搞定了,怎么样if。temp.next不等于空,我们才去执行这个操作。是不是只要你把这句话加进去就可以了?来,同学们,我们执行一下。我们执行一下。走一个我运行好,同学们可以看到最后这个节点呢,也被顺利的删除了。对吧,其实我这样删还是有一个有一个漏洞的,这样删会出现一个非常奇怪的现象。
19:01
你们你们你们有同学能把这个现象能解决吗?就是如果我这样删啊,你看同学们,我我删多删几个。我多删几个,同学们看啊。我三。我删这个三号。再删一个。几号啊,四号。好,那这样我一删除呢,代码,看看有没有问题,同学们看。是不是没有问题啊,是不是没问题啊,是对的吧,说老师那你这个没没毛病的来,没毛病,我们看看这个地方,如果我再加一个节点。我加一个,那我加一个什么呢?我要把这个。注意听啊,听一听,我把这个这个三号加进去。我把这个黑肉加进去。Hero加进去能理解这意思吧,我把它加进去了,这边加进去了,加入。
20:00
加入的话,我们再来打印一下。波浪号。诶,这个地方我们来找一个double点什么呀,List。我们看这个地方,按理说你这加一个hero,是不是这个地方删除完了过后变成这个你加一个hero hero这个二,二是编号为几的呀。二是编号为三的,是不是按理说这边只有一个一和三就够了?实验是吧,但是我们发现这个结果,我我我再看一下是不是这样子的啊。诶,怪了。怎么你掐了一个变两个进去了呢?你看你加了一个。很奇怪啊。你这是不是你加了一个黑是是三嘛。四三,但是为什么他把这个事业打出来了呢?对,因为有一条线你没断掉,就是刚才那条线没断掉,因为你你在这儿刚好如果删的是最后的那条线的时候,你这条线没有断掉,所以说这个问题我就留给同学们想这个地方,因为你看你这加了这么一个判断。
21:14
你加了这么一个判断,确实保证了最后这个不出问题。但是你也同时。出现了一个什么其他的问题呢?就是最后那个点,假说每删到最后节点,它的节点不是还保留在那的吗?他以后再连的时候,它是你连一个节点,它会把后面给一便利时候也给你遍历出来了,理解这意思吧。那这个问题我留给同学们想,同学们想想这个怎么解决啊,自己先思考一下,不是大问题,思考一下,我把问题先抛出来,好,同学们,那关于我们这个双向链表的这个先讲到这里。
我来说两句