转载

JDK源码分析-LinkedList

概述

相较于 ArrayList,LinkedList 在平时使用少一些。

LinkedList 内部是一个双向链表,并且实现了 List 接口和 Deque 接口,因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下:

JDK源码分析-LinkedList

前文分析了 Queue 和 Deque 接口,正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承结构如下:

JDK源码分析-LinkedList

结点类 Node

查看 LinkedList 的源码可发现它内部有个嵌套类 Node,代码如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> static <span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">class</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">Node</span>&lt;<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">E</span>&gt; </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> E item; <span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 存储的数据</span></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; next; <span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 后继结点</span></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; prev; <span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 前驱结点</span></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">this</span>.item = element;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">this</span>.next = next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">this</span>.prev = prev;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

LinkedList 是双向链表的实现,而该 Node 类则是链表的结点。

此外,LinkedList 还有几个成员变量如下:

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// list 的长度</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">transient</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> size = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 链表头结点</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">transient</span> Node&lt;E&gt; first;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 链表尾结点</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">transient</span> Node&lt;E&gt; last;</span>

构造器

LinkedList 有两个构造器,如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">LinkedList</span>()</span> {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">LinkedList</span>(<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">Collection&lt;? extends E&gt; c</span>)</span> {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">this</span>();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> addAll(c);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

PS: 由于链表的容量可以一直增加,因此没有指定容量的构造器。

其中第一个为无参构造器;第二个为使用指定的集合构造,并调用 addAll() ,继续跟进该方法,代码如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">boolean</span> addAll(Collection&lt;? <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">extends</span> E&gt; c) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> addAll(size, c);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">boolean</span> addAll(int index, Collection&lt;? <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">extends</span> E&gt; c) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> checkPositionIndex(index);</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 将集合元素转为数组</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">Object</span>[] a = c.toArray();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> int numNew = a.length;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (numNew == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">false</span>;</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 获取当前链表的前驱和后继结点</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; pred, succ;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (index == size) { <span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 尾结点的前驱和后继结点</span></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> succ = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> pred = last;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> } <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">else</span> { <span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 若非尾结点,获取指定位置的结点</span></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> succ = node(index);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> pred = succ.prev;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 循环将数组中的元素插入到链表</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">Object</span> o : a) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">@SuppressWarnings</span>(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">&quot;unchecked&quot;</span>) E e = (E) o;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; newNode = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> Node&lt;&gt;(pred, e, <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (pred == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> first = newNode;</span>

<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;"> else</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> pred.next = newNode;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> pred = newNode;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 若插入到末尾,则数组中的最后一个元素就是尾结点</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (succ == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> last = pred;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> } <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">else</span> {</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 若插入到指定位置,将数组中最后一个元素与下一个位置关联起来</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> pred.next = succ;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> succ.prev = pred;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> size += numNew;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> modCount++;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">true</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

其中 node(index) 方法为获取指定位置的结点,代码如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">Node&lt;E&gt; node(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">//</span> assert isElementIndex(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">//</span> 若下标在前一半,则从前往后遍历;否则从后往前遍历</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span> &lt; (size &gt;&gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">1</span>)) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">x</span> = first;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> i = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>; i &lt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>; i++)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">x</span> = x.next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">x</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> } <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">else</span> {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">x</span> = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">last</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> i = size - <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">1</span>; i &gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>; i--)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">x</span> = x.prev;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">x</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

该方法通过遍历链表获取指定的元素。

值得注意的是,该方法并非直接从头到尾遍历整个链表,而是先判断下标的位置,若在前一半则从前往后遍历;否则就从后往前遍历。这样能减少遍历结点的个数。

PS: 前文「 数据结构与算法笔记(一) 」对链表进行过分析,由于其内存空间非连续,因此不支持随机访问(下标访问)。所以,查询某个结点是通过遍历整个链表来实现的。

与此同时, get(index) 方法内部也是这样实现的:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">public E get(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> checkElementIndex(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> node(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">index</span>).item;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

常用方法

之前分析 Queue 和 Deque 的时候提到:Queue 中的方法在 Deque 中都有对应的。下面简单分析 LinkedList 中一些常用的方法。

新增结点方法:add(), addLast(), offerLast()

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">boolean</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">offerLast</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">(E e)</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> addLast(e);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">true</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">addLast</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">(E e)</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> linkLast(e);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">boolean</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">add</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">(E e)</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> linkLast(e);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">true</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

可以看到他们都是调用了同一个方法  linkLast(e)  实现的,如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">linkLast</span>(E e) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> Node&lt;E&gt; l = last;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> Node&lt;E&gt; newNode = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> Node&lt;&gt;(l, e, <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> last = newNode;</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 若链表为空,则新结点为头结点</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (l == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> first = newNode;</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 若链表不为空,将新结点插入到链表尾部</span>

<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;"> else</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> l.next = newNode;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> size++;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> modCount++;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

该操作就是将指定的结点添加到链表末尾。

删除结点方法:poll(), pollFirst(), removeFirst()

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> E <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">poll</span>() {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> Node&lt;E&gt; f = first;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> (f == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>) ? <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span> : unlinkFirst(f);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> E <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">pollFirst</span>() {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> Node&lt;E&gt; f = first;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> (f == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>) ? <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span> : unlinkFirst(f);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> </span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> E <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">removeFirst</span>() {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> Node&lt;E&gt; f = first;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (f == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">throw</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> NoSuchElementException();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> unlinkFirst(f);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">} </span>

可以看到这三个方法都是调用  unlinkFirst()  方法实现的,其代码如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> E <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">unlinkFirst</span>(Node&lt;E&gt; f) {</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // assert f == first && f != null;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> E element = f.item;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> Node&lt;E&gt; next = f.next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> f.item = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> f.next = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>; <span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// help GC</span></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> first = next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (next == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> last = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>;</span>

<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;"> else</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> next.prev = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> size--;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> modCount++;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> element;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

该方法的操作就是从链表头部移除一个结点。

向单链表插入和删除结点的操作示意图如下(双链表比这里多了前驱结点):

JDK源码分析-LinkedList

栈的入栈(push)和出栈(pop)操作:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">push</span>(<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">E e</span>)</span> {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> addFirst(e);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> E <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">pop</span>()</span> {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> removeFirst();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">} </span>

可以看到这两个方法直接调用了双端队列的实现方法。即,该栈是一个「链式栈」。

线程安全性

线程安全的概念不再赘述。分析以下场景:

若有线程 T1 对 LinkedList 进行遍历,同时线程 T2 对其进行结构性修改。

对 LinkedList 的遍历是通过  listIterator(index) 方法实现的,如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> ListIterator&lt;E&gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">listIterator</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> index)</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> checkPositionIndex(index);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> ListItr(index);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> <span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">class</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">ListItr</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">implements</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">ListIterator</span>&lt;<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">E</span>&gt; </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> Node&lt;E&gt; lastReturned;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> Node&lt;E&gt; next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> nextIndex;</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 初始化时二者是相等的</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> expectedModCount = modCount;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> ListItr(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> index) {</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // assert isPositionIndex(index);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> next = (index == size) ? <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span> : node(index);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> nextIndex = index;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> E <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">next</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">()</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> checkForComodification();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (!hasNext())</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">throw</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> NoSuchElementException();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> lastReturned = next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> next = next.next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> nextIndex++;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> lastReturned.item;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">remove</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">()</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> checkForComodification();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (lastReturned == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">throw</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> IllegalStateException();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Node&lt;E&gt; lastNext = lastReturned.next;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> unlink(lastReturned);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (next == lastReturned)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> next = lastNext;</span>

<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;"> else</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> nextIndex--;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> lastReturned = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">null</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> expectedModCount++;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // ...</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> </span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> // 是否有其他线程对当前对象进行结构修改</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">final</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">checkForComodification</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">()</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (modCount != expectedModCount)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">throw</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> ConcurrentModificationException();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

该类的 next() , add(e) 等方法在执行时会检测 modCount 与创建时是否一致( checkForComodification() 方法),从而判断是否有其他线程对该对象进行了结构修改,若有则抛出 ConcurrentModificationException 异常。

因此,LinkedList 是线程不安全的。

小结

1. LinkedList 内部是「 双向链表 」,同时 实现了 List 接口和 Deque 接口,因此也具备 List、 双端队列和栈的性质;

2. 线程不安全。

相关阅读:

JDK源码-Queue, Deque

Stay hungry, stay foolish.

JDK源码分析-LinkedList

原文  https://juejin.im/post/5d4fe42bf265da03ad14418c
正文到此结束
Loading...