350_尚硅谷_Go核心编程_数据结构和算法-单链表的基本介绍.avi原创

好，同学们，我们来看一下，那上午呢，我们给大家讲了一下，用数组来模拟一个环形的队列啊这个呢，呃，同学们肯定也会去看到一些其他的不同的方式哈，那不管怎么样，它的核心的思想呢，都是一样，就是说核心思想就是什么呢？就是说他能够在我们的这一个，就是我们这个指针，或者说标识我们这个元素的那个。下标呢，它在到达对尾的时候，它可以通过取模的方式又重新回到咱们的这个数组的前面，这是它核心思想，好好，下面呢，我们来看另外一种数据结构，这个数据结构呢，的确是非常有用的，我为什么说这个数据结构呢更有用呢，或者说更有意思呢？因为这个链表啊，它可以实现前面的队列。它还可以实现，在大家还记不记得我们在前面讲RA的时候，曾经有一个有一个那个结构，就数据结构叫list，那个list呢，它底层可以用数组实现，也可以用链表实现啊链表它这个就很灵活了，这个数据结构可以做很多好玩的东西，好玩的东西出来，好，那么来看看列表是什么，同学们看，列表是有序的一个列表。

啊，它在内存中的存储是这样子的啊内存比如说诶这有个投子帧，有这个投子针呢，诶它这有个投子针，它指向了后面的各个节点，节点之间呢，是可以这样互相指向，比如下一个领域，我指向它A。这个领域只要103。A指向这对，然后呢，103又指向哪里呢？这是它的地址，诶指向1107对这样子的。当然了，对于我们来说，你感觉好像它这个并不是完全连续的，这个很正常，因为地址的分布，它下面这个地址的分布其实还是由系统来决定的，对不对啊，这个并不影响我们，因为在我们来看，我们认为它都是有的，他认为都是一个有序的就行了啊，比如说110指到下一个，待会儿呢，我们来画一下这个图啊来，这是它的一个基本的一个说明。

那么我们来看一个单链表的一个结构，单链表带头节点的这么一个结构，你比如说吧，这是一个high的节点，它先指向一个头节点，头节点里面有一个字段，这个字段呢，又指向另外一个节点，另外一个节点里面呢，又有一个字段，它又指向另外节点，我画一个示意图，你比如说最经典的案例，它是这样子的啊，打个比方，我们这有一个头节点。He的节点。有害的。那么这个he呢，它指向了一个头节点。啊，比如说这是我们的一个节点啊，同学们，这是个节点，但这个节点里面是什么内容，我们可以随意，比如说是一个人吧，Person，这个person呢，我们假设它有个字段是名字叫汤姆，另外呢，它有一个，它有一个域叫next，这个next next呢，又是它是一个什么类型呢？我们姑且认为它是一个这样的类型，Person。

好，假定，假定我们这个节点，它的结构体是长这个样子的啊，同学们，假定它是这样一个结构体，Structure。什么呢？哎，这样子的type person。一个structure里面呢，有这样一个东西。首先有它自己的信息，比如说人的名字，比如name寸，另外一个最重要的地方呢，就是next指针，他又指向什么呢？它的类型是person。好，如果说我有我有这么一个人，这么一个节点，那么到时候我可以这样来玩。怎么样，我这有一个汤姆。

好，我还有一个节点，我还有个节点叫什么呢？叫Jack。Jackie。好，假设我还有一个节点叫什么呢？叫做这个SC。诶，有这么一个节点是靠的，那么我如果用链表来管理，我可以怎么管理呢？诶同学们可以看到我可以这样管理，我先来一个投节点，这个投节点没有具体的数据。就他专门用来做头节点而已。那这里面的这个内容呢，呃，它可以不不不给任何东西，然后到时间形成这么一个结构，怎么一个结构呢？大家看到它的头节点指向这个地方。好，然后呢，下边这个地方继续指向它的下一个节点指向它。对，下一个节点又指向汤姆，汤姆呢？汤姆的下一个节点又向Jack Jack又怎么样呢？Jack又指向Scott。诶，这样子呢，它就形成了一个链表的结构。

