352_尚硅谷_Go核心编程_数据结构和算法-单链表有序插入.avi原创

刚才呢，我们给大家介绍了一下，就是呃什么呢，就是单节点的一个显示和插入，但是这个插入呢，有一点问题，有一点什么问题呢？大家可以看看它的问题在什么地方，比如说现在呢，我有一号和二号，OK，那么我假设还有一个英雄人物，对，还有一个英雄人物是三号。三号，假设这个三号呢，是林冲，各位是林冲。林冲，OK，他呢，这个三号人物，呃，他是什么呢？豹子头。好报纸头，假设我在添加的时候啊，同学们注意看，我如果是按照顺序添加的呢，它将来在显示的时候，诶，它的的确确就是按照123给我们进行这个排序的。哎，他确实是按照123排序，就说第一名是宋江同学，第二个如第三个零，但是如果我在添加的时候，我不小心写成了这个，而且呢，的确有这样一个情况，就是说假设有些数据是临时产生的，哎，是临时产生的，比如说你将来在这个实际开发中，对方给了你一个节点，这个节点的编号在传递的时候，他不是按照这个从小到大的顺序给你，给你传过来的。

但是呢，他就要求你按照链表要形成一个顺序来排列，那就麻烦了，你看比如说我这先插了一个HERO3。OK，那么我加了一二，那这个时候我们可以看到我们打印出来这个数组呢，呃，打印这个列表呢，你会看到是什么呀，是三排在第一名的。一反而排在第二名，那这就不对了，那有时候我们就是有这个要求，就是要求必须在添加的时候，就按照这个顺序给我排。也就是说你如果先添加了三，那么一和二就应该插入到中间去，这个怎么做？

所以说我们要对这个插入的方法呢，进行一个改进，那改进的时候呢，同学们我不动原先的代码，我不动原先代码，我单独的再写一份insert hero load节点，大家看啊来，我们这次呢，换一个套路。就说根据什么呢？我们啊，就是list啊做错了，我们找到这个here inside，我们这个时候呢，来重新写一份新的插入方法，要求必须按照。英雄的编号从小到大的方式插入来稍有一点。第二种方式。在单链表不是在单量最后了，要根据什么呢。要根据，诶根据。根据根据什么呢，这个。Hero的就是那个no的这个编号编号编号从小到大排序，就是的排前边啊，从小到大到大进行插入，这个呢是一个非常经典的一个案例啊呃，以前我们这个这个在开发中就有这个要求啊，幸好呢，我还会一点这个东西，不然的话就蔫点菜了，你要说到不走不行，走数据库，你不能这么干诶，我放到数据库里面先放一下，然后order by，黄花菜都凉了对吧，不允许order by，就你先放到数据库先先浪费了三条数据，然后再查回来还order by又是三条数据。

而且你想一想，你这个服务器喽，你服务器呃，假设10万个人来，那10万乘以一个六。多少条连接过去了，10万乘以六，就60万个映ER的语句，你附近扛得住吗？如果我们走内存的话，60万条数据，60万条circle全部没有了，那开玩笑呢，对不对？肯定效率高啊，肯定效率高，那说老师老师不是配内存了吗？现在还谁还在乎内存了，有的是啊，现在有的是内存啊，内存不值钱了，现在现在内存不值钱啊，随便买，呃，以前我们那个呃2G那个计算机刚刚出来的时候，内存很值钱，现在不值钱了啊，几几几G的啊，15个G一个G的内存，几个GG的内存也花不了几个钱，对吧？好，所以说公司还这点钱还是出得起的，那么搞一下走二，那这个时候呢，我们根据它的编号排序，还是老规矩，这个就不是找到链表，最后这个节点了，而是要找到适当的节点，要找到什么，找到。

要找到适当的。适当的。哎，适当的这个节点节点的位置，那么我们还是搞一个跑龙套的，还是他普他不是一个好好人，但是这种插法就不行了，哎，那么我们怎么办呢。我们这么玩。好，这个地方我们就就要全部的重新来一遍了啊，那你想一想，什么时候才能找到这个适当的节点呢？

