乐趣区

关于java:别孤寡了看看-LinkedList-不香吗

jiezi

作者爱谈话

Hello，我是 isysc

这是保持原创的 第 8 篇 文章

每次写完文章都感觉，糟了糟了，爆文预约了，怎么办怎么办。等到正式收回去的时候，才晓得，原来是想太多了。

每次写文章的选题都是一件很纠结的事，就比方我从下午 5.30 坐在电脑前想选题到了 6 点，终于决定好了，还是先去吃饭吧。

回来的路上终于有了灵感，写一些汇合相干的源码？

Got it

背景引入

尽管明天阳光明媚，然而林布丁的心里却下起了雨，不是因为女朋友的傲娇，而是今天上午面试官说的“ArrayList 和 LinkedList 的区别都不会，你还是回家种地吧”

失落的林布丁来到了表哥林步动的家里“步动表哥，你为啥始终盯着屏幕？”

步动：就你话多，找我有什么事？

布丁：表哥，明天面试官问我 ArrayList 和 LinkedList 的区别，ArrayList 我倒是晓得一点点，LinkedList 我都不晓得是啥玩意，而后面试官就和我说，8 月是种白菜的好节令。表哥你能不能和我讲讲，什么是 LinkedList，最好能从源码角度给我讲讲？

步动：嘴巴如同有点渴。

布丁：表哥，你给我讲明确了，我请你喝一个星期的 奈雪的茶

步动：安顿

什么是 LinkedList

你不懂的货色只是因为你没看过它的源码 –

秉承着万物皆可 new 的准则（女朋友除外）

咱们先来 new 一个 LinkedList，而后点进去看一看，会不会有什么神奇的事件产生。

步动：看！呈现了一堆的正文，表弟你只有全文熟读并背诵就能够解决面试官了。明天就讲到这里了，快去给我买奶茶吧。

布丁：表哥，你也太水了叭，这么多英文我哪里看得懂，你就不能给我概括一下吗？

步动：好吧，谁叫我是暖男，毕竟是过了英语 5 级的男人，我给你翻译概括一下，要是有不对的中央，你就本人推敲下，也别和我说。

“

想要看原汁原味的正文，能够去 idea 里 new 一个看看，这里贴出来篇幅就过长了。也能够看看官网介绍 https://docs.oracle.com/javas…

步动：这里正文次要写的就是

  • Linkedlist 应用“双向链表”来实现 List 与 Deque 接口。实现了所有 List 接口中的办法，并且容许寄存所有元素，包含 Null
  • 所有的操作都可通过双向链表实现。通过从结尾或者结尾遍历汇合，去靠近要操作的那个元素。
  • 请留神，LinkedList 是非同步的。如果多个线程同时操作 LinkedList 实例，并且至多一个线程在结构上的批改链表，则它必须要保障线程的同步。（结构性批改：减少或删除元素，或者调整数组大小，仅仅批改属性的值不属于结构性批改）典型的实现是同步操作数组。
  • 如果这种对象不存在，又想同步汇合，能够这样写
Listlist=Collections.synchronizedList(newLinkedList(...))

布丁：表哥，你说完了？我尽管看不懂英语，然而我数的分明，一共 7 段英文，你就给我翻译了 3 段，剩下的 3 段呢，你是不是不行啊，表哥？

步动：男人怎么能说不行，剩下两段是对于 fail-fast 个性的，区区几句话段说不清楚，我在网上给你找了一篇文章，你回头关注下 码儿嘟嘟骑 回复【fail-fast】就能够看到了，二维码我给给你贴在信上面了，关注回复还有大厂面试材料，别怪表哥没有通知你。

布丁：表哥我关注啦。表哥，我听你的意思是 LinkedList 底层构造就是双向链表是吗？

步动：是的，我再给你具体讲下双向链表到底是啥玩意吧。让我给你整个图

布丁：什么 first，Node，prev 我都不看不懂