那有些同学可能就要问了，说老师，那这个链表它形成的意义有什么用呢？大家可以想象，在我们现实的这个边，在我们现实生活中就会存在这样类似的这种结构，你比如说。一圈小朋友围成一圈丢手帕，哎，我就可以形成一个环状的，怎么样形成一个环状？这个地方，我让他再重新回来，指向它。不要再重新指向这个头节点。你看这样子就是一个就是一个，就是就是一个环状，那如果说我不想做环状，我不想做环状，环状的这个链表，它本身其实看起来也像是一个队列。也就说它可以又可以当成一个队列来使用，它可以当队列来使用，更有意思的是，它可以在我们的这个内存里面形成一些非常有用的结构，比如比如说哈希。比如说哈西，你比如说这个地方是有一组人，那我将来假设有多组人，我可以这样干呀，哎，你这是一组吧，可以没问题，你是一组，然后呢，我还有一组。

大家看到我还有一组。诶，来，我又有一组。这有11组人，这有一组人，你是不是还不够好？假设你还有一组。好，我又一组人。那么我可以让这么多主人形成一个什么呢？形成一个哈希啊，到时间我在这方找找某一组人的时候，我也我通过一个里面有另外一个一个结构，比如说我这外面还有一层这个结构。对，我可以很轻松的通过这个节点来找到我的哪一组人，比如说到时我可以让他，让他这里面有个节点，指向他这边，这边的一个头节点。对，然后呢，我还可以让这里这个数组里面的又一个地方指向另外一个头颈，让它跟这一组发生关系等等等等，所以说这个呢，还是非常有用的啊，非常有用。好，这是它的一个示意图，那么我这个图呢，画的有一点点不准确，这个图如果在Java或者C加加里面呢，它是一个很精准的图，但是放在我们go里面呢，有一点不准确，我说一下是哪里不准确啊，来朋友们。

我先把这个不要的先删掉。我这样画的哪一点不准确呢？就是因为我们我们都非常清楚的知道，在构元里面这个结构体啊，它本身是一个直类型。它本身是个直立体，所以说这个next呢，它这个指针准确的讲，它并没有直接指向这个结构体，它应该准确的话应该是这样画，但是呢，我后面在画图的时候，我可能就就按我这个画法了啊，他准确的讲应该是这么画，听我说。它准确的讲是这样，这样画才是合理的，就是你这个地方有个下一个节点，这个下一个节点呢，其实它指向的是直接指向的是一个地址。它其实是指向一个地址，对不对，再由这个地址。

再有这个地址指向我们这个这个这个这个汤姆真正的这个结构体。是吧，因为我们以前讲过嘛，我们以前讲过它是指针的话，是先指向个地址，再有一个地址指向真正的结构体，那也就是说这边呢，也标准的画法也应该是这样画。但是这个不影响啊，同学们这个不影响，就说就说我把这个撤回去。啊，Y的周易，也就是说它应该这本身是个地址，比如说0X0X，呃比一一好，它指向这个汤姆，然后这边呢，也是一样的，它也是先指向一个地址。啊，比如说他这指向一个地址。我把这个画过来啊，同学们。诶，这个怎么拖不过来哈。好，把它挪到这来，对，挪到这儿来同样。这边后面这个呢，也是一样的啊，也是一样的。啊，但是每个地址可能不一样，这个可能是假设是幺五吧。

哎，药物有它这方是指向它，然后由这个节点再指向这个，呃，真正的结构体下面这个也是一样啊，比如说这是二零。那么你这个JT的下个节点呢，本身是先指向那个地址，有这个地址呢，再指向我们真正的这个结构体的一个，呃，内存空间它应该是这样画的，但这样画呢，有时候我画图啊，这样画画的很很麻烦，看起来不舒服，所以说我在讲课的时候呢，我可能把中间这个地址我就不画了，大家理解一下啊好，嗯，这个就是我们一个链表的一个最基本的结构。那么我们就来完成对这个链表的增删改查。啊，通过这个练习呢，我们就能知道链表它是怎么怎么用的，你可以这样理解，你可以这样理解，这句话我觉得还是比较到位的，你可以这样理解，就说我们可以利用链表来做一个自己的属于自己的内存数据库。啊，这样就非常的经典了，这句话就是有些时候我们我们往往把数据是直接放在哪里的，各位同学，我们放在数据库里面的没问题，但是这是人家的东西。

