356_尚硅谷_Go核心编程_数据结构和算法-双向链表的删除.avi原创

那同学们可以看到啊，刚才呢，我们已经讲了一个双向链表的这个正向输出和逆序输出，同时呢，我们也讲了一下，就是双向链表的这个。这个呃，添加啊，双向里面添加，那如果说我们要实现双向链表的这个，按照顺序添加，这个哪里改呢？其实非常简单，你要改一个地方就行了，哪里改还是这个地方。前面这些地方都不用变化，都不用变化，只是在这个地方进行这个关联的时候，要想办法让它形成一个什么呀，双向的。就是你你必须要考虑这个问题，就是说你不能说，诶我如果你这样做的话呢，像这种方式添加他的呢，是个单向的链表，所以这地方呢，我们来把这个双线给它搞出来啊，把它搞出来，现在这要改的就这啊学习一下叫给双向链表。对。双向链表插入一个节点啊，其他的呃，找这个节点仍然是呃一样的，这就是怎么把这个节点给我建起来，来写一下这个怎么写。

怎么玩呢？打开我们的Excel表。好，我们还是以这个Excel表为例来进行完成。好，先把这个拿过来。好。水。啊。腿太长了。好，我还把你拉过来啊，拿到这边来。好，假设我们同步节点还是在这开始的啊同学们，那现在呢，假设我们寻寻觅觅，我们找找找找，诶，我们找到有一个点，有一个点是要找到这了，找到二我们有一个节点要要谁呢？是三号节点要插进去，大家看这个时候怎么加进去啊，有个三号节点。是不是是不是这个数据结构听久了过后突然感觉头有点晕了啊，头有点晕，这很正常，这是正常反应啊，这正常反应呃，你要你要是不决定因反而是也不正常的啊好，那么假设这有个三号节点。

那三号节点呢，我要把它加进去，这个怎么加呢。各位，你得想怎么让它形成个双向的，而且这段顺序是非常重要的，一旦你加入不对，把整个链表就会搞乱。一般来讲原则是这样子的啊，原则是这样子，先通过它，先不要改变，先不要去啊，先先让这个节点。先让这个节点先指向这些节点，然后再让它去指向节点，这是原则，就是先让它。它能够指向的先做好，不要去断掉它们之间两根线，这两根线一旦断掉的话，你就找不到它们之间的关联了，这是个原则，这个我就没写了啊，也就是说先要完成，让把它能够关联的节点先做完，它能做什么，它的前后节点我是可以确定下来的，对不对？

然后再把这两个节点改变，思路是这样子的啊，注定先动它。好，那我的思路就来了，因为你你你你改变这个这个节点一点改变了，可能就找不到后面这个了。所以说这个顺序呢很重要，现在动新节点，新节点的next节点等于time，这个OK，不动这个是OK的。没有任何问题，因为你新节点嘛，你一个新节点，诶新节点，我说这那不就相当于这个线就有了吗。你这个往下走的线不就有了吗？诶，万里长征走完，走完了第一步，紧接着你还要做一个节点，让它的前一个节点指向特步节点，你又走完了第二步。让他指向他。好，这个节点，这句话呢，我们可以把它马上写出来。就是这样写。六注意听啊，这个地方稍微不注意又是一个麻烦事，Pray等于谁呢？看读，哎，这个也OK。

那一旦这句话做完了过后，在我们的内存里面，其实这根线就形成了。但是你这样做的话，不是双向。现在要做一件什么事情，让这个节点的就是臀部节点的下一个节点指向它。对不对。指向他，但是你要敢这么一动，你就完蛋。你这么一动的话也也可以啊，那你最好你就可以通过这个漏的去呢，但是我我我还是先动后面这个，因为你为什么为什么不要先动它呢？因为你通过这个temp能够找到它的前一个节点，你先动这根线。大家理解我的意思吧。先让他走走过去。就让他怎么让这个它的下一个节点知道这个很简单，可以这样写。就是你的temp的点next这个节点。的这个节点等于六。Hero node。大家看能不能看懂。

这句话呢，是我让昆的下一个节点的。前一个节点直接新节点，也就是说相当于把这根线关联起来了。让他执行了。他。最后一个动作，让自己的下一个节点也指向这个新节点。大家看双线那边形成了插到这儿。这这形成的就最后一句话啊，最后一句话就是让臀步的下一个点直接记点OK。OK，但是这个地方有一个漏洞。如果同学们注意看的话，这边是有一一个很巨大的漏洞的。什么都用呢，就说如果你这个痛就是最后这个节点。如果你的temp是最后一个节点的话，那么你最大的问题是你的next已经没有了你，你居然还敢去访问它的前一个节点。就说这句话会存在一个巨大的漏洞，什么时候会爆发呢？就是你刚好在添加的时候吧。它那个节点刚好是最后一个节点，就是你要添加到最后，就是你那个数太大了，它排到这个链表最后，你这样去想想的话，是ten.next这个面已经是个空了。