什么时候才能找到这个适当节点呢？来看一下这个示意图，同学们可能想象空间就会有点问题了啊，大家看，假设宋江是呃呃，比如说这样子吧，宋江是一号，卢俊义，假设他的编号是假设啊，他是四号。现在现在我要插入一个节点，它的编号是二号，大家想想这个怎么加。假设呢，现在我要插入的一个节点是二号，他正等待你的，你他正等待你，你要找一个位置，大家想怎么做呢？非常简单，假设呢，这个是个三号的，呃，二号的节点来了，我就这样子让让这个temp，因为temp呢，它始终是在。4TEMP有一个特别核心的作用啊，就一定要让temp去找到它下一个节点，跟他比对。你才能加的进去。说，老师你在说什么都听不懂。嗯。说你是说什么呢？因为如果我我不让temp，我不通过temp找下一个节点的话，我即使找到找到这个点我都没有机会加进去了。

大家知道为什么吗？比比如说啊，打个比方说儿子，你你让这个temp去找你，你你让这个temp不停的移动吧，移动到宋江，哎，你发现这个二。比一要什么样呢？比2:1呃要大，所以说这个不能不能不能确定，然后呢，你又比较哦，你看卢俊义还卢俊义呢，是四号，他比你大，而且他原先一直保持是一个有序的嘛，所以说老师我知道了，应该插入到卢俊义的前面。你还有机会查？你的节点你跑这屁股后边来了，你想把它插在前面去，那不是搞笑吗？所以说你一定要在哪一个位置就知道呢，一定要在宋江这个位置，就是你在进行这个比对的时候，你一定要在宋江这个位置就知道，他就应该插到宋江的后面，这样就好办了，我让宋江的节点指向他，让他节点指向他就插进去，明白吧。

说老师还是不明白，不明白怎么写代码，就是说一定要让这个temp的价值在这凸显出来了啊，那你看我的代码开始这样写。让我我的思想是这样子啊，我的思想是让temp的下一个让什么呢？让插入的，插入的节点的这个no no和temp的。Temp遵循这句话，Temp的下一个节点的节点的no进行比较。的能够进行比较，比较。那怎么怎么比较呢，比较啊，那你看我代码中间写了来了。好，来，如果几种可能性啊，同学们看这个代码有点不是那么容易看懂了啊。啊，但是如果你有基础的话，同学呢，可能还是看得懂，我先写一句话，如果ten.next等于near。

这个说明。已经到屁股后边了，就是他现在已经已经找到哪儿去了，找到最后那个了，就是就已经到这个链表的最后了，这个说明到链表最后了。说明到。到链表的，链表的最后能理解哈，那如果到列表最后你还玩啥break。啊对对对对对对对对，同学们，等于啊，说明到那就break了，就说明不能再走了，再走就就跳悬崖里边去了，那么还有一种可能性就是else if，那else if我这样写temp.next的点no，它的这个值大于了。大于了，你的这个new就是你的那个新的节点的no，哎，各位同学，如果一旦这个条件成立。一旦这个条件成立，就说明我们这个new这个节点刚好就应该插在ten的皮革后边。

大家看能不能理解这句话，就说如果这个条件成立，说明。说明什么呢？啊，说明这个temp，注意听啊，说明这个这个就是new new这个hero new这个hero就应该就就应该。应该插入到这个temp的后面。后面。对。就应该插到后面了，因为你你你你一直是按这样插的嘛，就整个勾顺序，它总是一个有序的，所以说你放心，你只要沿着按照这个每一个都要插，它每插入一个它都是一个有序的，所以说这个呢也可以break。相当于说我找到位置了。我找到了，还有一种可能性，哎，就说老师，那有一种可能性呢，就是他们如果都相等怎么办呢？如果两个都相等，我们认为这是错的，因为我们知道英雄排行呢，不能说你是老大，我还是老大，对吧，比如说差了一个编号唯一的宋江，你说诶卢俊义也是编号唯一，我们就认为其实他已经有这个ID号了，假设我们认为ID是唯一的。

