jdk8源码3---集合2---LinkedList

╰+哭是因爲堅強的太久メ 2022-05-23 13:47 171阅读 0赞

**一、签名**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public class LinkedList&lt;E&gt; &nbsp;&nbsp;&nbsp; extends AbstractSequentialList&lt;E&gt; &nbsp;&nbsp;&nbsp; implements List&lt;E&gt;, Deque&lt;E&gt;, Cloneable, java.io.Serializable </td> 
 </tr> 
 </tbody> 
</table>

**1.  继承了AbstractSequentialList<>**

**2.  实现了Deque：出现在1.6，继承了Queue。双端队列容器，不仅可以在尾部插入，删除元素，还可以在头部插入和删除元素。**

**3.  Clone:可以克隆**

**4.  Serializable：可被序列化**

**二、成员变量**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> trainsient int size = 0; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> Transient Node&lt;E&gt; first;&nbsp; // 记录第一个。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> Transient Node&lt;E&gt; last;&nbsp; // 只记录当前的节点，也是最后一个 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> protected transient int modCount = 0; //记录当前对LinkedList修改的次数 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> private static class Node&lt;E&gt; { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E item; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node&lt;E&gt; next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node&lt;E&gt; prev; &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; this.item = element; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; this.next = next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; this.prev = prev; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

** **

**三、构造方法**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public LinkedList() { &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> public LinkedList(Collection&lt;? extends E&gt; c) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; this(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; addAll(c); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

** **

**四、成员方法**

**1.1 .add(E e)**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public boolean add(E e) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; linkLast(e); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return true; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> void linkLast(E e) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; l = last; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; newNode = new Node&lt;&gt;(l, e, null); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; last = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (l == null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; first = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; l.next = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; modCount++; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**1.2     add(intindex,E element)**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public void add(int index, E element) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; checkPositionIndex(index); &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (index == size)&nbsp; // 如果插入的位置是最后一个， &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; linkLast(element); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; linkBefore(element, node(index)); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> void linkLast(E e) 见上 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> void linkBefore(E e, Node&lt;E&gt; succ) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // assert succ != null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; pred = succ.prev; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; newNode = new Node&lt;&gt;(pred, e, succ); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; succ.prev = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (pred == null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; first = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; pred.next = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; modCount++; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**1.3     push();**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public void push(E e) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; addFirst(e); // 不知道为什么 不直接使用linkFirst(e) &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> public void addFirst(E e) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; linkFirst(e); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> private void linkFirst(E e) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; f = first; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; newNode = new Node&lt;&gt;(null, e, f);//注意linkLast的不同之处。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; first = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (f == null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; last = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f.prev = newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; modCount++; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

** **

**2.1.remove()**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E remove() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return removeFirst(); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> public E removeFirst() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; f = first; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (f == null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; throw new NoSuchElementException(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return unlinkFirst(f); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> private E unlinkFirst(Node&lt;E&gt; f) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // assert f == first &amp;&amp; f != null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final E element = f.item; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; next = f.next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f.item = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f.next = null; // help GC &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; first = next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (next == null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; last = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; next.prev = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; modCount++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return element; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**2.2 removeFirst()**

**2.3 removeLast()**

**2.4 remove(intindex)**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E remove(int index) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; checkElementIndex(index); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return unlink(node(index)); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> Node&lt;E&gt; node(int index) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // assert isElementIndex(index); &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (index &lt; (size &gt;&gt; 1)) {&nbsp; // 二分查找。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node&lt;E&gt; x = first; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = 0; i &lt; index; i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x = x.next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return x; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } else { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node&lt;E&gt; x = last; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = size - 1; i &gt; index; i--) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x = x.prev; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return x; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> E unlink(Node&lt;E&gt; x) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // assert x != null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final E element = x.item; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;final Node&lt;E&gt; next = x.next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; prev = x.prev; &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (prev == null) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; first = next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } else { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; prev.next = next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.prev = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (next == null) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; last = prev; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } else { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; next.prev = prev; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.next = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.item = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; modCount++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return element; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**2.5 public E pop()**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E pop() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return removeFirst(); &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**3.1 public E set(int index,E element)**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E set(int index, E element) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; checkElementIndex(index); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node&lt;E&gt; x = node(index); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E oldVal = x.item; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.item = element; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return oldVal; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**4.1     publicE get(int index)**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E get(int index) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; checkElementIndex(index); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return node(index).item; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**4.2     publicE peekFirst()**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E peekFirst() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; f = first; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (f == null) ? null : f.item; &nbsp;&nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**4.3     publicE peekLast()**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public E peekLast() { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; final Node&lt;E&gt; l = last; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (l == null) ? null : l.item; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**5.  publicBoolean contains(Object o)**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public boolean contains(Object o) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return indexOf(o) != -1; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> public int indexOf(Object o) { // 这种方式就是挨个遍历。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int index = 0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (o == null) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (Node&lt;E&gt; x = first; x != null; x = x.next) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (x.item == null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return index; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; index++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } else { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (Node&lt;E&gt; x = first; x != null; x = x.next) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (o.equals(x.item)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return index; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; index++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return -1; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**6.  publicvoid clear()**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> public void clear() { // 将所有都置为null，help GC &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (Node&lt;E&gt; x = first; x != null; ) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Node&lt;E&gt; next = x.next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.item = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.next = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x.prev = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x = next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; first = last = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; size = 0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; modCount++; &nbsp;&nbsp;&nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

** **

**五、遍历方式**

**1.  for**

**2.  fori**

**3.  iterator()**

** **

**总结：**

**1.  原理是链表。**

**2.  有序**

**3.  非线程安全**

**4.  元素允许为null**

**5.  遍历时候for,都会调用node(index)方法。**

**6.  效率问题：**

**很多文章都再说，arrayList查找快，增删慢，LinkedList增删快，查找慢。**

**这种说法不准确：**

**（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址**

**（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址**

**所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。**

**从这个分析看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你删除、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作，**

## 最后 ##

如果你觉得写的还不错，就关注下公众号呗，关注后，有点小礼物回赠给你。  
你可以获得5000+电子书，java,springCloud,adroid,python等各种视频教程，IT类经典书籍，各种软件的安装及破解教程。  
希望一块学习，一块进步！  
![20190901125800286.jpg][]

[20190901125800286.jpg]: https://img-blog.csdnimg.cn/20190901125800286.jpg