它应该是空，你再去取到pre肯定就报错，因此在加一个条件就可以了，如果就是要满足什么条件呢？temp.next它不等于near的时候，我们才去做这个工作，也就是说。相对说最后一个节点，它少一个链接。最后那个线少一个连接，这很正常的，好，如果它不等于零二，我们再把它加进去完事。好同学们，这个呢，双向列表在有效的时候就加进去了，也是可以的啊好，这个代码肯定是没问题的，大家放心好了，好，这个是这个是添加添加。那还有一个问题我没有讲啊，删除。说是删除不是删除，删除我们一还没讲呢，删除的话呢，怎么让他删完了过后仍然是一个双向链表。啊，删完了过程中，是不是这个是添加大家看清楚了啊，这是添加是按照编号添加时候保证是个双向列表，那么删除我讲一个就行了啊抛砖引玉讲一个讲哪一个呢。

这个是删除最后的一个节点，我记得好像是。啊啊，这这这个就是删除啊，删除一个节点，那么我们就以它来删除吧，啊好，我们来删除节点，这个时候是双向链表删除一个节点啊把这个讲完差不多了，双向链表。删除一个节点。好大啊，再痛苦一下啊。好。好，那这个删除怎么删呢？其实啊，嗯，跟前面这个也很相似，比如说我们现在突然发现这个家伙要干掉了，这个线我画的稍微好看一点。这对线有有有点不好看了啊，比如说这个三号，他光荣的加入到我们的这个团队，我们现在呢，因为种种原因要要要干掉他了。啊，大家怎么把它干掉过后呢，它还是个双向的。

好，各位同学。好看到了啊，首先假设我们现在呃，要删除的就删号，它删完的功能，你还能保证它是一个双向的啊。你首先要明白你现在这个找到这个被删除的节点是哪一个，如果是前一个节点。这个好，这个呢。这个可以，其实这个地方这个temp也可以直接指向它也可以删，就看你的实际情况了，比如说我们现在呢，仍然是呃，仍仍然是这个前一个节点啊，当然如果他是就找到三也能三。道理是一样的，我就不去啰嗦了，只是你找的时候呢，逻辑上稍微变化一下，就是你找的时候可能是这不是next找的，是直接让特步来比对对吧？诶好，我就以这个为例吧，我就不去说那么啰嗦了，我就以比如说temp找到这了。找到它，要删掉它，好来了，首先第一步，根据老规矩。老规矩，你要做的事情呢，首先就是让他脱离，让他脱离的话，你是让他这个，诶这一是不是有有一个问题啊。

啊，就这这么整整成这个应该是有一个线指向他的吧。好，是这样子的啊，这样子的好，我第一个动作让temp next指向。Next，它的next这个让它这个线呢，先指向它。好，这个动作很好，很容易实现。这个动作很用时间是就是temp next，等于这个已经OK了。这个以原先就这这根线。然后呢，还要做一个动作。就是让它的这个节点，它是next这个节点的前一个节点，让它呢，不再指向temp步，让它指向它。好让他执行它，好，那这个期间也也很好，也很好做，他就这样写的就是temp。点next。点呃，它是next的啊，现在注意这个。

这个这地方有有大家要理解啊，此时此刻这个的。就已经指向了。这个时候的temp next，因为它它已经这个next已经指向它了，所以说你就不能再取next，也就是说这个时候的next已经跟前面这个next不一样了。它相当于是这个了，它等价于原先的这个nextx X，如果你这再再再加一个X，就是四个X，那就不行了，这方这个X就已经指向了，相当于指向它那个后面的节点，然后它的pre。他的这个地方还是有点绕啊。这个指向谁呢？他这个pre指向。指向这个temp就完事了，指向这个temp篷就完事了，好，Temp，那么看看这有没有危险。啊，哪个地方会有危险呢？是next next如最大的危险可能性来自于最后这个节点，我们看最后节点有没有这种会出现一个异常的情况。如果是我们，不幸找到的就是他。