这是人家东西，但是有些时候呢，你想自己去存放一个数据量比较大的。这种数据。数据量比较大，而且呢，你还要让它具有很好的扩展性，比如说你还对你你在内存里面存放数据，有增删改查的功能，这个时候链表加上这个哈希。就是链表，配合哈希的这种算法就是非常不错的一种结构。所以这这个就是为什么后边我再给大家讲的时候，有一个散裂散裂散裂加上这个散列啊散裂它本质就是一个哈希，然后呢，配合我们链表，这个就相当于说你自己可以做一个小小的内存的数据的一个管理的一个机制。这就上档次了，明白吧，说老师，诶那意是不是有的同学说老师，那是不是意味着我们将来自己想去搞一点这个，这个数据，我们自己在内存里面把它维护起来，有增删改查的功能，是不是就可以了，就是这个意思，做链表这个必须学会啊，看起来它它虽然不是很难，但是它很有用，它很有用啊，反正以前我在工作中，说实话，队列我还用的比较少。

但是真正用到的链表还是还是不错的，还是个好东西啊，好东西很好啊，后面呢，我们还要把它进行一个扩展啊，好的，那基本的介绍呢，老师就先说到这里了，来把它进行一个板书，进行一个板书，然后呢，我们就来玩一把。好的。好，链表的一个基本介绍，对老师讲了什么东西呢，链表啊。链表，OK，那现在呢，我们给它来一个标题三。啊，那表。啊，这个不是这个标题二啊，因为它是属于一个新的一个数据结构，那刚才呢，我们讲了链表的基本介绍。那么我们说一下列表是什么呢？诶，别人问到起，也就是说链表是一个有序的列表啊，有序的列表它在内存中的存储呢，可能不是连续的啊，就是但是在形式上体现出来，它肯定必须是一个有序的。

也也就是说，诶，也就是这句话，这个图怎么理解呢？就是我这画了这个图，我这画了一个这个图的，怎么去理解它同学们。好，就是说，呃，这个图怎么理解呢？就就还是拿这个说事，就是将来有可能这个地址它不是连续的，就说可能这个东西啊，它它它是肯定指向汤姆的，但是这个地址不是说幺幺过者是幺五，它可能是另外一个地方，它引用过序的，但是从这个形，从这个形式上来说，肯定是个有序的啊，肯定是个有序的。好，那么我把这个拿到这里，接着我们来再看一个单链表啊，单链表来走一个。那单链表呢，我们待单链表就是老师画的这个呢就更好一点，我直接把我的单链表的这个东西拿过来，单链表一般来讲会带一个表头啊，就是说会比较容易一点，我说一下啊同学们单链表单链表。

单链单链表的这个它的一个示意图先拿过来，然后呢，我做一点说明。一般单链表都会带一个表头。啊啊说明一下说明一般来讲，一般来说为了比较容易控制这个链表啊，一般来讲为了比较容易控制这个链表，一般都有个表头，这是肯定的啊，一般来说来说，为了比较比较好的比较好的对单链表单链表。链表。链表进行什么呢？增删改查，增删改查的操作，哎，改查的操作，改查的操作，那么我们都会给他来一个投节点。操作。操作我们都会都会给他给他设置，设置一个头节点，那么这个头节点是什么玩意儿呢？头节点它主要是用来表示它是链表的头。

它本身并不存放数据，注意听这句话啊，那头节点的作用。头节点。头节点的价值或者作用主要是主要是用来标识啊，用来标识什么呢？标识。他标识或者是标志啊，标标识标识这个链表的头。链表的头这个是不能动的啊，这个不能动，一旦头没有了，那你整个就完全找不到了。你头都没有了，你肯定没办法下手了啊，用来标识的链表头，好，这这点大家注意一下就可以了，但是它本身一般不存放数据啊，本身这个节点，本身这个节点，节点不存放，不存放是不是数据，OK，好示意图呢，我给同学们拿过来。

示意图，OK同学，那就不说了，这个写完过后我们就直接正常改查。这是一个头节点，哎，这个把上面这个也拿过来啊，把上面这个拿走。你看我在投节点，我就没放东西啊，空着空着就空着。好了，这是我们单链表的一个基本介绍，下边呢，我们就来做一个应用实例。