00:00
同学们,我们下面为大家讲解链表这样一种数据结构。那首先呢,我们先来对链表做一个基本的介绍,先看一张图。先看一张图,链表呢,它用英文来说的话是linked list。啊,这是它的英文名称,那么列表首先呢,仍然是有序列表,这在前面我们已然给大家讲过了,对吧?那么他在内存中存储的方式呢,是这样子的,大家有没有注意观察到。年表呢?有,有一种是带头节点的链表,有一种是不带头节点的链表。呃,这个呢,呃,有没有投节点,根据你实际的需求来确定,我们看一下链表它有几个特点。第一点呢,链表呢,它一个节点,大家看到这个就是称之为一个节点,就是大家看到这个看是一个节点,一个节点里面呢,它分为data域,就是放数据的域,还有一个是next域,这个next域呢,就是指向它的下一个节点。
01:07
大家有没有看到它的头节点,这个150实际上是指向。这个节点的。A1这个节点,而A1这个节点后面A1当然就是它的数据了,而后面有一个next域,这个next域呢?110,它实际上是指向了哪里呢?指向的这个位置。大家有没有注意观察到,而这个A2,它的next域是180,这个180指向哪里的呢?大家注意观察,它指向的是。这个位置。同学们,通过这个小的图片,大家有没有发现它的特点?它的特点是什么呀?它的特点是。它是一个链式存储,也就是说它的每一个节点并并不一定是连续存储的,这点大家要注意好,待会儿呢,我们做一个小结,大家看通过这边图呢,我们来做做几个小结啊,小结一把。
02:07
小结一把,第一点呢,我们可以看到就是。就是链表。链表是以是以节点的点的方式方式啊,我们就叫这样叫方式来存储的。来存储的。那么每个节点呢,必须包括每个节点包含。包含什么呢?Data域就是域,这个data域是用来干什么呢?就是纯数据的,还有一个叫做next域。这个next域是干什么呢?这个语是指向,指向我们叫这样写啊,叫指向。指向下一个节点。下一个节点的。OK,没有问题吧,就是它是指向下一个节点,而且通过这个图啊,如图我们发现它有个特点,如图我们发现什么呢?发现。
03:06
我们发现这个节点呢,就是链表的,链表的各个节点,各个节点不一定不一定是连续。连续存放的,也就是说他在内存里面呢,比如说这个A1 a一下面的下面的这个节点并不一定就立即在110的这个内存地址的下一个位置。你看它这个A1,它是110是吧?哦,你看你看A1本身是150,但是它的下一个节点到110去了,它是有跳跃的。这个就叫。不一定是连续存放,或者叫连续存储。都可以,希望大家把这几个点搞清楚好吧,别别把这个搞蒙圈了,搞蒙圈了好,那么链表的基本结构就这样子的,而且呢,我在这儿加一句啊链表呢,链表分分什么呢?带头节点的头节点的这个节点啊节点的链表。
04:11
和没有没有头节点的。头节点的链表,这个呢,根据什么呀?根据实际的,实际的需求,就是根据你的需求来确定。好,这是老师总结了四点,那么链表我这儿呢,有一个工作的案例给大家分享一下。就以前呢,老师在参加工作的时候呢。有这样一个需求啊,当时带我的这个领导呢,他是新浪的第一任CTO啊,技术非常的牛,他当时有这么一个需求,因为我当时呢,是在做服务器,他当时呢。他是在写客户端,他写客户端我写的是server服务器。当时呢,我们要做一个两个,嗯,就是要要去管理在线的用户。
05:03
他有一个需求,他说我每隔一定时间把某个某某个人的好友发给服务器,但是这个好友的ID号呢,并不是连续的。他要求我在服务器这边把所有的好友信息按照编号。按照编号的顺序给他返回来。因为。服务器端这个客户端呢,要定时的向服务器去询问他好友的状态。而我这边呢,呃,需要把他发过来的好友按照顺序来返回,比如说客户端发过来的他的好友编号是21 19 38。然后呢是五,比如他发了某一个人的好友,有21 19 38和五号,他发给我以后呢,要求我把这几个人的状态返回来,但是他要求。
06:02
五要求返回的时候,这个顺序是按照大小顺序的,比一,五,然后下一个是19,再下一个是20,再下一个是38。他要求我按这个顺序给他返回,而且不允许查数据库。啊,就在内存里面,就要把这个事情做完。你不能说我把这些数据先把它保存到数据库里面去,然后呢,通过这个order by来给他返回,不允许,因为他要求时时间和这个速度,所以说我当时就想了一个什么呢,当时想的就是链表。我拿到一个ID号过后,我按顺序插入到这个单项列表里面去,这个问题就给他解决了。如果我当时没有学这个念表的话,这个需求我是很难搞定的,所以当时我做完了过后呢,哎,这个领导还很欣赏的样子,对吧?哎,这个小韩干的不错,那也就是说我们在实际开发的时候呢,的确是能够用到单链表的。
07:01
只是呢,有些同学现在还没有做这方面的工作,感受不到这种链表的威力,而且链表呢,也是我们学术这种结构,学图这种结构的一个基础,同学们一定要认真听好了,那么我们再来看看另外一张图,这张图呢,是展示了一个带头节点的一个链表的逻辑结构,注意听,这是逻辑结构啊,刚才这个呢,其实是它的一个在内存里面的一个实际结构。可以看成是从这个实际结构看出来呢,我们发现它的每一个节点,它的各个节点不一定是连续存储的,但是我们这画的另外一个逻辑结构,这个图呢,看起来好像是连续存储的,但实际上不是啊。你看我们在。在做这个开发的时候,在做分析的时候呢,往往是这样画做一个头节点,这个是头节点啊,大家看这是头节点,它指向A1 a1指向A2 a2指向A3,依此类推,最后这个节点的下一个next域呢是空。
08:04
就代表我们这个链表结束了。列变就,那么你从这个图看起来好像A1后面就是A2 a2后面就是A3,意思类推,但我刚才讲过了,这只是逻辑结构,他之所以这样话是因为它的下一个域刚好是指向A2的,但实际上在在内存里面呢,A1后面并不一定马上存的是A2,它只是通过一个指针指向了另外一个地址,把它连成了一个单链表,看起来好像是一个有序,看起来好像是连续的,实际上真实的存储是。真实的存储是这样子的。看到没有A1,按理说A下面下面就应该是2A2,那应该在这个位置对吧,但实际上不是A1到哪去呢?啪,走到上面去。A222下面有个180指哪去呢?噌的一下跑这来了,显然这不是连续的,明白这个才是它的一个内存中的布局图,理解啊,一定要理解,所以说它是链表,是以节点方式来存储的啊,从这呢是链式存储。
09:05
哦,是临时存储。练试。链式存储。好了,呃,那同学们关于这个链表的基本介绍呢,我们就先讲到这,我我们就先讲到这个位置啊讲到这儿好,我们截取一段视频。
我来说两句