就333到这儿。如果是这样的话，我们删除就是这个节点，因为它始终是让后面这个节点去比对，看看这个行不行呢，Nextx的，那看nextx那就麻烦了。如果这样说的话，风险比较高。因为你这样做，他已经在这儿了，它的next，再next就是空。反正也没没问题，他next就是它的next就是temp点。temp.next是它在X空，把空给它，相当于是对的，反而是正确的。他本身就是就滞空了，把自己制空，这是对的，但是滞空了一个滞空了过后。Pray这地方应该有一个前提，对，这边要加个条件啊，分析出来了，这个风险度很高，就是你一定要保证tap.next不等于near才去做这个连接，因为假设它最后就是一个逆你，你就不需要再去动它了。因为你已经把它干掉了嘛，对吧，所以说这边有一个条件是它不等于内二的时候我们才去做，否则的话，这种事存在一个问题的，大家想想是不是这个道理。

我们这样说吧，我们这样说，假设我没有接这个，你们看。假设，假设我们没有这句话，我们会有什么风险？来看看，把这个代码我给粘过来。第二站过来，我就做一个分析。做一个分析，听我说啊，同学们不要不要害怕。数据结构是大家长知识的地方，也是比较烧脑，烧脑的一个111个点，不是你们觉得难啊，不是你们觉得呢，所有的学计算机的都会觉得难。包括我们以前在大学的时候学习也是觉得很难的，而且这个呢，还不算特别难啊，大家看如果如果在中间这个没问题，刚才我们已经我们已经做过测试了，就是假设你三的这个节点是三。没问题，因为我我这个temp每次都是以下一个节点来进行这个删除的。因为我最终是只从害开始走的嘛，所以说其实到三的时候，我已经把把这个四就已经做了比较了，假设我这个ten定位到这了，我发现诶要删的就是四。

如果我判断要三到四四的话，这个temp其实就在三这个位置，大家这点必须认同啊，说老师那假设要三到14呢，我反复强调了它如果，因为它总是跟他后面那个比对嘛，所以他这个就找到，如果他到四的话，就说明根本一个都没有要删除的，明白了吧，我们原先就是这个逻辑。因为我们始终是在以temp的下一个节点进行跟新节点进行比对的，如果真的temp到这来的话，你你就不用删了，就直接到哪了，直接到这个地方了，到我们这这句话了。看到没有？已经到这来了，明白这意思吧，所以说大家不用担心，所以说他要删的话，一定是temp在哪呢？在这最后一个点一定是在这，好，我们来看看这个代码的风险在哪里，第一点ten.next。Ten不点next，好，原先这个线是这样子的啊。

好，原先这根线是如此这般的。好，我们先把这个线给它画好。原先是这样一个情况，现在要删除的是卢俊义。因为如果三中间没问题，好，temp.next就是这个地方等于temp next next next就是。你看temp点点X已经是它了。在那不就空吗？好，这个相当于是temp，这个就等价于什么temp。点next等于near，这个是可以的。因为你本身就是这个节点，就是你要删除的，所以说他一旦把它相当于把这个线断掉了嘛。对不对，他断掉了，其实这个事情已经结束了，同学们，因为你最后这个节点。他以他前他后面没有节点，其实这个事情已经结束了，但是你没有结束，你你为什么你没有结束呢？你没加条件判断你干了一件什么事呢？好，你做了这样事事，你说temp.next。

点好不是谁，是这点next是谁。它那已经是空了，还还好跑啥，因为你上面已经把next制成空了，如果你再去取next的这个地方已经是空，你再取空的一个必然报错。所以说这方要有一个条件，什么条件呢？一定要保证，就说你要保证一个前提就是temp.next它是不等于空的才可以。啊，把这个条件加进去，这个代码就完美了。好，这个代码就完美了，就把这个写进去，说明这个条件，其实其实就是说我删的不是最后一点，好把这个写进去就就可以了啊，这个地方是有点绕啊，因为你付完这个next，这个temp next已经发生变化了，好我把这个加条条件加进去就完事了，好同学们，这个呢，就是我们的删除动作完事了。肯定是对的啊，你放心好，我把代码呢给同学们整理一下，刚才我们整理了几个逻辑啊。

好，我们，呃，把这个双向链表的这个地方也做了啊，呃，跟双向链表没关的，我把它删掉。这个是有双向链表在里面的，有有双向链表，这个呢也有双向链表。好，这个也算向量表，其实都都有了。删除也有双向链表显示，这帮也有双向链表都都在里边啊好，这边是双向链表显示逆序好可以了，那现在说也就是说我把双线列表的增三显示全部给他讲完了。当你有没有理解清楚这个同学们啊，就是说好好去想一想，我的代码就不多说了啊，直接粘到这，因为代码比较多，就不截了。好的同学们，那关于这个双线链表呢，就先给同学们介绍的这些。