但如果说有些说是如果ID不不唯一也可以的话，那你把上面这个呢，打成这个等号就行了。对，那相当于说没如果相等的，我也把它加进去，就这么一点点改的好，就看你的要求啊，假设这两个相等，我们就认为提示一句话说，呃，对不起，不不允许插入啊，这样就说说明呢，说明我们的链表中。链表中已经已经有这个ID了，有这个no就不让插入，就不让插入，这是我的一个业务逻辑啊，说老师假设我不想这个业务逻辑，我认为相同的编号，假设人家有一个要求，说假设有相同的编号也可以加进去，那你把上面这个这个地方呢，写成等号就行啊，那马上就可以加进去，其他同学新来的编号总在前面也可以啊，就看你的需求好，那现在这个逻辑有了过后呢，同学们这个也应该是break。

就说只要有一个条件成立。我们就认为这个位置找到了。有一个未知条件，对好，那么这边有个问题，就是这个情况，这个情况是一种不不不插入的情况，所以说我加一个标识符。我给他来一个什么呢，我就认为它默认是可以加进去的。因为添加的可能性肯定是更大的嘛，说如果说一旦这个条件进到这儿了，我们认为就不让加了，不让加我就把这个标识服务改成一个force。就代表说，哎，对不起，你这个插入你这个节点有问题啊，我们就提示个信息，那开始这样说了啊，如果flag等于false，也就说这个条件成立，我们就认为就给他提示一句话说对不起，已经有这个英雄的排号排名了，你就重新来做啊，就是对不起，对不起。

啊，对。对不起，对不起，已经存在存在这个英雄的存在这个no了，把这个no你可以打出来看一下。这个no已经有了，这个no不就是你从这个new load里面取出来的吗？点no完事啊，输出来就可以了。好，这个地方就做完了，过后就这就我就就就不玩了啊，直接可以。不玩了，Re t，那么else条件A。那么A是什么意思呢？就说诶，它真的要加添加，那真的要添加的话，就是在这个temp后面。但是有些同学老师这个这个这不等于next等于空，什么意思，就说明你整个条件一直都没满足，最后到最后就整个列表全部都看完了，就发现。

没有没有这个，那就说明你这个下的这个节点太大了，刚好应该插入到屁股后边去。哦，去后边去，那这样就很好加进去吗？这个怎么加进去呢？好同学们看现在怎么让这个假设是二这个节点要加到松江这方，应该怎么加。首先各位同学啊，你这个因为是单链表，还比较简单。它比较简单，你也可以这样做。哎，各位同学看一下啊，如果我先让他那这个宋江这个下节点先指向他，完蛋，我们这个链表就断掉了。我们这面推，因为你一旦让这个宋教下给指向他，他又不知道卢俊玉是谁，就完蛋了。这列表就断掉了，你应该这样做啊，注意这个顺序先。先怎么办？先让这个这个二这个节点指向这个卢俊义。那有些同学为什么这样可以呢？因为你这个temp刚好在这，大家看你的temp刚好指向宋江的说temp的点next就是溶金液，所以说先把这根线连起来。

这根线连起来，那这个这个线好连吗？非常的好连，就是new no.next等于temp.next。那如果你X最后呢，就相当于白做了一次，也无所谓，那么仅这条线这这个动作就是让哪根线连起来，就是让这根线连起来，就是这根线啊，注意注意听讲啊，然后下一个呢，就让这根线再重新指向我们的这个。指向我们的这个线，好，那先说宋江，它进去两个就是一个连接，只是我没画到一小线而已。那这这根线又怎么写呢？非常简单，那就应该是我们的这个temp.next等于new no，注意这个顺序绝对不能颠倒。颠倒就完蛋。颠倒就完蛋，你颠倒你想一想，因为你让NEX先指向它的话，那NEX一旦指向它，它下面那个节点你就找到了。

