00:00
那同学们,我们下面呢,继续来接着前面的讲解啊,那既然我刚才已经画出了这样两张图对吧?一个是它的实际的内存布局图,一个是它的逻辑结构示意图,那现在呢,我们就来用代码一边来分析,一边给大家实现一个单向链表。那么同学们都知道,单项列表呢,最重要的肯定就是增删改查,也就是说再看我们这儿,使用一个带头节点的单项列表实现水浒英雄排行榜的管理,能理解我意思吧,就是说我用链表的形式来管理了一些这个英雄的这种节点英雄人物,那么完成对英雄人物的什么呢?真删改查的操作,这是我的一个目标。啊,那么呃,删除和修改和查找呢,可以考虑让你们自己去做,也可以带带你们来完成,那这样子啊,呃,因为在讲课的过程中呢,我希望同学们多学一点,所以说查找,包括这个删除、修改、查找,我们带大家一起来完成,那么一边分析一边完成,好这是第一个,第二个,那么我们来看,现在呢,既然我要去完成一个单向链表,所以说我先要给大家完成第一种添加,或者第一种创建我们链表,单链表的形式叫什么呢?直接添加在链表的尾部,不考虑排序。
01:25
什么意思?就说你给我一个英雄这么一个对象,我就把它加入到列表的最后。不考虑排序,把这个第一种方式做完以后呢,我们再来考虑,再添加英雄的时候,考虑他的一个排名。考虑它的一个排名,好,同学们现在呢,老规矩,打开我们这个地方,我画一个单链表的创建和创建的一个示意图。单恋。单链表的一个创建示意图,好创建示意图,所以创建其实就是添加,因为你添加的过程不就把这个搞出来了吗?还有一个呢,就是呃,显示显示单项。
02:09
单向啊,单向链表的一个分析,好同学们看,因为刚才呢,我这里不是有一张图吗。有张图我们重新来画一遍啊,来,各位。首先呢,我这里会有一个头节点,因为我这里面是做的一个带头节点的链表,好我们认为这是一个头节点。啊,当然这个这是个节点啊,这个节点这是个节点,这个节点呢,分成了两个啊,分成了以下几个部分,我待会儿会写一个类。啊,我待会儿会写一个类class。我会写一个hero node。就是一个英雄呢,就是一个her load里面呢,会给大家给他设置一些信息在里边去,我会给他设置一些信息在里面去,哪些信息在里面去呢?比如说这个英雄人物的他的一些属性和它的呃一些这个节节点信息,比如说待会我会设计这么几个东西,第一个呢是它的编号。
03:15
对吧,第二个呢,我们会给它设计它的一个名字,时钟类型的,我先简写啊同学们还有一个就是它的昵称。还有一个就是他的昵称。比如叫林克的内蒙。没问题吧,下面呢,我还有一个指向下一个节点的月,这个呢,我们就写个叫hero hero什么呢?No the next。也就是说,将来每一个节点,它包含的这个属性有这么四个。明白啊,这是头节点。我们认为这是头节点。头节点呢,我们不放数据,它主要就是用来连接整个链表的,就是头节点,注意听哈,头节点它的作用是干什么呢?它。
04:01
不存放啊,不存放具体的。具体的这个这个数据。那它的作用是什么呢?它的作用主要是起到呃,起到一个呃,它的作用是干什么呢?作用。就是表示表示这个单链表的头。哎,单链表的头,就好像我们这个节点,它它就是表示单链表的头,好了,现在呢,我们来看在创建的时候,我的思路这样子的。当我创建一个新的节点,比如这有一个hero节点了。这是个no的节点啊,我就叫hero no的节点。然后呢,我让这个头节点同学们看啊,这个头节点指向它。那么怎么指向的呢?大家看,头节点下面不是有个next域吗?哎,它有个next域,我让这个next域指向差,也就是说这个next。我用一个颜色啊,就next指行下一个节点,当然这个节点里面它有两个部分,一个是数据,就是它具具体数据就是哪些呢。
05:09
就这三个就代表它的数据能理解啊,那么还有一个域域也是next域,哎,Next域,这个next域呢,又指向下一个节点。又指向下一个节点。那理解啊。这个next域指向下一个节点。没问题吧,同学们。哎,指向下一个节点,就是这样子来做的,那么当比如说我再画一个。如果我还有一个呃,Hero load,它这个前面这个next域呢,又指向后面这个。这个next这样就形成了一个链表,那最后这个不再指向怎么办呢?它默认为no,就说我怎么去判断我们这个链表。哪一个是最后这个节点呢?是以这个判断它是否为空,来决定这个链表是否结束。
06:03
明白啊,这个就是一个添加的一个示意图。添加的示意图。大家能能理解这个意思吧,那么我们在便利的时候怎么便利呢?便利的时候显然我会设计啊,这是添加,刚才就是添加便利的时候我的思思路这样子的啊。我们先把这个思路写一下,添加式或者叫创建式,创建。创建第一步呢,我们先创建一个氦的头节点。啊,它的作用注意听啊,它的作用就是代表或者表示我们单链单链表的头能理解啊,然后呢,后面后面我们每添加一个添加。一个节点就直接加入到什么呢?对尾就链表的最后就是链表最后。
07:06
那么便利的时候怎么办呢?便利时这样说,啊,同学们,听我思路,听我思路啊,便利。便利的时候呢,我要这样做,我去设置,我会通过。通过一个临时变量或者叫辅助指针都可以啊,通过一个辅助辅助变量,变量帮助我们帮助便利整个单链表,整个链表好同学们思路我就分析完了,下面我们代码来实现一把代码我们来实现一把左左。好,现在呢,我们来看一下这个单链表的具体实现啊,我把这个先关闭一下。哦,单列表的具体实现。好,首先呢,我在这里新建一个包包。新建一个包,OK,没问题吧?那么既然叫链表,我直接取个名字叫林可的list。
08:03
Link的list,好,我新建一个文件,那新建一个类。我们取个名叫single single什么呀,Link的list就是单列表,没问题吧,Link的单列表,好,我把这个先干掉。那首先呢,我们先创建一个黑节点,根据刚才的分析,是不是先要搞定它呀。因为这个节点将来它是真正存数据的嘛,也指向下一个节点,所以说你先要定义一个load。就是节点啊写定义。说啊,定义一个hero node。好,那么每一个啊,注意听啊,每个hair no的对象,Here no的对象就是一个节点,能理解好,那开始写了,Class hero node,刚才分析里面有这么几个属性,我就写进去了啊,我用public public string,它的名字我就写快一点啊,这个很简单,Link的name。
09:07
没问题吧,这个代表昵称,代表昵称,那下面呢,有一个重要的就是下一个月hero no,对吧,No no next,这个指向下个月指向。下一个节点。Her no这个单词写错了,加一个O。大没写完,那既然有了这个东西,你是不是应该有一个构造器啊?构造器是不是应该写构造器?好,构造七我就写上啊,Public。那构造器你要给我传什么呢?至少传三个信息进来吧,比如说我写一个h no英雄的编号对不对,String。你再给我传一个英雄的名字,你再给我传一个英雄的昵称。好就行了,当然我们把它初始化一下,No是不是等于你传进来的这个值。
10:03
没对吧,This点它的名字就等于这个你传进来的值。对吧,我们把这个带进去就可以了。没问题啊,然后呢,Z点啊这个地方我们Z是点呃,我们的link。Link link link name在于你传进来的这个值。好,我为了以示区别这样做的,当然你如果说对方说老师我不想这样写,我自己写个N也可以啊,你要这样写也是可以的。也没问题啊,我们把它改成这个形式也好啊,然然后呢,这边是呃,内蒙这边是link name一样的啊一样的好,这个做完了过后,为了将来显示比较方便呢,我重写一下这个图书顺。对吧,为了我写句话啊,为了显示方便,我们重写一下这个to string方法怎么重写?很简单吧,直接把这个打出来,大家都打出来就行了。
11:04
是不是很简单?好,我把这句话呢写到上面去,重写我们图斯村,那也也就是说现在我们这个节点已经就把它创建起来了,创建起来了,那下面我们要做的事情是什么呢?好,下面我们要做的事情就来创建这个single。单链表,好,我们现在开始创建这个东西了啊,来定义或者要定义都可以啊,我们定义一个single什么呢?Link的注意听讲啊,Link的list干什么呢?来管理我们的这个英雄。英雄人物啊。英雄。英雄好,那我开始写了,Class什么呢?Single link的list。根据刚才的分析,是不是我们首先要去做一个这个头节点呢,对吧,这个没问题,好。
12:04
这个门体他说已经定义过了,我们保存一下。哦,因为前面这个名字有了,那我把这个名字改成DEMO。好吧,这个它是一个测试,那我把这个名字改一下。我把这个名字改一下。把这个名字修改一把,修改一把加一个DEMO就可以了。演示的嘛,对吧,演示的分离取向。好,下一步。好,改一下就可以了。保存一下。De Mo,好,那这个地方我们就不要它了,好那就可以了,对吧,没问题,好现在呢,我们先去先初始化啊,注意听初始化。初始化一个头节点。头节点。好,这个节点干什么呢?这个头节点一般不能动,头节点不要动,为什么头节点不要动呢?同学们想一想,就是因为你将来在进行这个便利的时候,这个头节点是它最前面,如果这个节点变化了,那你将来就找不到我们这个链表的最顶端,这个是不是?所以说这个不要去动它,那么我就先把它写出来好不好,那就写一个private。
13:17
Hero load是不是?然后呢,Head等于六一个her load。还有这个这个呢,我们初始化第一个为零,名字没有昵称,我们也不给。啊,这个呢,它主要用来是表示头节点的,并不存放具体的数据啊,不写上啊,不存放具体的数据,这样思路好,有了这个方法过后呢,下面我们就来完成这个添加的方法是不是好,我们现在添加方法。添加什么呢?节点节点到我们这个单向链表。大家相表能理解啊,那就写了public void ADD,你在添加的时候是不是应该给我传进来一个he load。
14:04
这个能理解吧,就说你添加的时候,你要给我传进来一个here no。那么我在这个时候应该怎么去添加进去呢?来看一下。是不是你在添加的时候,最重要的就是找到,你看这里我们每添加一个节点,直接加,添加到链表的最后,那也说你一定要想办法找到这个链表的最后,假如。我们。那要添加,那你那你这个添加到最后打个比方吧,说现在在这样一个情况下,我们就以这个为例啊,我现在有个新的节点来了。有个新的节点来了。那你现在是不是首先要想办法找到这个链表的最后这个节点?是这意思吧,找到这个节点,然后让这个节点的next这个域指向。我们这个节点。这个事情就是不是就就完成了。
15:01
大家看是不是这个意思啊,就说。当然这个你要肯定要改嘛,你这个next这个空就不再是空了,就要指向它嘛,也就你的思路是要找到最后这个节点,然后呢,把。把最后节点的next域指向这个新的节点,是不是就完事了?好,我的思路已经来了啊,那下面我们来搞定这个事情。搞定这个事情,好,我们的思路这样子的。我把这个思路写到这里。啊,思路当当不考虑,不考虑这个编号的顺序时。顺序啊,顺序是对吧,我们的思路这样子的,找到,找到当前这个链表的最后这个节点。旧节点是什么就是什么,然后呢,将最后最后这个节点的next域指向哪里呢?指向这个新的节点即可。
16:04
这意思吧,好,同学们,那现在我们就来开始做第一件事情,首先呢,我们需要一个辅助节点啊,因为头节点就是派的节点不能动。这个节点不能不能动,原原因我已经讲过了啊,不能动,因此呢,因此我们需要一个辅助节点。啊,辅助这个辅助指针吧,辅助指针。辅助变量吧,辅助变量,比如说我们就叫temp。啊,那么现在呢?我们怎么做呢?我就这样写hero node temp。等于害大家知道这什么意思吧?也就是说,现在你要想象到有个temp指向了head,如果按这个图的话呢,相当于。这儿有一个temp。有一个temp变量指向了头节点。那么我这个temp节点怎么能找到最后这一个呢?显然要便利。好,现在我们写上这句话。
17:01
想着啊,便利。遍历链表。链表找到找到最后找到这个最后能理解吧,最后那么怎么便利呢?肯定Y循环。我我写一个出死循环啊,死循环那怎么找呢?我这样判断什么时候注意听啊,什么时候说明这个链表到最后了。当什么,就是说当这个情况下啊,你看我写大家看能不能看懂,如果temp.next。它等于了空,说明什么问题?是不是这个时候步找到最后了啊,就是。下面就是就是找到找到链表的最后了,能理解吗?因为你不点next等于空了。那肯定就是假设你上来过。害的节点就是只有一个,是不是害的节点就最后这个。啊,那如果你嗨到几点不是他就不停的找吗?好,如果是这样的话呢,我们找到了。
18:01
就这个条件说,说明已经到最后了啊,那如果不是我们怎么办呢?啊,如果没有找到最后是不是我们这样写。大家看看我的思路,是不是我让这个臀步往后后面移动一下对不对,这个就说如果没有找到就。就将这个temple后移。后羿。后羿,那么后羿是什么意思呢?就是说相当于说如果第一个不是。是不是往里面移动一下,如果再不是。如果再不是。好,到这儿发现是了,但原原先这条线还没有啊。是不是到这诶发现是空,然后你再点嘛,好也就是说。也就是说,当我们退出这个while循环的时候,说明碰指向的是链表的,最后这个能理解吗?就是当退出这个while循环时。循环时,那么temp就指向了指向。
19:03
A选项啊,指向了什么?链表的最后,链表的最后。那这个时候你就把它连上就可以了,是不是点next等于谁新的节点?是吧?这句话就是说,将最后这个节点指向新的节点就完事了。代码就完成,也就是说这个添加就搞定,那么添加搞定过后呢,我们需要做一个验证,所以现在呢,我们再写一个方法干什么呢?就是显示链表。然后显示列表呢,也要通过遍历。是不是需要通过遍历啊,那现在同学们老师就开始来写这个东西了啊,因为这个节奏咱们稍稍微放快点list。好,显显示这个链表是不是跟老师刚才一样,也要通过一个辅助变量。辅助通过通过一个辅助变量来便利。便利啊便利,我们这一个电表为什么需要辅助变辅助变量。
20:02
辅助变量,为什么需要一个辅助变量呢?因为你temp是不能动的啊,就是害的几点不能动是不是好,我们现在同样的道理,我们来写上这句话啊,好的,呃,首先呢,我们这样来做啊,大家跟上老师思路先判断。判断链表是否为空。如果列表为空,就是一个数据没有,那么我们就不要遍历了。什么情况下为空呢?hide.next。它如果等于呢?No,各位同学说明什么问题?说明链表为空没问题吧,同学们是链表为空直接退出就完了,直接能理解吗?好,下面我们继续来看,如果它不为空不为空,好,这个就是刚才我们所说的啊,还是那个道理,因为头节点不能动。节点。啊,不能动。因此,因此,因此我们需要一个辅助变量来。
21:05
来便利对不对,那代码就比较简单了,那同学们我想这样写啊,还是跟刚才一样,Hide。Head no temp等于hi.next。Head next。因为我刚才已经判断了这个。写错了啊,Hero,就是我刚才已经判断了这个hide呢,这个列表不为空,说明它至少有一个,是不是至少有一个数据啊好,那下面我们就开始遍历了哇,循环。我坐。没问题吧处好,现在呢,我们先来判断判断是否到最后了,到链表最后,因为我要退出嘛,链表最后,那怎么在这种情况下,什么情况下才是链表的最后呢?非常的简单,就一句话,如果temp等于空。是不是说明说明这个。
22:03
呃,这个就就为空了呀,你就为空,那如果如果为空那么一句话,我们就做一件这样这样一个跳转动作就行了,就退出去就完了,是吧,直接break,我就直接break就完了。因为这个时候你已经便便利的时候已经到了最后嘛,如果你没有这个条件,那永远是个死循环呢,所以你需要来做一个小小的判断,好,那现在呢。如果它不等于空,我们应该怎么办?是不是这个时候我们就输出输出这个节点的信息就可以了,好,输出这个节点信息呢,也非常简单,我们先点out一下就可以了。对不对,甚至连out就可以,而且这个节点同学们都很清楚知道我们已经重写。是不是已经重写这个图论方法了?也就是说,此时此刻,我只需要把这个temp。打出来就可以了。是不是这句话就会把整个节点的信息打出来,打出来完了过后不要忘忘了一句话啊,将这个next的后移。
23:08
同学们,知道为什么要后移吗?因为你想你在便利的时候你的你,你在便利的时候你你原先寸步走到这。嗯,你你只你只能是这个地方的指完了过后,你把它输出来了,输出来过后你不得输出下一个吗。是不是这个道理啊,同学们,因此你需要后移,不后移是是个死循环啊,一定一定要后移,一定记住一定小心啊,不然它是个死循环。那么怎么样来走呢?temp.next。后羿。对好,那这样子的话呢,经过一番这个历史的一个处理呢,那显然我们这个显示就写完了,非常的简单,那同学们我们测一把。测吧,啊,那现在呢,我们来简单的写几个案例,来测试一下我们这段代码是不是正确的。哦,我们这段代码是不是正确的。
24:00
好,现在呢,我们来进行一个测试啊,测试好,现在首先我们先来创建几个节点,没问题吧,同学们先创建。啊,先。这个怎么回事,这个玩意先创建。创建节点,好,我就快速的创建几个哈,呃六一个hero。好,第一个呢,我们排名为一的宋江。宋江,没问题吧,昵称及时雨。及时雨。好的同学们,那现在呢,我给他分配一个。好,假如这是我们的第一个变量。第一个变量,我就小HERO1吧,好不好HERO1。好,下面呢,我们再来排一个二号人物,二号人物是啊,我就随便写啊,吴用。对吧,吴用呢,比如说他是二号人物,其实是卢俊义啊,小卢行卢卢。
25:04
俊逸。好,卢俊义呢,他是玉麒麟对吧,玉玉麒麟。OK啊,第二号人物也有了,好了,我们再来放一个第三号人物,第三第三号人物呢,大家知道是,呃,无用叫智多星对吧,吴用吴用外号智多星。写上智多星欧了,好,我们再来第四个人物,第四个人物是林冲,对不对?排行第四的是林冲。二零冲。啊,不管是谁了,我就随便写啊,豹子头,豹子头。诶,豹子头。爆炸头了。好了,我就随便写了这么几个人,那现在呢,我把它加进去,加入,加入之前我们先先要创建一个列表是吧,也就我们要创建一个链表,能跟上我思路吗?六一个single。
26:02
Single OK,好分配一个single,那现在有了这个单项链表,我们加入的时候呢,我们就来往里面加点爱加第一个人物HE1。以此类推啊,以此类推。好,我们加上这四个人进去。好的,同学们,现在呢,我们显示一把。显示一把。我们看看目前写的这个单链表是否能够顺利的运行,点一个list跑起来走一个啊好,同学们,我们可以看到现在电电表呢,没有毛病。应该没有毛病啊,完全正确,那现在有一个问题,你看我们有一个什么问题呢?因为你在这编译的时候,为什么它会反复打压。大家知道为什么吗?你看你打第一个人的时候,宋江的时候,他居然会把卢俊义也打出来。谁能告诉我这是什么原因?谁能告诉我什么原因,是不是因为你在打这个第一个人物的时候,他在里面有个next域,这个next域呢,又指向下一个,是不是它相当于一串全部打完了呀?
27:08
是不是这道理,因此呢,我们这个地方呢,把这个next就不要打了,因为next在打这个,他就会打第一个人的时候,他会把后面他的next全部打出来,你看这是为什么最后这个人只打只打了一个包子头。而其他人总是会多打,就这个道理能明白吧?好,那我把这个稍微改一改,我这边就不要再打这个next域了,Next域把它去掉就行了,好吧。我不要这个东西了。把这块拿掉就nextx不要了啊,Next不要了。好,去掉它。这样看起来比较清晰一点。好朋友们,我们再来运行一把,这样看着就比较清晰。走起来,大家看,第一个人物是宋江。昵称为什么没打呀?啊,昵称没打出来,忘忘写了昵称,呃,加一个吧。加一个昵称,昵称的话加这吧,啊。
28:03
多删了一个linked。好,我们再跑一跑。再跑一跑啊,同学们看第一个人物,宋江,及时雨,卢俊义,玉麒麟,吴用,智多星,林冲,豹子斗好同学们,那现在有一个问题,就说我们现在其实已经把我们的这个呃,链表创建起来了,但是有一个问题。有什么问题,同学们假如我说假如啊,我把这个四号人物在第二这个地方加进去,我请同学们思考。此时此刻你你这个顺序应该是什么样子的?就说假如你先加的是第一个英雄,你紧接着加了第二号英雄,我问大家,此时此刻你这个英雄的排序正不正确?你的英雄排序正不正确?来,我们看一下。我们运行时你会看到呢。第一个是及时雨,第二个就变林冲了,为什么?因为目前它是按照你添加的顺序来添加的。
29:05
也就是说我们目前这个ID呢,我们这个ID没有考虑编号。是不是没有肯定编号,那如果我给大家提个第二种写法,就是我们要求同学们。干一件什么事情呢?再添加英雄的时候,根据排名,我不管你按什么顺序添加,始终按照排名将英雄插入到指定位置。如果这个排名已经有了。添加失败,并给出提示信息,这个就是待会儿我们要做的第二件事情。也就是说现在我们已经把什么呀,把第一个按照顺序添加做完了,那待会儿呢,同学们,我们来,我们要完成。第二种。添加英雄人物的分析,还有它的代码实现,好同学们,那关于第一部分单向链表的创建和直接添加到链表的尾部这一部分的内容呢,就先给大家讲解到这里。
我来说两句