00:00
实现,那么现在我们根据刚才的分析呢,一步一步实现,我们新建一个包,这个我们就叫link的list。啊,Link的历史专门写到这个包包里面去。好,现在呢,因为是用单向链表写的,所以说我写个名叫single。Single link的list。啊,DEMO。OK。那现在我把它放到这里来,注意听啊,那首先我们这写个主方法,这个没问题,先先创建什么呢?Hero node。好,这段代码呢,刚才老师已经写过了,我就直接拿过来。先创建这个he no,那这里面呢,我们要做一个主构造器进行一个初始化,比如说hero no啊no一个int,然后名字呢,我们也给大家来进行一个初始化,还有一个它的这个外号link name。
01:01
死罪。好,基本上就有了,然后呢,我往里面副词her no,然后这边名字用传进来的名字,下边是他传进来的link clean默认,这个下面这个域,这个next域默认。默认为空。好,第一件事情就做完了,好,现在呢,我们来在这个基础上写下面的代码。啊,就是定义定义我们的这个单向链表,单向链表管理,管理这个hero OK,那么它是一个单线列表,那从我们编程的角度来说,也可以把它当做一个类。对,有单向列表的人是以面向对象的方式来实现的,所以说这个名字呢,我们叫single list。好。首先我们。从刚才这个画的图来看,这个整个这个链表有一个头节点,这个头节点呢,是不管你有没有放数据,它都会有这么一个这么一个东西,所以说我可以先初始化一下。
02:08
我先初始化一下来,第一步先初始化一个。初始化一个头节点。那么这个头节点呢,呃,一般来说不会动啊,一般来说这个头节点呢,不要动,因为你动了以后,你在便利和查找的时候就已经找不到了,所以头节点一般不动。头节点一般不会动。不会变化,不会动就不会移动啊,那么这咱们可以写这样一个东西,还这写一个呃,Had。等于我们直接六一个,在这直接给他分配一个六一个什么呢。Load,好,默认我给他一个零编号,默认零啊。好可以了,反正我也不用他说说我随便给给个纸也无所谓,但是呢。至少你最好不要跟后面的这个编号冲突好,因为后面我们的编号从一开始的好,这是第一个好,这个头节点我们有了。
03:08
投签单有了以后呢,我们来做下面的工作,编写添加。添加的这个方法。好,添加方法咱们。怎么往里面添加呢?好,现在呢,我们来写一个啊,写一个方法啊,比如说现在我们写一个D。方法DeFi的,那你要添加的时候,你肯定给我传一个。这个节点过来嘛,这是肯定的,所以说我首先呢,要接受一个higher load。对吧,那么我就写个海。OK。那添加时怎么形成这个链表呢?怎么形成这个链表呢?所以说大家看我们这个思路大致是这样子的,在添加的时候,我们这有一个方法,有两种方式,第一种方式就是我们不考虑这个排序。
04:06
不考虑排序,直接把它添加到我们链表的尾部。大家能理解什么意思吗?就说我们直接把它添加到链表的尾部。哦,把它添加到链家尾部,所以说我们先做第一种方式的处理。这先先来做一个简单的。第一种方法是在添加英雄人物时,直接添加到链表的尾部,那既然你要添加链表尾部首所说,我们这首先要找到这个链表最后是哪一个。那怎么来找到最后这个是哪一个呢?头节点又不能动。所以说这里往往在单量表里面会有一个临时的节点。做一个辅助功能啊,我们这定义,因为具体这句话我要把道理给你讲清楚,因为这个头节点,头节点不动不能动。
05:01
大家知道为什么不能动吗?因为偷镜链一旦动了,你以后再想去电表你你找不到他了,就好像我们有一有一个小朋友。在排队,第一个是老师牵着第二个小朋友的,如果这个老师都找不到了,那你整个队伍都找不到了,所以头几年不能动,因此我们,因此我们需要有有一个临时节点,有一个临时节点作为。作为辅助功能。辅助。OK,那现在我就这样写了啊,VAR temp等于head。什么意思,就说我待会呢,让碰搬过来做到现在我要做一件事情,就是找到。找到。找到什么呢?找到这个链表的最后,链表的最后是哪一个。那怎么找到呢?肯定要用while循环,那开始写了啊,While。
06:03
那大家想一想。这个链表最后你怎么知道是最后呢?因为只有这个next等于now的时候就代表最后了是不是?所以说你就做一个很简单的判断就可以了,如果这个temp.ne。Next。啊,这样子,我先写一张啊处。我先做一个死循环。啊,如果。如果什么呢?temp.next。它等于了,那各位这个条件一旦成立,说明什么?说明说明这个temp已经是。链表的最后了,能理解吗?如果这个不等于next,它肯定就最后嘛。杜老师,那这个你这你这上来不就最后吗,对的。你上来我刚就是最后,因为你headde给了这个temp,大家想想temp指向了hide headde,目前它的next u是不是在你还没加的时候,这个只有一个头的时候,这个头是不是就是最后这个呀。
07:07
好,那如果它等于这个,那就是你找到了,找到找到我就不要再找了,就直接break。对不对?那么我们再问大家一个问题,在一个单向链表里面,这个next等于空的,有几个节点是等于空的?是不是只有一个呀,只只能有一个好,那么就退出去,那如果说他没有到最后我就怎么样啊。如果没有到最后应该怎么办呢?如果没有到最后,是不是我就让这个temp继续往下走啊?这个能理解吗?你看吗?我打个比方,各位同学,假如我们看这个例子啊,因为我们很多同学第一次接触这种数据结构,那么举说我上来第一次,假如我这个链表。已经形成了,但是你如果说你说老师我第一个还没有没有,还没有的话,我可以认为这是我们的第一个投节点,大家看啊。
08:04
这是我们第一个头节点。在你还没有去做任何工作的时候,这个头节点已经形成了。这个next,它肯定默认是个空。然后呢,你上来过后,你整了一个临时变量叫temp,这个temp呢,它干什么呢,它指向了。延伸向它,那你上来这个temp.X就等于。就等于空,是不是就说说明他刚好就最后最后现在是不是就可以往里面整一个节点往里面扔进去了呀。是不是这个意思啊,好,那现在呢,我们回到这来,就说他只要跳出这个Y循环,就一定找到了链表,最后。所以说我现在需要来做一个break able进行一个。进行一个控制。好,这边有红色的是因为我们没有一个包,还记得这个包在哪里吗?UT点什么呀?CTRL.breaks。
09:07
对不对,点小心能理解吧。好,这样就处理了,那只要他跳出了这个外循环,Temp就指向了最后。这个没有问题吧,啊出来后这时。当。当退出这个while循环后,循环后注意听啊,这些都很有用的,都很有用,那我尽量讲的通俗一点,通俗一点,大家跟上思路啊,当退出Y循环以后,那么这个temp就是。就是链表的,链表的最后这个能理解吗?好,如果是最后是不是我把这个节点截到我上面就可以了。挂到我上面去就行了。那怎么挂上去呢?是不是你只需要让这个next指向你的这个节点就可以了,至于这个节点里面是什么内容是什么就是什么,无所谓嘛。
10:01
那这个时候你就要做一个工作就行了,做什么呢?Temp。temp.next等于我们的head,啊,等于我们的这个hero node。这个就结束了,大家看这段代码有没有什么疑问?这个就叫指向。什么叫让next指向谁?这个就是这个her load直接付给他,其实是这个her load的一个引用的一个地址是吧,实际上是交给他了吗?这不就关联起了吗?这个动作就是你们看到这句话再说一遍这一句话。就是代表这个。这个这个这个线的关联,就这句话就让这个线关联起来,以前是没有的,当你执行完这句话以后,这条线就。关联起来了。好,我们再考虑,第二个节点又来了。假设我们又去添加了第二个英雄人物。第二个英雄人物,那同样他在他在做这个工作之前,仍然让这个temp指向这个pad,所以说你们看到列表有一个最麻烦的地方,特别不好的地方是什么呀?它总是要从投节点开始来搞。
11:14
但是没有关系,因为后面我们会优化。等到二叉数的时候,我们会有很很好的一个二叉,这个这二叉排序数,说这学数据结构还是很很有意思的一件事情啊,链表他没办法,他总是要从头节点找。那你如果再有个节点,它会怎么算呢?假如我有来新的节点,它这样子temp。这个时候肯定不等于空了啊。这肯定不等于空,那么这个时候你新加的第一个节点,它的next是等于空的,我,我第一次稍微慢一点。那当你再加第二个节点的时候,它当前是这样一个状态,能理解吧,然后temp呢,先指向这个节点,好,然后它让这个temp判断,那等不等于空啊,不等于空,哎,不等于空,那你这就会执行一个。
12:01
Next付给temp这句话会导致什么事情发生呢?就会让这个temp指向第二个节点,这个大家能理解吗?是不是那他这个时候再一判断,发现这个next就等于空了呀。因为你你在没有做任何处理的时候,初始化的时候,这个就等于空好,这个时候这个temp呢,就指到这个最后来了,然后它跳出这个Y循环,再把这个next。在temp.next指向我们的。这个节点啊,但是我是花的幼儿园啊。待会儿我可能还要画一个。你看这个时候,当然一旦指向这个空就不是了,但是你新加的这个节点呢,它的最后这个next的默认就是空。好,以此类推上不停的往屁股后面追加,这是一个最简单的追加方式啊,同学们。我先讲的是最简单的,好,这个如果同学们没有任何疑惑的话,那我们现在就来。
13:00
再写一个方法进行一个测试了,我现在写一个方法来便利。遍历单向链表。好,同学们,便利的先念表,我就写个list。那我怎么来便利单项链表呢?肯定是要从头开始便利,而且这个头呢,你也不要去动它,也让一个跑龙套的帮我们来做这个事儿,好来命令我们首先仍然有这个动作。走一个。因为头节点不能动,因此我们需要有一个临时的节点来做,对吧?但是在便利的时候有一个问题,这个链表有可能是个空的,是不是我们就没有必要往下走了呀?那我问同学们一个问题。这个链表为空,什么情况下链表为空?是不是你上来这个high的点next的,它等于空,就代表这列表是空的,我就没必要便离了,是这意思吧?好,这点大家一定要注意啊,首先是要判断,判断当前链表是否为空。
14:09
别空啊,大家忍耐一下,这个这个听起来有点绕,但是很有用啊,我再说一遍啊,hide.next如果等于空不玩了。同学们注意,代写代码的时候一定要小心,很多同学写着写着,他容易把这个写成等号。尤其是JA旺里面这种还不报错。啊,像在这个像有些语言里面呢,他这个直接报错,有些语言他这个就不报错。一定要是等啊,如果是等,我们就提示一句话,说当前列表为空。电表为空,OK,那我就直接了,这能理解吗?不要再走了,如果不为空,好,同学们看我的思路了。这边我要做一点改变,大家看能不能跟上我的思路啊,我问大家一个问题。这个hide是有,它有我们需要的数据吗?Hide本身有没有?Hide本身有没有我们需要的数据,是不是在刚才我已经讲过了,这个数据本身我是不需要的,他只是为了做一个,做了一个方便方便我们操作而设计的节点。
15:14
说老师你如果不要这个头节点会怎么样呢?你们去试一下,如果没有这个头节点,这种链表的操作起来很麻烦。首先上来给你先判断是不是空的,然后再决定创建第一个还是第二个很麻烦,所以说人家有投进点,它是有有便利的地方的,而且有投进点它利于将来的删除。好,我们先不说那么多啊,那现在呢,我们说一句话,因为因为头节点。头节点的数据。数据,数据我们并不关心,我们不关心,因此这里这个痛可以直接这样子玩。大家能理解什么意思吧?因为我害的,如果我直接把害的给他,还判断这个是不是投太麻烦了,所以说我直接这样给。
16:07
而且这样给你也不用担心,因为前面我已经判断是不是为空了,这个head绝对不可能在空。至少他有一个吧。好,下面我就开始便秘了。那就现在同学们看老师的代码,看看能不能理解well。哦,这个还不不算难啊。这个还不算呢,这个还还很简单的。那么Y循环我就用这个temp帮助我们来编译,那这怎么写呢?是不是上来过后先把这个temp打出来就可以了,好,同学们,我们先打出一个。啊,当前节点我就要写节点信息。几点信息,我们,嗯,比如说我们只只把这个英雄人物的编号名字和。昵称打出来就可以了,好吧,那么编号呃,我就写啊,因为待会我要我要我要那个当前英雄啊。这个。
17:01
节点信息哦,No等于,因为待会我要判断,然后它的这个名字,名字是不是个字符串呢。好,还有一个Li claim。啊,百分之A大家能看懂吧,然后各位,那这边我要格式化了。然后这边我要换行,那这个时候no是谁呀。No是不是就是temp?点no。然后呢,这他的名字是不是特点name蒙啊。能看懂吧,然后ten。点。好,这个地方我们稍微往前挪一挪,这代码有点不好看,怎么办呢,换行。啊,你不要整的太长,一长串自己看起来很难受。好,然后这个打出来过后,我们是不是要判断它是不是已经到结尾接电了呀,你都要判断一下吧,判断是否到。到这个最后了,那怎么是最后呢?同学们是不是temp,只要等于这个no说明它到。
18:09
最后了,能理解吗?不是next,是不是next啊,而是臀本身了。呃,有些同学说老师为什么你不这样做,我告诉大家,如果你这样做的会这个代码写起来很困难,所以我就直接这样,这样玩的就是temp,他因为你你上来就是让让temp指向next,下一个实际上就指向第一个节点了嘛,啊指向我们第二个节点了,第二个节点就是我们真要数据好,那如果我。我判断它已经等于空了,好,这个时候说明它到最后了。好,到最后我就不玩了,我就直接break。啊有好,否则我我是不是还要继续去打印这个信息啊。我应该怎么做?是不是temp等于temp next?能看懂吧,好,然后整个这个while循环,是不是我们要用一个break able把它包下。
19:06
Break able。好,同学们。我慢点啊,慢点来。咱们把这个写完了,好,同学们,便利已经写完了,一个最简单的单项便利就写完了,那我们来玩一玩,看看这个行不行,好吧,把这个呢做一个测试。测试这个单项。链表的这个添加和。显示,或者叫便利。那现在呢,我我不写那个动态的了啊,因为时间关系,我不写那么多了,我就直接写一个数据测一下,我们先新建几个开就行了。Load,来吧,咱们一号人物宋江。好的,及时雨。及时雨。好的,那VR我们就来一个HERE1。
20:03
下一吧,好吧,就快速的测一下。好,同学们,二。三。二号。比如这是我们来个三号吧,来个四号,我为什么故意这样写呢?待会我想给你们告诉大家,如果我在后面加个二,你会发现二它放在最后的,好,那为了以示区别呢,把这个改成三。这大家能理解啊,我就不去写名称了,省的事,然后这个创建好了,是不是我们创建一个单向链表。啊,那么怎么创建一个单向链表呢?Single。呃,Single这个历史的好,这个时候我们VR一下。和single linked list,现在我就往里面添加数据了啊艾。我加HERO1按顺序来。皮二。
21:00
三。加进去了,加进去过后呢,我现在要准备把它显示出来了。啊,现在我就直接这样显示,就link list的点list。好,我们现在加了三个。节点进去,那么同学们在脑海里面应该这样想象,就相当于说我们这个链表。形成了。就在内存里边,他的链表就是长这个样子的,那现在呢,我们来打印,看看这三个人是不是能够。显示出来好运行。同学们请看代码,我们跑项目发现这个代码呢,诶有一个问题,哪里写错了呀?哪里写错了?这个地方有一个。呃,是。
22:03
你是把把这句话吗。哦,对,这个。Next。我们看看这地方是哪里写啊,要把这个提到上面去是吧。看看是不是啊,第一个节点,因为我在上面已经判断了呀。Hi的点next。这个很好看的。哦,把这个提到上面去试试看。再运行一下。走。哎,这就对了,也就说我们上来过先判断一下对吧,因为你你比如说打个比方,我们走到最后,走到最后它移动了过后再去判断,你看第一次我们先判断为为空,它肯定不为空,不为空我们就显示最后呢,这个信息也就打印出来了,看134这个目前有个什么情况呢?目前有个最大的问题是他不是一个有序的。
23:04
那你看。
我来说两句