00:00
来,那咱们就继续再往下了,那这个数据结构当中啊,我们得看一下这个link list它是个啥。对吧。咱们看一下这个啊,首先要看这个,我觉得首先这个得需要学习一个数据结构,这是一个单,这是一个双向链表的数据结构。对吧,那它其实除了双向列表之外,还有个单向列表。我们看看链表的处理结构,好吧?保存一下各位啊,保存一下。对,29的。链表数据结构。单列表啊,单项列表。我们去先学一下这种数据结构,各位啊。假如说这个呢,就是我大脑抽象的一个内存。各位啊,就是内存,假如说。啊,内存什么叫单向链表呢?单向链表链表当中啊,它最基本的单元是什么呀?是节点。
01:01
是节点各位啊,表当中最基本的单节。对于链表数据结构来说。呃,基本的单元是几点node啊,几点node。那对于单列表来说呢,任何一个节点里边都有两个属性啊。对于单链表来说,单项啊链表来说。任何一个节点node中都有两个属性。啊,都有两个属性。哪两个属性第一?是什么呢?是存储的数据。第二是什么呢?是下一个节点的内存地址。下一个节点的内存地址啊,这是对于我们这个链表数据结构啊,基本单元是节点note,对于单向链表来说,任何一个节点note中都有两个属性,一个是数据,一个是下一个节点的内存地址。
02:12
啊,你比如说我在这里,我可以自己写一个单链表。单列表啊。在这我加SE啊,新建一个package吧。Package。单链表单链表啊,单link。这个啊。新建一个class。我想。Link吧。啊,Link。然后呢,单链表。里边最基本的单元是什么呀?是节点,我在这新建个class叫node。
03:02
这是单列表中的节点啊。节点是单。像链表中基本的单元。每一个节点no的都有两个属性。一个属性是存储的数据。另一个属性是下一个节点的内存地址。所以。这个note当中啊,应该有什么呀,有两个属性。Element这个呢,就是存储的什么数据是吧,它应该有下一个什么节点的内存地址吧,下个节点是不是no的呀。你下个节点还是no,所以那就是no next。啊。对吧,你可以提供构造方法。
04:03
构造方法无参的。是不是啊,午餐的午餐的,你这个值默认值是空,这是空呗。对吧。然后再提供一个有参数的构造方法。提供有餐的,这个有餐的话。这个object element是吧?那就写上this.element呗,Element对吧?this.no this next next。构造方法,两个属性啊,这是无参的构造,这是有参构造。然后呢,你这个链表这块怎么着啊。给个什么?初始值对吧,叫no header问是空。行吧,哎,这就是个列表,各位头节点。
05:02
几点啊?然后你在这里可以怎么着啊,给他提供方法。对不对,哎,叫爱。增的方法,往列表上添加元素的方法是不是?Object来,我先写上啊,一会说一下这是像什么,像列表中添加元素的方法。对吧?你会再提供一个方法,Remove删除的方法,这是删除列表中某个元素的方法。删除链表中某个数据的方法。对吧,哎,可以修改链表中某个数据的方法,那修改的话就叫modify吧,假如说对吧,修改某个元素。这是那个新元素对吧,哎,增删改对吧,你也可以获取某个元素啊。
06:04
对不对。某个元素。返回index吧,下标是不是哎。Int类型啊,Int类型就反我先大概写一下啊,这是查找链表中某个元素的方法。那这些方法你可以都给他实现一下。对吧,哎,都实现一下,我这边呢,就是大概写个架子,各位啊,就是单链表它的数据结构是怎样的呢?就是说链表它的这个结构啊,它最基本单元是什么呢?叫做节点。这个节点呢?它有两个属性,一个是数据,一个是下个节点内存地址,什么意思是这样各位啊。这就是个列表。这是个节点,各位啊。别用这个红色了,用一下黑色吧。
07:00
然后线条粗点,用方框吧,这是个节点,而这个节点可能就是就是我们所说的头节点。几点啊?这个节点当中有两部分组成。明白吗?这就是那个对象。就是no的对象啊,节点node对象,然后呢,这个节点两部分。就这个节点两部分,一部分是数据,一部分是啥呀。啊,是下级的内存地址吧。那么这块的这个数据呢,比如说存一个什么呀,123数据。叫date吧,啊数据。然后呢,他有下个节点,你比如下个节点可能在这儿。在空间存储上它不是连续的啊。这个节点吧。这个节点有没有内存地址啊。有吧,这个节点的内存地址给了谁啊,给这。0X1234。
08:00
而这个00X1234呢。指向了下一个节点对象。啊,不知道大家理解不理解这个这种数据结构啊。那这个节点同样也是一样,前面是什么呀?是有数据有两部分组成嘛,一部分是什么?0X2356啊,这个0X2356是啥呀?是下个节点内存地址。下个阶段可能就跑到这儿了。这是个节点对象啊。这个也是一个节点对象,叫node对象,单向链表。对吧,这个也是一个什么呀,叫no的对象。啊,然后这个NOTE2部分组成都有数据和下个节点内存地址。啊,比如说0X6987,那这个0X2356是谁呢?是是这个节点内存地址。是这个节点对象的内存地址啊。对,然后呢,这个节点两部分组成,这个地址是谁的呀,就是他的呀。他也是个no no的对象。这是个not对象,各位啊,No。
09:03
那么这个节点对象呢,它有两部分组成啊,一部分是存储的数据吧,一部分是内存地址吧,假如说是none,那就代表是末尾节点。如果这是none,就代表末尾节点60X6987呢是指向这个节点的。就是我们单向链表的数据结构,就是这样的一个结构。啊,这个是节点。这是节点。啊。尾巴节点或者末尾节点啊,末尾节点。No。那就这么着吧。末尾极点的特点是next等于空。明白吧,这个节点它不是有下个节点内存地址吗?将来在这不是绑内存地址0X1111,这个内存地址指向一个对象吗?而这个是不是就那个数据啊。就数据把date,假如date来拿过来,拿过来,嗯,拿过来行吧。一个节点有两部分组成,一个是数据,一个是下一个节点的内存地址。
10:04
这是那个节点类型,然后这个链表里边不是有节点吗。链表里边有个头几点?几点?啊,然后接下来你往里边加个元素对吧,你就可以创建个节点加加数据嘛,你等于是往里边加数据嘛,是不是加数据就是创建一个新的节点对象,让之前单链表的末尾。节点的next克斯指向新节点对象,大家好好思考一下,是不是这意思?你往这个链表上加一个数据,你怎么加,加一个数据实际上就是假如说现在这个链表已经成这个德行了,你要加一个数据,无非就是说你要在这个位置上新建一个节点对象,然后让这个位置的这个nu。对吧,变成什么呀。变成这个。对象的内存地址。
11:01
然后你这个对象呢,无非就是说这是那对吧,这是数据让他去指向它呗,就这个意思,不知道大家理解不理解,就是说我们往这个单项链表上加数据的时候是怎么加的,是把。当前列表末尾节点这个呢。改成那个新的。节点对象的内存地址。新的节点对象的是空。这样的话就加上一个元素了吗。就假如说你现在你要加加个几点进去,就是弄到几点吗。对吧,这是一个no的对象。假设这是新增的新末尾节点。那你要加一个元素进去,你得六个对象啊,六个note对象对吧,这个note对象它肯定有内存地址啊。它的内存地址给谁。0X4567。
12:00
把这个对象的内存地址啊附到这儿。然后呢,让它指向谁呀,他。指向它。然后你的数据不就加到这个节点上面了吗。这个节点,它的next是。明白吗?这样的话就加上一个元素了。那如果是删除元素呢,各位。假如说现在我要把这个元素干掉。我要干掉这个元素的话,应该怎么做呀?应该把这个地址。因为这个地址是这个对象的地址吗?把这个地址给了谁?给了他。就原先在这吗?给了他。给了他之后呢,他其实说白了就指向谁了。他就指向他了。
13:01
听懂了吗?它一旦指向它这个这就没了呀。这就没了呀。那这样的话,这个元素是不是就被删掉了。对吧。你看这个链表是这样的,各位啊,就是链表最基本的一个单元,我再说一下是node,一个节点里边有两个属性,一个是存储的数据,一个是下个节点的内存地址。它跟数组不一样,各位啊,数组存储是在空间存储上,它的内存地址是连续的,你有一个数据,然后再来一个数据,这个空间地址都是连续的,你如果是链表的话,它的内存地址不连续,你这个节点也许在这,这个节点跑这儿来,这个节点跑这儿,这个节点跑这儿来跑跑跑这儿了,它内存地址不连续。啊,所以他呢,他在查询的时候效率比较低。你比如说你要找这个节点,那你这个时候得从第一个头几点开始,往后一个一个找,通过它next找到它,通过它再去找到它,通过它再去找到他,通过他再去找到它,对吧?它查询效率比较低,但是它有个优点是它由于空间存储上,它的内存地址不是那种连续的情况,所以你在删除某一个节点的时候效率比较高。
14:15
就你比如删除这个节点,它不需要后续元素位移啊,因为它内存地址不连续啊,所以你只需要把这个节点它里边保存的这个NEX的这个地址付给我们上这个基点,它上一个节点的什么呀?哎,这个位置就行了。就你原先你比如说你这个date里面存的是0X6987,指向的是这个对象对吧,那你把0X6987这个地址,只要给了这个这个这个数据它的next,那这样的话,它自然就会指向这个位置,这个就不指向它,如果你没有去指针去指向这个对象,这个对象会被垃圾回收器回收走,这个对象就没了。它不需要涉及到对象的一个位移问题。所以说链表的优点和缺点是什么呀?链表优点。
15:00
随机增删元素效率较高。因为增删元素不需要涉及到位移,明白吧,因为增删元素不涉及到。大量元素的问题。链表缺点是什么?查询效率较低啊。每一次查找某个元素查找。某个元素的时候。都需要从什么头节点开始往下便利。注意啊。它也有它的优点和缺点。对吧,链表优点,随机增删元素,就是增加一个元素,你比如说现在啊,我想干啥,我想往这增加一个元素,各位。往这增加元素。增加一个元素,那应该是怎么着啊。
16:03
应该是让这个位置保存什么0X4567。4567。那这个0X4567是哪个对象的内存地址啊。是上面这个节点的内存地址对吧。是不是啊?就这个0X4567,这是新加的这个节点吗。对吧,你再随机增加一个元素。这个位置就是你的存的数据啊。对不对,指向它,然后这个位置给它换一下。明白吧,这个对象扭出来可能是0X1111,所以这呢就变成什么呀,0X1111,而0X1111去指向谁呢?去指向了我们这个对象。你明白吗?然后这个呢,就给没了。这样的话就完成元素的新增了。
17:03
元素增加一个,或者是你这个卡删除一个,它都不会涉及到元素位移问题,因为在空间存储上,它的内存地址不连续,随便的这一个节点有可能这一个节点有为这一个节点有可能这点,因为这个节点,这个节点永远都是这个节点里边有一个下一个节点的内存地址。你这个节点对象的内存地址在上一节点这个地方有。这叫单向的,各位你看单向的。是吧,单向链表。啊,它和数组不一样啊,正好是和数组相反的。链表的优点,随机增删元素效率较高,但查询效率较低,因为它在检索的时候,它必须从头挨着往下找,通过这个找到它,通过它找到它,通过它找到它,通过它又找到它,通过它又找到它。但如果增加一个元素,那很简单,新建出来这个节点,然后这个节点的next值。这个位置是吧,然后呢,让这个新建对象内存地址给了他就行了,很简单,只是一个很简单的一个复制操作就完事了。
18:04
啊,增删删除也是删掉的话,这个位置保存内存就指向它下一个就行了,这个位置对象没了。啊,它有优点和缺点,这是优点啊。一的缺点,行,那这个单向列表说到这儿,那如果说我让大家去写一个程序,你自己去把这单列表实现一下,比如这块呢,你定一个note是不是,哎,这有object date,这是一个数据吧,这是不是下一个呀,这个无三构造吧,这是不是有三构造,来这边这个列表,这个列表啊,列表有个投节点呀,投机点你可以不赋值,如果你不给投机点电赋值,默认值就是那。对吧,那接下来我问大家元素你怎么加,咱们可以实现一下这个方法,各位。你把元素加到这个列表上怎么加?有可能怎么着,这个元素是第一个,也可能是第二个,对吧。
19:00
也可能什么呀,是第三个。下一个内存地址,呃,末尾几点下个内存地址是那对对对对对对没问题,头几点的数据能访问到吗。头节点的数据能访问到吗?当然可以啊,为啥不行?你加元素呗,这不是把元素加进去啊,加进去你怎么办呀,你判断一下呗,如果如果要这个hier,要是等于none,这说明啥。这说明什么,各位?说明还没有节点吧,没有节点,你是不是有个节点出来呀。谁啊?什么呀?你有这个note的时候,这个数据是谁,是不是这个数据,因为note里边有两个属性嘛,一个date一个next的吗。是不是好,那这个date拿过来放这呗,Next是不是none啊?这个理解吗?好,这个是不是就是了各位。那呢?
20:04
添加元素吗?对吧,啊,这个元素如果头是空的话,我们是不是就你有一个新的基点作为头节点。说明还没有节点,那就有一个新的节点对象作为头节点嘛。是不是好,那我问大家,现在是不是相当于我们内层已经有头了,但头这个头既是头又是末尾,对吗?这会儿这个头是不是既是头节点,又是末尾节点,这个时候的头节点既是一个头节点。又是一个什么末尾节点吧?因为现在只有一个节点呀,所以它既是头又是尾巴。懂吗?那L呢?L说明啥?各位说明头不是空吧?
21:04
说明头不是空。说明头不是空头,节点已经有了。对吧,头几天已经有了怎么办。各位。头节点有了,你应该找出什么?找出当前什么末尾节点吧。你头几天已经有了,你要找出当前末尾节点,让让什么让当前末尾节点的next。是什么是新节点,就是找啊,假如说现在find last找到了,明白吧,哎,找到了最后那个节点。
22:07
Current last node当前的最后这个节点,它的next等于谁?是吧?哎,各位,这个大家理解吗?李老师,Find last是个啥玩意儿?这是个方法呀,你可以,你可以把he传进去,让他去找啊。是不是你可以有这样一个方法,这个方法是私有的方法,你可以创建出来。这个方法是专门找末尾节点的,这是一个专门什么呀。专门查找什么末尾节点的方法。对吧,你有这个头吗?或者说你你不用,你不用这个头,你不需要传参,其实也可以。不需要传参,其实也可以,因为这个方法是私有的方法嘛,是不是啊。
23:07
这个私有方法在哪呀,在我们这个类当中对不对。在我这里边是不是找找最后一个节点呀。找最后找到最后节点之后拿到这个节点,它最后这个节点的next不等于它吗。这样是不是就相当于把这个元素加到末尾了,向链表中添加元素的方法,向末尾添加,这是向末尾添加啊,你现在你加元素,你这不有有一个有一个数据吗?判断一下,如果头等于空,头要等于空的话怎么办?就扭一个node就作为头就行了,然后L就是头不等于空,头要不等于空的话,你就找出最后一个呀,找到最后一个之后,最后一个的next不就等于它吗?这样不就等于加上去了吗?那你找最后一个,你怎么找啊。啊。
24:10
得派一个探子去找。就这个方法是找找找找节点的,我们用递归行不行。用DV行吗,各位?我说一下啊,这个内容不需要掌握,这是我刚才在这里给大家说呀,说这个单项链表的数据结构,你你你先把这个最基本的掌握了行吗。哎,那掌握了这个基本的结构之后,那么接下来我们在这里就是,哎,咱们也对吧,你可以自己写一写这个读这个单链表是不是,你可以去写一下这玩意,这不链表类吗?这是个列表啊。链表类呀,是不是,那这是节点吧,这是不是链表中的节点啊,节点有两部分组成啊,下一个节点是不是啊,以及它里边存的数据啊,那这个应该不是很难吧。
25:03
对吧,这不是node这头几点啊,你添加元素你不是往里面添加吗?添加的话,你的头要是等于空的话,你就作为头呗,扭出来这个几点就是头节点呗,那else就找出下最后那个几点呗,找出最后几点之后,那最后的几点的next不就等于它吗?对吧,你找节点的话,你找节点你也可以把参数传进去,对吧,你从哪开始找,从头开始找,找从这个节点开始找。也是可以的,对吧,No t对吧,或者叫no对吧,节点找no.next。If啊,如果no.next要是等于等于no,那这个时候是不是就直接返回这个no就行了。程序到这儿的话,我们返回什么呀?返回find last no,点什么next,这能看懂吗?这不找最后那个节点吗?
26:02
是不是啊,最后那个节点它的next等于空,这就是no,是不是就最后那个节点?如果这个节点的next等于空,如果这个节点的next等于空,是不是就代表这个节点就是那个末尾极点?如果一个节点的耐克斯特是,那说明说明nod,说明这个节点就是末尾节点呀。是不是把末尾今天返回就行了,不是find last吗?返回返回node吗?最后一个。是不是啊?那程序如果能到这儿呢。程序能到这说明啥?程序能够到这里说明什么?说明no的不是末尾节点,那我no.next是不是下个节点再传进去调递归?
27:06
Node的next不是一个node吗?就这个节点,它的next是不是一个节点。所以是no.next是不是就取出下个节点内存地址放到这儿继续递归调啊?他一直掉一直掉,直到掉到node点怎么着?它是等于等于空的情况,是不是就返回了。这递归啊,看不懂是吧,递归啊,这是递归。嗯,递归算法啊,这是递归算法,这是找。明白吗?你捋一下头节点是空的时候,你有一个座位头,其他情况头不是空,不是空的话,你可以找出找出末尾节点,然后末尾节点的next等于这个新节点。然后呢,在这你就可以find的呀,找呗递归找呗,如果你no.next等于空的,就把最后一个呗,其他情况你就一直往找找找找找就行了。
28:03
对吧,那这个时候你就你就可以在这写一个测试程序了。你有时间你可以写一下啊,我不要求所有的学生都写啊,你看你情况能写你就写一下。能写就写一下啊来link是不是link一个link出来呀。好,New完之后呢,这个link new完之后大家想想这构造方法是母参的构造,这什么none啊,那这个时候我能不能往里边加元素啊,叫link.I的,我放一个100进去行不行?link.I我再放一个200进去行不行?Link,我在艾再放一个300进去行不行?可以吧,啊,然后那这个时候我能不能在这儿给一个size,给一个size默认值是零,然后呢,我这边能不能提供一个方法叫get size啊,啊不是size就直接叫size啊。Return就行了,行吧,好,那我问大家,如果加加只要是加一个。
29:05
那我size能不能加加呀,在这儿。只要添加方法size加加呗,对吧,好,那这样的话我就可以调size方法呀。是不是,所以这边呢,我添加了三个元素,那我system.out link点你看。几个呀,应该是三个元素吧。是不是三个元素里边存了三个元素啊A。BC对吧,DFXYZ。是不是XYZ,那你这就等于创建了一个集合呀,创建了一个集合对象啊,这个是不是往集合中添加元素啊,加维元素是不是获取元素个数啊,是不是哎,获取元素个数。嗯。
30:00
对吧,你运行一下,你看元素个数是几个呀,三个呗,你加了三个,它就是三个呀。对吧,所以说。只不过这个不需要我们写了,我们链表这种东西不需要我们去做了,明白吗?这个node也不需要我们写了,S公司在JDK的文档里边已经提供了一个东西了。哪个东西啊各位。哪个list下边有个叫什么叫link list是不是。嗯,在哪。在这。Link。对吧,Linked list无餐的有餐的是不是是不是也有size啊你看。有没有方法叫size?返回此列中元素个数吗?对不对啊,这个东西只不过我们这是单向列表,这是单链单链表,单链表这个node有个特点是里边有数据以及next。
31:00
对吧,哎,这样的一个东西。那你可以在这个链表里边再提供方法。再提供方法,你你想想啊,就是打印列列表上的数据。打印列表上的数据。对吧,怎么打印,怎么删除原列表上的数据,怎么修改,怎么去查找列表上的数据。是不是,哎,你可以考虑自己写一写这种单列表。对吧,哎,这个理解吧,大家。就是关于链表这种数据结构,咱先不说这个,这个代表你理解不理解啊,你理解好不理解好,总之这个单链表的数据结构,你理解不就是我都是节点,每个节点有两部分组成,一个是数据,一个是下个节点对象的内存地址。我这个节点它有数据,有下个对象内存地址吗?我这是个节点对吧?有数据有下个对象内存地址,我增加个元素怎么加的,我删除一个元素我怎么删的,是不是它效率为什么高,它的优点是什么呢?缺点是什么对不对?哎,和数组对比着去学啊,对比着去学。啊,行吧,大家吃饭去吧啊。
我来说两句