00:00
同学们,那现在呢,我们把这个双向链表来给大家实现一下,好吧,实现一下那当然了,我们在实现的时候呢,呃,可以在原先单链表的基础上做一个修改和调整就可以了,没有必要完整,就是完全重新写一遍,好吧,但是该改的地方咱们还是改一改。来吧,那现在呢,打开我们的eclipse,我现在新建一个类。新建一个类,我们取个名字叫做double double,双向的是吧,Double link的。林可的什么呀,List?对不对,双向链表一个DEMO。OKDEMOOK,那现在呢,我们把这个方法放进去。把这个方法放进去。小的来。好,同学们,现在呢,我们这样子做,首先呢,我们仍然是创建一个类。创建一个双向链表的类。
01:03
Class,那前面这个呢,我们就叫double。Double。Linked list,然后里面有哪些属性呢?我们可以参照原先的单向链表来走一把啊,首先这个hero hero我们还是需要的啊,Hero node还是需要的,我们把这个呢拿来用一下。好,这个呢,我要用一用好,我先拿过来,好吧,我先拿过来,但是拿过来过呢,因为你这边已经有个hero了,我把这个名字改成二没有问题吧,HERO2,那除此之外呢,我们这个地方还有需要一个节点。是不是需要一个指向前面的这个属性呢,就是。PRE。啊,Pre,我们把这个写上,这个是指向。哎,指向前一个节点。
02:01
没有问题吧,那这个地方肯定我要把这个构造器的名字改一下。而next和pre呢,默认都为空。就是你在没有。出你在没有给他指定next和pre的时候呢,它都是空,所以这个呢可以不用改,它默认为no。下面这个呢,也默认为no没问题吧,同学们。好,这个这个地方也,嗯,就输出它的编号名字和昵称就可以了,那现在呢,回头我们再来写这个double的,呃,Double link的list,好,首先呢,我们仍然要初始化,这个我就不写了,我拿来用一用。我因为它是带表头的嘛,我们双双向链表呢,我这儿也是带表头的,所以说我在这呢,还是。哎,还是把这个拿过来。啊,这句话我是需要用的。但是呢,因为你这里同学们看啊,你这里这个头节点呢,就不能是hero node了,22,因为二里面才有P,好,同样这边呢,也把它给二。
03:09
没问题吧,好,现在呢,我们仍然把这个话拿过来,就是返回它的头节点,这个呢,我还是要有可能要用到是吧,我也把它写过来。那这个时候返回的是,呃,这种类型的。没有问题吧,同学们,下面呢,我们来写这一个遍历,遍历双向链表的一个方法,我们刚才分析过电力双向链表的这个方法呢,和单链表一样,因此呢,我不需要改变,我拿过来用一下就可以了,我找到这个历史的方法。找到历史的方法在哪里?是不是在最后啊?这个呢,我拿来用就可以了,我不需要再重新写一遍。啊,不需要再重新写一遍。好,然后呢,我在这隔一下,同样道理,同样道理这个地方应该改成二,是不是因为我辅助的时候是按her load来做,嗯,下面这个地方呢,我们来做一个调整啊NEXT1这边又什么问题,他说不匹配。
04:12
嗯,那现在呢,说明我们这个higher load这个地方没有变,是不是这样也应该指向her node2这种类型呢?能理解吧,同学们好,那便利就这样做就可以了,不需要做额外的变化,我们再来接着写这一个添加,好添加了,我们先完成这个默认添加到双向链表的,呃,这这个方式就是刚才分析的添加数据,而为20的这个here no的节点,我们是怎么做的呀?好,把原先的这个单链表的拿过来做一定的修改。哪一个呢,从这找也可以啊,这样找的会快一点。在这儿不是有个ID吗?好,我把这个呢拿来用一用。
05:00
好,我把这个方法拿过来啊,同学们。我把这个方法拿过来,肯定要做调整呢,不是完全一样的,不是完全一样的啊好,我先把这个添加方法拿来,然后呢,我把它格式化一下,看我怎么改。首先,这个节点类型变成HER2。然后呢,这个地方也是。是不是有个辅助节点,辅助节点呢,它便利找到,最后是我刚才分析的,先找天要手先找到双向链表,最后这个节点没有问题吧。紧接着呢,这个这个就已经找到最后了,找到最后的时候,同学们看这里。当我们找到最后。退出二循环时,Temp就指向了最后一个。那现在。让。怎怎么样的操作就把我们这个双向链表关联起来呢,两句话,我们把这两句话写上这啊。呃,第一句话是不是刚才我们分析的。
06:02
Her temp.next等于这个新的节点。那就应该这样写,temp.next。等于你要加进来的这个her node。这个没问题吧,然后让hero node点。指向这一个它的最后这个节点。是不是这样就可以了呀?当Y推出他不就自行车,然后呢,把它连起来。我这做一个注释形成或者叫构成都可以啊,形成一个双向链表。没问题吧,好,这个添加呢就完成了,就是做一个是添加一个节点到双向链表的最后。哦,我现在是已最后完成,那添加完成了,是不是应该写修改了,我们把修改拿来写一写,叫修改一个节点的内容。
07:00
同学们还记不记得我在做分析的时候,我说修改和原来和原来的啊,这写错了,原来和原来的单向链表是一样的,那这地方我们就不需要做太多的改变,我们拿来用一用就可以了,找到原先的update拿来用一下。拿来用一下。把这段代码呢,放到我们的这个位置。是不是好里面做一定的修改,因为现在是双向链表的节点是he no2。OK,这个地方仍然是先判断是否为空,没问题吧,如果为空我们就不要做了,然后这边呢,还是二。啊,还是二,我用一个辅助节点先找到它下面没有问题一样的啊,找到它过后呢,该怎么改就怎么改。该怎么改就怎么改好,这个就不用改了,所以说从这看呢,修改双向链表的修改一个节点基本上和前面一样,只做了一点点改变,就是把节点的类型修改了一下,可以看到可以看到双向链表的呃节点内容修改修改和呃前面的和单项链表几乎一样。
08:13
单向。单向链表啊一样啊,只是什么呢?诶,只是这个节点的类型类型。的类型啊类型。类型改成了,改成什么了,改成hero node2。是这意思吧,同学们好,最后一个顶立的方法就删除一个节点,来这个地方要小心一点啊,删除节点呢,变化会稍微大一点。啊,从双向链表中删除一个节点。删除一个节点,好,现在呢,老师把这个代码拿过来,我要做。做一个调整。好,最原先的删除代码是这样子的。是不是最原先的删除代码是这样子的。
09:02
好,我拿来做调整。我拿来做调整,首先呢,这个时候我们要注意啊,要做几点说明。啊,对于双向链表,对于这个双向链表链表我们可以直接直接找到,找到要删除的这个节点。而不需要说找到这个要删除节点的前一个节点的,然后找到以后自我删除对吧,找到以后。啊,找到后,找到后自我删除即可。删除即可,那么删除的这个流程和步骤是不是老师这已经分析完毕了?是不是好,那现在我们先把代码写一写,你给我一个no。啊,你给我一个no,好,现在呢,我们来把这个代码做一点改进啊,我在这判断一下啊,判断当前。
10:02
当前链表是否为空,如果为空我就不去修改了,你不去删除了,对吧,我取一个如果hide.next。等于no说明什么呢?说明这是一个空列表。空链表,既然是空链表,我们给他一个提示,说链表为空不能删除,对吧,链表为空啊,无法删除,那这个时候呢,就直接return。没问题吧,好,紧接着呢,下面我们来找这个辅助节点temp,这个是一个辅助节点啊。这是一个辅助变量啊,或者叫辅助指针啊都可以。那这个flag呢,我们仍然是要的标识是否找到了,有这个带删除的节点找到了,好,下面呢,这个地方就不需要用next来比较了,我们直接用temp。
11:00
因为我们直接找到这个节点就可以了,所以说我这呢,对,那我既然是直接找到,我就这样写了next,大家知道为什么我这写个next吧,也就是说我直接从这个节点开始找就行了,因为我原先为什么是从这个high的节点走的呢?是因为我希望找的是待删除节点的前一个节点,但现在不一样了。我只要找到这个要删除节点就可以把它干掉,所以说你看我这做了改进,我直接让这个辅助节点指向hide.next也就是真正要删除的那那个节点。那个有效节点好,那这个地方就直接按temp来走,对吧,如果temp等于空,那说明我们就不用再找了,那下面这个next也不需要了,直接。让他比找到了啊,找到过后,呃呃,找到过后就就退出,如果没有找到呢,让temp temp往下走一下,当temp等于空的时候,是不是就意味着已经找到链表的最后了,是这意思吧,就是已经相当于说你已经找到,找到这个位置过后还这个还不是,然后又往下走了一步。
12:12
明白我的意思吧,就说现在大家要知道,知道现在这个temp,呃,退出的时候,这个temp指向哪里了,它实际上是指向链表最后一个节点的最后。应该这样写,已经找到链表的最后节点的next这个域了,能理解吧,但是我在做注释的时候呢,我我还是这样写,好吧,我还是这样,大家知道什么含义就行了,那现在呢,我们通过这个flag来判断。如果flag为真,说明我们找到了,那就删除,删除的话,这个流程以前这样写的就不对了,应该怎么走,是不是老师原先走过,就是原先是这样删除的,不好使了。因为你是双向链表,就不能这样删了啊,这是以前的单向链表的删除方式,单向链表的那双向链表应该是有两句话,哪两句话一句话是这个,再有一句话是这个,我们写一遍。
13:08
跟上老师思路啊,跟上老师思路temp。Temp点什么呢?点next。等于temp.next。这句话是干件什么事?这句话是不是形成了?这条红色的线。是不是形成了这条红色的线。是不是同学们好,然后呢,还有一条线不要忘了,就是我们下一条线就是什么呢?就是temp。哎,Temp。点什么呢?Next点等于temp点。这个能理解吗?这这一句话是不是就是形成了。这条线。但是同学们要注意,我这句话是是有一个风险的。
14:04
我这句话是有个风险的,为什么呢?打个比方,注意听啊,注意听,这边这个地方是有风险的啊,这里这里我们的代码有问题。大家看出来有什么问题了吗?有什么问题?假如我们要删除的节点,很不幸是最后这个节点。有没有这种可能性是删除最后这个节点?有可能吧,如果我们删除的是最后这个节点,注意听,如果删除的是最后这个节点,这句话没有问题。这句话是没有问题的,因为你删除最后这个点,你temp.p.next等于temp.next就相当于把你最后这个节点,这个最后节点的前一个节点制空。就是相当于这条线断掉了。对不对,但是呢,你你紧接着又做了一句话是temp.next.p等于temp,那大家想temp它已经是最后一个节点了。
15:05
如果你在next,相当于,也就是说temp最后一点,那temp.next已经是空了,空的前一个肯定是没有的。能理解吗?这方就说。就说就说下面这句话呢,有一个条件。有一点就是说,如果。要要区分啊,就说就说如果是最后一个节点,就不需要不需要执行下面这句话。这句话,否则,否则会有什么呢?会出现会出现空指针异常。指针异常你们不相信呢,待会儿你可以试一下。你们不相信,你就试一试,因为你如果是真的是最后一个,那temp.next就是现在我高亮的部分就已经是no了,因为你如果是最后一个节点,那这个其实等于空了。
16:03
你在空点。是不是控制的异常啊?老师有没有讲过这个东西啊,所以说这个地方有一个前提,就是它不是最后一个才这样做,那怎么写呢?就是如果temp.next它不等于空,说明现在你要删除的呢,并不是最后这一个,好,这条线就可以加进去。好,我们把它格式化一下。能理解吧,这句话一定要加上啊,否则会出现空子的异常,待会儿你可以试一下。待会儿你可以试一下好了。那下面这句话不用不用变,那到此为止呢,我们的帧这个这几个这几个就写完了,也就是现在的便利添加修改和删除全部搞定。根据我们分析就全部把它做出来了啊做出来了好,那既然做出来了呢,那现在呢,我们就可以来准备测试好,那代码的测试呢,我们放在下一个章节来进行测试,这现在这这几个方法大家都理解了吧。
17:06
理解啊,如果没有理解的同学呢,可以先再看一看,我先截取一段视频。
我来说两句