00:00
下面呢,我们来讲。一下面我们来讲一个另外一个非常重要的这么一个数据结构,我为什么说这个面表这个数据结构很重要呢?因为链表的应用场景很多。应用场景很多,也非常的有价值,你比如说同学们。都接触有一个数语也叫树,我相信很多同学其实没有学过,也听说过树这个结构,比如二叉树里面就有很多特别有用的,比如说二叉这个排序数。平衡二叉树。再比如说霍夫曼树听过吗?霍夫曼数,它是专门可以用来做数据编码的,而且可以用来做压缩。他是做了一个算法的一个基,一个用的比较多的。啊,还有这个多路查询数。等等,那么这个数它在这个底层呢,也是依赖于这种链表的结构的,只是它是把这个链表呢做的更灵活了,能理解这意思吧。所以说链表大家。
01:13
要认真听好不好,那现在的老师呢,就开始讲电表了啊。大家今天要认真听课,那么列表呢?首先我们把这个名词它的英文给大家说一下,叫linked list。啊,你们在学Java的时候呢,也经常听到过这样的东西,比如说orist的对吧,Link list等等,那么底层它是怎么做的呢?我们自己也可以写好,比如说链表,我们先看一个介绍链表,这个链。很好理解。就是链式的,就像一个就像一个链条一样才能拉出去,这个表怎么理解呢?诶,为什么叫链表呢?名字很怪。不就整了一个节点吗?这是因为这个链表,它那个数据结构可以是个节点。
02:02
这个节点里面内容你可以放很多,你想要的任何数据都可以往里放,因为节点就是一个对象了嘛。那既然是一个对象,那这个对象的数据就可以随便你放。所以它那个数据也可以变得很丰富啊,所以说我们把它称之为一种链表,那么链表是一种有序的列表。但是他在内存中的下面啊,但是他在内存的存储,存储方式是这样子的,我们先看一下它的一个基本结构。同学们看链表呢,分为两种链表。从大的来说,第一种链表示。带头带头节点的。一种叫带头节点。带头的。带头节点的这种面表。OK,说老师为什么他要整一个带头节点的呢?待会儿我们会体现出这个写法啊,还有一种呢,就是没有头节点就是不带的。
03:02
那今天我们这两个呢,大家都会接触到。都会接触到,那么我们看这个地方,我这儿有一个图。这个图展现的是带头节点的一个这个链表,那么这个头节点head。它指向比如说它指向这么一个链表的头部,那下面这个链表呢,这个链表一般都是一个节点,这个这个表一般指的就是一个节点,这个节点里面呢,它一定会有数据与就专门放数据的,还有一个就是。Next指向下一个。那就直接下一个,你看这个next指向哪里了,它指向这了。OK。那你看这个1150,它这个这个刚才我就画错了,它应该是准确的指向这了。它这个后面有个13130,它指向哪里的呢?它指向这的。
04:02
这个170指向哪里的呢?指向这个这个哎,大家有没有发现链表它有个特点。它这个地方,它的数据存储空间不一定是连续的。这点很重要,同学们说,老师我这个为什么重要呢?因为我们我们原先学数组的时候,大家知道数组是不是可以说,我们说数组它的一个通过下标可以直接取出对应的第几个元素的值啊。那一般来讲呢,宿主一般来讲,他在内存空间呢,它那个空间是连续的一块。但链表呢,它不一定这就可以,链表就有一个好处,它可以有效的利用这个零碎的。或者碎片的这个空间。理解这意思吧,啊,这是它的一个特点,至少大家要知道,在列表里面,它存储不一定是连续的,这点大家要知道,但是我说的不一定,那也有可能是连续的啊,那假如他刚好。
05:04
在操作系统运行你这段代码的时候,他刚好有一个整块的空间,他刚好够你用,那就直接给你按照这个一个整块给你分配也是有可能的。好,这个至于怎么分配这个next,那是系统的事,我们不用去关心,反正呢,它会形成一个列表,那么现在呢,我简单的结合一个实际案例,我给他说一下链表的价值啊,我就举我工作的一个案例吧。好,我在这个上班的时候,以前我们在工作的时候有这么一个需求。当时我就是用的单链表来实现的,当时需求是什么样子呢?大概是这么一回事,大家听一听,听一听啊听一听,嗯,是这样一回事,就是我当时做的是一个I'm的一个软件。就是即时通信软件,当时用的是什么写的呢?服务器那一块呢,是C和C加加。OK,那么前端呢,是别人别的程序员在写,他用的是din啊,Din号称界面之王,现在呢,大家可能没有听过,听过这个语言了,其实D挺牛逼的,但现在为什么现在德这些做界面的,这些做界面的这些语言现在目录了呢?原因很简单,因为。
06:20
这个网BS太牛逼了,对吧,小程序啊,这个你们都也看到,直接打开一个浏览器啥都有。说做界面的语言就没落了,但但是在我们那个时代,在03年04年做界面是工资很高的,比如用D,有些有些用MFC。啊,有些用那个dolightlight,不是有个win for吗?听过吧?啊win for那做界饼也非常漂亮,那个那个小伙子王长城应该用过是吧,用过用那个win for吧。是不是他一拖拽,然后就做这个很漂亮的效果是吧,还是很不错的,但是后面的这些这个做界面为什么慢慢不行的,就是因为它那个浏览器现在越来越强大了,像H5他这个界面一上去后,基本跟你做的那个CS结构差不多了,甚至功能更强。慢慢做界面的程序员就。
07:09
没落了,好,当时我们用的是这个界面啊界面,我说我的事儿,当时有这么一需求给我了。界面当时给了我一个什么需求呢?他这样子的界面这边有有一个有有很多好友,就是因为是I'm软件,是通讯软件嘛,他有很多好友,比如他有100个好友。100个好友,这100个好友呢,他有编号,它有编号,还有很多其他信息,现在这个好友的信息,他每隔一定时间,它会把这个好友的状态。发给就说我就说每一个人会把他自己的这个状态发给我。大家知道什么意思吗?就是说假设我有100个100万个人在线,100万人在线呢,他发给我,假设我有一百一百万个好好友在好100万个这个用户在线,他每隔十秒钟向我服务器汇报他的状态。
08:06
好,汇报完了过后呢,这边我我要给了我一个任务,要做一件什么事情呢?不能入库,就这个状态不要入库。不许不能入库,什么叫不能入库呢?就说你这个信息不能把它打到这个MYSQL里面去,为什么不能打进去呢。为什么不能入库呢?因为一旦入库,这个速度就会变得很慢,而且用户的状态瞬息万变,每隔十秒都要变,你如果每来一个都入库,这个这个服务器直接就瘫痪了。当时所以说给的任务是不允许入库,直接在内存里面做一些什么事情呢?在内存里面做做一做两件事情,第一件事情接收。他要接收接收大家听一下就行了,我不做这个,不做笔记啊,接收所有用户的这些信息,第二个。写一个算法。把张三的好友。
09:01
比如说张三,他有很多好友,把张三的好友的状态形成一个列表。给他返回去,而且是要有序的。比如说张三他有十个好友,那么十个好友呢,因为张三他是不知道他好友的状态的,所以说需要福气把他好友放回回复给张三,张三才知道客户端才会去更新张三好友的状态,是离线了还是在线。那这个时候呢,我再给他返给这个客户端,返回这个信息的时候要求是有序的,而且不能入库。这就比较麻烦了,那当时我就想到,哎,如果我有一个办法是什么呢。我。在返回的时候,我就直接把接收到的这个用户。用一个链表形式管理起来,然后呢,来一个我插一个,来一个插一个,来一个插一个,等到我要返回的时候,我只要遍历这个链表。形成一个差面文件啪了,返回去就完事了。
10:01
诶,这个问题得到解决了,那当时幸亏我还用了这我会这个数据结构,不然的话这个对我来说就比较难了,而且你很难给。你的同跟你的朋友去交流,说这个需求是什么,人家没法帮你,哎,我做完了过后还得到了表扬啊,真的是得到表扬,我当时感觉很高兴。在写完了过后,当时。当时我的这个领导呢,我的领导不是以前跟你们说过吗?他是那个新浪的第一任CTO啊,还是很厉害的一个。技术很牛的,他喜欢,哎,他说这个他们在聊天的时候我就听到了,说也不知道那哥们怎么整的,把这个东西返回来了啊,我确实也没入库啊,他他也是觉得还是比较厉害的,就说这个地方就你要会一点数据结构就能解决,但是如果你一点数据结构没有,这个问题不好解决的。啊,不好解决,好,这是一个应用场景,还有一个呢,同学们再看一个应用场景,我就直接拿出来,待会我们要用的一个东西了啊,比如说我们来写一个约瑟夫问题,这个约瑟夫问题呢,也是一个经典的用链表来解决的一个。
11:12
最佳时间,你比如说我现在有N个人围成一圈。那么围成一圈以后呢?我约定从编号为K的这个人开始报数。啊报数,就说我有N个人,然后呢,从第K个人开始数,数数几个呢,数M个,然后把这个数到M的这个人。把它出圈问。问。这个出圈的就是产生一个出队列的编号序列,把这个出队列的顺序给我打出来,最后问谁留在这个圈里面。大家想这种其实是特别适合用链表来实现,那么我们今天就会把这个链表。学完了过后,我们把这个问题给他解决了,再比如说我们的环双向这个链表,这个双向链表呢,也非常有用,它可以提高我们这个链表的一个什么呢?删除的速度。
12:11
同样大家也应该也听过,我们在学这个,比如说后面同学们在学这个二叉树的时候,也会利用到这些一些一些比较特别的这个二叉树,这个二叉素呢,可以前它负负节点可以指向子节点,子节点还可以反向指向负节点,就会用到这个双向链表。好,这是这是老师呢,说了一些,说了一些这个应用场景,这个就说完了,下边呢,我们就准备给大家来实实在在的写案例了,好,我先把刚才这一部分截取一段。
我来说两句