步动：我给你解释下吧

  • Node 代表链表中的节点。具备两个属性 prev 代表前一个节点 next 相同 就代表下一个节点
  • first 代表着是双向链表的头节点，它的前一个节点因为赤贫如洗，那就是 null
  • last 是双向链表的尾节点，它的后一个节点同样穷困潦倒，所以也是 null
  • 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null

口说无凭，上源码

// 节点值  
Eitem;  
// 指向的下一个节点  
Node<E>next;  
// 指向的前一个节点  
Node<E>prev;  
// 参数按程序初始化  
Node(Node<E>prev,Eelement,Node<E>next){  
this.item=element;  
this.next=next;  
this.prev=prev;  
}  
}

布丁：我明确啦，表哥，我记住啦。那你再给我讲讲 LinkedList 的构造函数吧？

LinkedList 构造函数

步动：LinkedList 的构造函数写的十分优雅，你看。

// 无参结构，结构一个空的双向链表  
publicLinkedList(){}  
 
// 有参结构  
publicLinkedList(Collection<?extendsE>c){this();  
// 应用 addAll 办法，实际上就是应用遍历 c 并且采纳头插法进行双向链表插入值  
addAll(c);// 具体不开展啦，}

布丁：哦哦，那表哥，那给我具体讲讲 CRUD 吧。具体讲讲

LinkedList 的 CRUD

add

布动：咱们往下扒拉扒拉源码能够看见

/**  
*Insertsthespecifiedelementatthebeginningofthislist.  
*  
*@parametheelementtoadd  
*/  
publicvoidaddFirst(Ee){linkFirst(e);  
}    
/**  
*Appendsthespecifiedelementtotheendofthislist.  
*  
*<p>Thismethodisequivalentto{@link#add}.  
*  
*@parametheelementtoadd  
*/  
publicvoidaddLast(Ee){linkLast(e);  
}

一个 addFirst 和 addLast 你本人看就完事了

布丁：表哥，你这样那我就只能请你喝古茗了

步动：你本人看也吃力，必定得表哥给你讲讲你也好排汇嘛，那咱们先讲讲 addFirst

// 从头部追加  
privatevoidlinkFirst(Ee){  
// 头节点赋值给长期变量  
finalNode<E>f=first;  
// 新建节点，前一个节点指向 null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值  
finalNode<E>newNode=newNode<>(null,e,f);  
// 新建节点成为头节点  
first=newNode;  
// 如果头节点为空，就是整个链表都为空，那么头尾节点是一个节点  
if(f==null)  
last=newNode;  
// 上一个头节点的前一个节点指向以后节点（有点绕口，多读两遍）else  
f.prev=newNode;  
// 批改 LinkedList 大小  
size++;  
// 批改 LinkedList 的批改统计数：用来实现 fail-fast 机制。modCount++;  
}

中心思想就是扭转节点指向，批改 LinkedList 大小和统计数

// 从尾部开始追加节点  
voidlinkLast(Ee){  
// 利用一个长期变量寄存尾节点数据  
finalNode<E>l=last;  
// 新建新的节点，初始化入参含意：// l 是新节点的前一个节点，以后值是尾节点值  
// e 示意以后新增节点，以后新增节点后一个节点是 null  
finalNode<E>newNode=newNode<>(l,e,null);  
// 新建节点追加到尾部  
last=newNode;  
// 如果链表为空（l 是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点  
if(l==null)  
first=newNode;  
// 否则把前尾节点的下一个节点，指向以后尾节点。else  
l.next=newNode;  
// 大小和版本更改  
size++;  
modCount++;  
}

总的来说，addFirst 和 addLast 两个办法是十分类似的，只是前者是挪动头节点的 prev 指向，后者是挪动尾节点的 next 指向。

布丁：步动表哥，那我默认 add 是增加到尾部还是头部啊？

步动：如果你 new 一个 LinkedList 而后间接 add，默认是增加到尾部。

remove

布丁：那表哥，我如何从链表中删除一个元素呢？

步动：删除元素和减少也是相似的，能够从头部删除，也能够从尾巴删除，remove 操作会将你想要删除的节点的值，前后都指向 null，你晓得为什么都要指向 null 吗？

布丁：无依无靠？不便 GC

步动：对，接下来给你看看 remove 源码

// 从头删除节点 f 是代表链表头节点  
privateEunlinkFirst(Node<E>f){  
// 取出头节点的值，作为一会办法的返回值  
finalEelement=f.item;  
// 取出头节点的下一个节点  
finalNode<E>next=f.next;  
// 原正文就是 helpGC，就是帮忙 GC 回收头节点  
f.item=null;  
f.next=null;  
// 头节点的下一个节点，取代原先头节点的霸主地位，成为新的头节点  
first=next;  
// 如果 next 为空，表明链表为空  
if(next==null)  
last=null;  
// 链表不为空，头节点的前一个节点指向 null  
else  
next.prev=null;  
// 批改链表大小和版本  
size--;  
modCount++;  
returnelement;  
}

步动：从尾部删除的源码我就不给你说了，和这个也 十分相似，给你本人斟酌斟酌

布丁：行叭，表哥，我看其实 链表的节点新增、删除都好简略啊，仅仅把前后节点的指向批改下就好了，所以 LinkedList 新增和删除速度是不是很快？

步动：对！你很聪慧哦

get

// 依据链表索引地位查问节点  
Node<E>node(intindex){  
// 如果 index 处于队列的前半部分，从头开始找，size>>1 是 size 除以 2 的意思  
// 用位运算就是为了放慢计算速度，冲呀  
if(index<(size>>1)){  
Node<E>x=first;  
// 直到 for 循环到 index 的前一个 node 进行  
for(inti=0;i<index;i++)  
x=x.next;  
returnx;  
}else{  
// 如果 index 处于队列的后半局部，就从尾巴开始找  
// 所做的一切都是为了放慢 get 的速度，用心良苦  
Node<E>x=last;  
// 直到 for 循环到 index 的后一个 node 进行  
for(inti=size-1p;x.prev;  
returnx;  
}  
}

步动：LinkedList 并没有采纳从头循环到尾的做法，而是采取了简略二分法，如果你不晓得什么是二分法，那就不晓得吧。

步动：简略来说，LinkedList 的查找首先看看 index 是在链表的前半部分，还是后半局部。如果是前半部分，就从头开始寻找，反之尾巴找。布丁，你晓得这样做有什么益处吗？

布丁：表哥我刚百度到二分法，就是通过这种形式，能够让循环的次数至多升高了一半呀，进步了查找的性能。

set

布丁：快快快，表哥，趁热打铁，给我讲讲 LinkedList 是怎么更新的？

步动：好滴

publicEset(intindex,Eelement){  
// 查看是否越界，你传入的 index 必须大于等于 0，小于 LinkedList 长度  
// 什么，你非得传小于 0，那不好意思，抛 IndexOutOfBoundsException 异样  
checkElementIndex(index);  
// 查处 index 地位原先的寓居客人  
Node<E>x=node(index);  
// 取出行将被替换的值，以便于一会扔出去  
EoldVal=x.item;  
// 新王登基  
x.item=element;  
// 旧王扔掉  
returnoldVal;  
}

LinkedList 的迭代器

布丁：好的，我明确啦，表哥，最初一个知识点啦，你给我讲 LinkedList 的迭代器？

步动：害，不争气的表弟。快讲完，我要吃饭啦。

步动：表弟，你晓得吗？因为 LinkedList 要实现双向的迭代拜访，所以咱们通常的应用 Iterator 接口必定不行了（Iterator 只反对从头到尾的拜访）所以 Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代办法，如下所示：

迭代程序

办法

从尾到头迭代办法

hasPrevious、previous、previousIndex

从头到尾迭代办法

hasNext、next、nextIndex

口说无凭，看源码

LinkedList 实现了 ListIterator 接口

// 双向迭代器  
privateclassListItrimplementsListIterator<E>{// 上一次执行 next()或者 previos()办法时的节点地位  
privateNode<E>lastReturned;  
// 下一个节点  
privateNode<E>next;  
// 下一个节点的索引地位  
privateintnextIndex;  
// 冀望版本号；modCount：目前最新版本号，也是 fail-fast 的相干知识点  
privateintexpectedModCount=modCount;  
…………  
}

咱们先来看下从头到尾方向的迭代：

// 判断还有没有下一个元素  
publicbooleanhasNext(){  
// 下一个节点的索引小于链表的大小  
returnnextIndex<size;  
}  
 
// 取下一个元素  
publicEnext(){  
// 查看冀望版本号有无发生变化  
checkForComodification();  
// 再次查看  
if(!hasNext())  
thrownewNoSuchElementException();  
//next 是以后节点，在上一次执行 next()办法时被赋值的。// 第一次执行时，是在初始化迭代器的时候，next 被赋值的  
lastReturned=next;  
//next 是下一个节点了，为下次迭代做筹备  
next=next.next;  
nextIndex++;  
returnlastReturned.item;  
}

布丁：就是间接取以后节点的下一个节点呗，那表哥再讲讲从尾到头迭代的过程

步动：好的

// 如果上次节点索引地位大于 0，就还有节点能够迭代  
publicbooleanhasPrevious(){returnnextIndex>0;}  
// 取前一个节点  
publicEprevious(){checkForComodification();  
if(!hasPrevious())  
thrownewNoSuchElementException();  
//next 为空场景：//1: 阐明是第一次迭代，取尾节点(last);  
//2: 上一次操作把尾节点删除掉了  
//next 不为空场景：阐明曾经产生过迭代了，间接取前一个节点即可(next.prev)  
lastReturned=next=(next==null)?last:next.prev; 
// 索引地位变动  
nextIndex--;  
returnlastReturned.item;  
}

步动：最初再讲讲迭代器的删除，LinkedList 在删除元素时，最好通过迭代器进行删除


public void remove(){checkForComodification();  
//lastReturned 是本次迭代须要删除的值，分以下空和非空两种状况：//lastReturned 为空，阐明调用者没有被动执行过 next()或者 previos()，间接报错  
//lastReturned 不为空，是在上次执行 next()或者 previos()办法时赋的值  
if(lastReturned==null)  
thrownewIllegalStateException();  
Node<E>lastNext=lastReturned.next;  
// 删除以后节点  
unlink(lastReturned);  
//next==lastReturned 的场景剖析：从尾到头递归程序，并且是第一次迭代，并且要删除最初一个元素的状况下  
// 这种状况下，previous()办法外面设置了 lastReturned=next=last, 所以 next 和 lastReturned 会相等  
if(next==lastReturned)  
// 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous()执行时，发现 next 是 null，就会把尾节点赋值给 next  
next=lastNext;  
else  
nextIndex--;  
lastReturned=null;  
expectedModCount++;

LinkedList 的利用场景

布丁：表哥，我有最初一个问题。LinkedList 的利用场景都有哪些？

步动：LinkedList 实用于要求有程序、并且会依照程序进行迭代的场景，次要是依赖于底层的链表构造。

LinkedList 的高频面试点

1，什么是 LinkedList，次要使用场景是？

2，什么时候应用 ArrayLis，什么时候应用 inkedList，二者的区别是？

3，LinkedList 底层构造是？

4，能说说 LinkedList 常见的办法吗？

置信你读过下面的文章，能够熟（zahung）练（bi）的答复进去

参考文章：

文贺：面试官零碎精讲 Java 源码及大厂真题

扬帆向海：深刻分析 LinkedList 的底层源码，再也不怕面试官问了！

退出移动版