你就找不到了啊，同学们好，这个就完事了，已经。搞定了，说老师你这没有写什么好听就搞定了呢，就这样就可以搞定了啊，来玩一把。看代码有没有问题，好，这边有点小问题啊，他说new node没有定义啊，是在这个地方。你用he啊，没问题，我把它改一下。好，这个地方带进去就可以了，保存。那保存过后呢，我们现在把这个插入的方式做一个调整，换成二。好同学们，当我换成二过后，你会突然发现柳暗花明又一寸，就说这个时候你不管怎么添加啊，你先添加三，添加一添加二，它永远是一个有序的，那看看是不是样子的周。跑起来，来看效果。OK。我们可以看到，我们可以看到。

哎，死死机了吗，难道。我负循环是不是有问题？可能死在这了，我们看for循环哪个地方有问题，在找的时候是不是少了一个动作。非常正确啊，我这看到没有，我这少了一个往下走的动作。你没往下走，它不是卡在这地方就数不来，是这地方少了一个动作啊，因为你这个地方还得往下走一下才能进行下一个的判断，对，说的很对，好的，他报的错误是正确的啊。来，重新来走。好，这个时候我们看效果。好，同学们看，这就正确了，你看宋江排到第一了，卢俊义排第二，林冲排第三，完全正确，跟我们想的是一样的，不管你怎么添加，它都是一个有序的了啊，那你如果我反过来啊，说老师我想从大到小呢，非常的简单，把这个改一下，只要把这一调整，你整条线就是从大到小，那是不是这样子呢，走一下。

那林冲会排在第一位？果然如此，看林冲、卢俊义、宋江正确，好，这个就是你的一个需求，那么我们来看看啊，我们看看如果给他加入相同的节点，它会提示什么信息，比如说我加了一个HERO4。Hero是呢，Hero是好，本身这个人呢，应该是吴用。表示无用啊，同学们。吴用。吴庸这个人呢？他是智多星。智多星没问题，那智多星的话呢，我给他来个也来三号，那么我往里面加，你们看看会有一个什么信息啊。诶，是。这个时候他应该会报告。插插入无用的时候，他会说对不起，你这个你你这个无用啊，呃，已经有了，这个编号已经有了，因为林冲已经占用三号了，看能不能提示这个信息走一个。

啊，走一个同学们可以看到，对不起，那么张一辰吴用没用进去，不用没有进去，那么问大家一个问题，我问大家一个问题，如果我允许有相同的编号存在的话，我只需要改一个什么地方，把这个改一下就行。如果我把这个一改，同学们思考，请同学们思考无用这个人不管怎么添加，只要是后面加无用的，这个无用它应该排在林冲的前面还是后面呢？显然它应该排在零冲的前面，因为你是大于等于的时候就定位了，所以说最后当这样子，如果你这样排的话，往后面加了这个相同编号的人，反而排在他前面啊，排在他前面，你们可以看一下，吴勇会进去，并且在林冲前面。可以看到这个效果果然如此，看到没有这一明确变化非常的灵活，变化非常的灵活，好的，那关于这一个呢，老师就把这个代码给大家整理一下，好吧，整理一下我们看我们完成了哪些个功能，哪些个功能好，我们先是完成一个普通版，普通版就是按照往屁股后边追加的这种方式，对这种方式是，呃，第一种方式是直接在链表最后加入，这个呢比较简单。

这个简单，但是没有太大的使用价值，没有太大使用价值，其实我们在工作中用的更多的一定是这个。一定是这个，这个相对实用性高。啊，当然也也不也不能说上面那个没有用啊，没有没有用也不说，因为你要我就让你用链表实现队列，哎，你你还去就这么干。我要你时间队列这么干，现在因为我有时候是要有序的吗？我就可以这么干了，好，都有用，也不能说是没有用好，同学们，我把这个代码给各位朋友保存到咱们的笔记里边去，好的。好。保存在这里。

报存在这里。好，这是我们的第一个小功能。好，那写完这个呢，我们把它，呃，关于这个显示和添加的两种方式，就先给大家介绍到这里。