关于java:JDK成长记6你了解LinkedList的五脏六腑么

45次阅读

共计 5725 个字符，预计需要花费 15 分钟才能阅读完成。

上一节你看过了 LinkedList 的 add 办法源码，是不是曾经关上了思路呢？其实外围原理就是辅助指针 +Node 双向链表数据结构而已。

置信通过后面的学习，你应该热身结束了，之后的学习能够让咱们能够加快速度了。

GO！GO！

这一节你还须要深刻 LinkedList 的其余办法摸索下它们的底层原理是什么。

学完这一节，你能够本人写出一个 LinkedList，甚至能够触类旁通写出单向链表的 List, 逆转一个单向链表等等。你也能够攻克很多链表的算法题。面试问到 ArrayList 和 LinkedList 的时候，置信你也会信手拈来。

让咱们一起开始吧！

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”> 另一个 add(int index,E e)办法 </span></h3></div>

有了之前的教训，置信当初你不须要我在一步一步带着你看源码原理了。我间接将外围源码 + 配图的形式给大家解说下原理。你更多的是要依据我的这个思路本人把源码浏览一下，本人画图讲给他人听听才是最好的学习办法。

首先来看下另一个 add 办法，在某个地位减少一个元素。外围源码原理图如下所示：

从 add 办法源码脉络能够看到，当调用的 add 办法时，会依据要插入的地位 index 判断，是否向尾节点增加元素。如果是和上一节讲的一般 add（E e）办法一样，调用了 linkLast 办法而已。次要不同的是当不是向尾节点增加元素时，调用了 linkBefore 办法。

而 linkBefore 外围是通过 node（int index）定位元素的。如下图所示：

先看源码的脉络，外围是一个 if，两个 for 循环。再看下细节，if 条件是什么意思？如图中所示，就是进行了右移 1，和除以 2 类似，相似于二分法的思维。接着 for 循环，通过 x.next 或 x.prev 开始从前或者从后向前寻找元素。

这个思路是不是，还是个不错的亮点，很多时候算法都会有二分法，或者分而治之的思维。

当通过 node 办法确认了 index 地位的元素后，就开始执行 linkBefore 办法了。如下图所示：

下面源码脉络，次要分三步，你能够跟着如下思路看：

1、将之前 node 定位的元素记为 succ 传入, 通过一个辅助指针 pred 指向定位元素的前一个节点。

2、之后创立一个 newNode，它的 prev 指针指向 pred 所在位置，尾指针指向 succ，也就是定位的元素。

3、最初批改定位元素的 prev 指针，指向新元素，批改 pred 地位的元素尾指针指向新元素。

最初就会造成上图的后果了。其实你能够发现，和 linkLast 很像，linkLast 是通过辅助指针 l 指向 last，来帮忙在结尾增加节点的。而 linkBefore 是通过，先定位元素后，用定位元素的 prev 前一个节点作为辅助，插入元素的。你只有记住这个思路，肯定能本人手写进去两种 add 办法的。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>remove 系列办法 </span></h3></div>

LinkedList 的 remove 办法，大多都很类似，都是一些指针变换。你剖析的最好办法还是 画图。

置信到这里，你曾经把握根本剖析源码的形式和办法了，这里就不再一步一步带大家看源码了。间接给大家解说下源码的原理图能够了。

首先是 removeLast 办法的源码原理图，如下所示：

源码的外围的脉络就是应用一个 l 指针，记录了尾节点的地位，之后通过 l.prev 找到之前的元素, 记录下为 prev，和最初一个元素断开 l.next=null，让 last 指针指向新的尾节点 prev 即可。

再看看 removeFirst 办法的原理图:

你其实能够看到和之前 removeLast 很像，只不过是应用 f 指针，记录了头节点地位，之后 next 记录下 f.next。断开和原头节点的连贯 next.prev=null。最初再让 first 指针指向新的头结点。

其实你只有记住这个思路就能够。双向链表应用一个辅助指针记录 prev 或 next 的地位 + 头 / 尾指针，就能够非常简单的实现从头节点或者尾节点删除元素。手写应该也不是什么难事。

最初你来看下 remove(index)办法的源码原理图：

能够看到，remove(index)办法，通过 node 办法定位元素，之后应用了两个辅助指针，prev 和 next 别离记录了所定位元素的前后节点。

定位元素的源码原理上一节曾经讲过了，就是二分法 +for 循环遍历查找而已。通过 prev 和 next 两个指针，就能够别离断开定位元素 x 的前后指针，并且 next 和 prev 从新相接，就实现了从某个地位删除元素了。

外围原理，就是定位 + 前后辅助指针来实现的，你要记住这点思路就能够本人尝试手写 remove 办法了。

到这里 LinkedList 的外围办法就带大家看完了，它还有一些高级办法，addAll、toArray 等等，你能够本人简略的看下，当初对你其实没什么难度的。大家看这些办法找到外围原理总结下来就好。

另外，Vector 和 Stack 这两个汇合类齐全和 ArrayList 很像。除了 Vector 扩容默认是两倍，是线程平安的，底层通过 synchronized 来实现的。Statck 继承了 Vector，通过数组实现了相似栈的数据结构。大家之后能够简略扫一下就能够了，除了很老的源码代码或者业务程序，当初根本不会应用这两个汇合类了，因为底层的 synchronized 锁太影响性能了。

这一节你应该学到的一个思维就是，总结。当你依照脉络看完源码后，画完图后，不能就此结束了。肯定要总结一个要点和几个要点进去。总结体现了做一件事的输入后果。做任何事件都是样的，比方运维治理 IDC 机柜机器，要出一个 excel 记录每台机器的洽购工夫，电池状况，硬盘状况等等。excel 就是一个输入后果，一个总结。

你在工作中，很多事件要以一个后果为完结才是最好的。文档也好，流程点、里程碑也好，最好你要总结记录下这个后果。置信你保持这样做会很有很多益处的。

除了明天常识，技能的成长，给大家带来一个金句甜点，完结我明天的分享：保持的三个秘诀之一视觉化。

置信你必定有会感觉过，保持很难，可能你保持 1 周还好，然而保持 1 个月，1 年，2 年,5 年，10 年，一辈子…… 总有一个让你感觉，如同真的保持好难。然而其实很多时候不是保持很难，而是你感觉值不值得的问题。这是根本原因，你能够认真想想，是不是因为这个观点所导致的。

除了要意识到这个观点以外，到底怎么能力保持一件事件呢？之后的文章我会给大家分享保持的 3 个秘诀。首先第一个秘诀就是 视觉化。给大家举个亲身经历吧，我毕业后工作了几年，从一个瘦瘦的程序员，变成了带游泳圈的瘦瘦程序员。于是有一天我决定要减脂塑形，想要复原原来的肚子。不晓得你们是不是也遇见过这种场景。于是我首先把我喜爱的一个偶像的有型的照片，有腹肌那种海报，贴在了家里一个比拟随便的中央，还附上了我本人的一个照片。那个画面几乎了。。。我开始管制饮食，逐步减少锤炼强度和频次，每次我不想静止的时候就会不经意的看到海报和我本人的照片，我再看看我的小肚子，就又开始锤炼了。就着这样人不知; 鬼不觉就保持了 1 个月，果然有了成果，居然体脂率降落了 2%，体重降落了 11 斤，肚子小了一大圈，就是肌肉量没啥变动，反正没少就不错了。接着，我就造成习惯了，再次在减少静止强度和频次，因为我始终想着有一天程序员能有 6 块或者 8 块腹肌，那个场景好让人向往啊。所以我始终在保持着。

其实视觉化的实质就是让你感觉保持的事件很值。你喜爱演讲，你能够设想，有一天你站在上千人的听众背后，你声情并茂的做了一场精彩的演讲，那个场景就能够激励你每天一直的练习和学习，你想要降职，你就不会睡懒觉，每天不会睡到天然醒，因为每当你起不了床的时候，你心中设想到一个场景，你降职后能够给父母多寄些钱，给妻子、孩子买好的货色，能够加重房贷或者车贷，能够帮忙感恩之前帮忙过的你的人等等，总有一个会让你觉的值的理由，让你坚持下去的，是不是？当然你喜爱学习，你也能够每周保持看几篇成长记来晋升本人，置信成长会让你变的更有价值，更有自信。

记住你人生中每走过的一步路，都不会被辜负的。总有一天又体现进去的。加油吧，各位！保持吧，各位！

最初，你能够浏览完源码后，在茶余饭后的时候问问共事或同学，你也能够分享下，讲给他听听。

欢送大家在评论区留言和我交换。