上一章学习了ArrayList，并分析了其源码，这一章我们将对LinkedList的具体实现进行详细的学习。依然遵循上一章的步骤，先对LinkedList有个整体的认识，然后学习它的源码，深入剖析LinkedList。

LinkedList简介

    首先看看LinkedList与Collection的关系：

    LinkedList的继承关系如下：

[java] view plain copy

1. java.lang.Object  
2.    ↳     java.util.AbstractCollection<E>  
3.          ↳     java.util.AbstractList<E>  
4.                ↳     java.util.AbstractSequentialList<E>  
5.                      ↳     java.util.LinkedList<E>  
6.   
7. public class LinkedList<E>  
8.     extends AbstractSequentialList<E>  
9.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}  

        LinkedList是一个继承与AbatractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

        LinkedList实现了List接口，能对它进行队列操作。

        LinkedList实现了Deque接口，即能将LinkedList当作双端队列使用。

        LinkedList实现了Java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

        LinkedList是非同步的。

        这里插一句，简单说一下AbstractSequentialList，因为LinkedList是其子类。

        AbstractSequentialList实现了get(int index)、set(int index, E element)、add(int index, E element)和remove(int index)这些方法。这些接口都是随机访问List的，LinkedList是双向链表，既然它继承与AbstractSequentialList，就相当于已经实现了“get(int index)”这些接口，可以支持随机访问了。

        此外，如果我们需要通过AbstractSequentialList实现一个自己的列表，只需要扩展此类，并提供listIterator()和size()方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的hashNext、next、hashPrevious、previous和index方法即可。

    下面先总览一下LinkedList的构造函数和API:

[java] view plain copy

1. LinkedList的API  
2. boolean       add(E object)  
3. void          add(int location, E object)  
4. boolean       addAll(Collection<? extends E> collection)  
5. boolean       addAll(int location, Collection<? extends E> collection)  
6. void          addFirst(E object)  
7. void          addLast(E object)  
8. void          clear()  
9. Object        clone()  
10. boolean       contains(Object object)  
11. Iterator<E>   descendingIterator()  
12. E             element()  
13. E             get(int location)  
14. E             getFirst()  
15. E             getLast()  
16. int           indexOf(Object object)  
17. int           lastIndexOf(Object object)  
18. ListIterator<E>     listIterator(int location)  
19. boolean       offer(E o)  
20. boolean       offerFirst(E e)  
21. boolean       offerLast(E e)  
22. E             peek()  
23. E             peekFirst()  
24. E             peekLast()  
25. E             poll()  
26. E             pollFirst()  
27. E             pollLast()  
28. E             pop()  
29. void          push(E e)  
30. E             remove()  
31. E             remove(int location)  
32. boolean       remove(Object object)  
33. E             removeFirst()  
34. boolean       removeFirstOccurrence(Object o)  
35. E             removeLast()  
36. boolean       removeLastOccurrence(Object o)  
37. E             set(int location, E object)  
38. int           size()  
39. <T> T[]       toArray(T[] contents)  
40. Object[]     toArray()  

        LinkedList包含三个重要的成员：first、last和size：first是双向链表的表头，last是双向链表的尾节点，size是双向链表中的节点个数。

LinkedList源码分析（基于JDK1.7）

        下面通过分析LinkedList的源码更加深入的了解LinkedList原理。由于LinkedList是通过双向链表实现的，所以源码也比较容易理解：

[java] view plain copy

1. package java.util;  
2.   
3. /*双向链表*/  
4. public class LinkedList<E>  
5.     extends AbstractSequentialList<E>  
6.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
7. {  
8.     /** 
9.     * 这里先说一下transient关键字的用法： 
10.     * 一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，可以不必关系具体序列化的过程， 
11.     * 只要这个类实现了Serilizable接口，这个的所有属性和方法都会自动序列化。但是有种情况是有些属性是不需要序列号的，所以就用到这个关键字。 
12.     * 只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。 
13.     */  
14.     transient int size = 0; //LinkedList中元素的个数  
15.     transient Node<E> first; //链表的头结点  
16.     transient Node<E> last; //链表的尾节点  
17.   
18.     public LinkedList() { //默认构造函数，创建一个空链表  
19.     }  
20.   
21.     //按照c中的元素生成一个LinkedList  
22.     public LinkedList(Collection<? extends E> c) {  
23.         this();  
24.         addAll(c); //将c中的元素添加到空链表的尾部  
25.     }  
26.   
27.     /***************************** 添加头结点 ********************************/  
28.     public void addFirst(E e) {  
29.         linkFirst(e);  
30.     }  
31.   
32.     private void linkFirst(E e) {  
33.         final Node<E> f = first; //f指向头结点  
34.         //生成一个新结点e，其前向指针为null，后向指针为f    
35.         final Node<E> newNode = new Node<>(null, e, f);  
36.         first = newNode; //first指向新生成的结点，f保存着老的头结点信息    
37.         if (f == null)  
38.             last = newNode; //如果f为null，则表示整个链表目前是空的，则尾结点也指向新结点  
39.         else  
40.             f.prev = newNode;  
41.         size++;  
42.         modCount++; //修改次数+1  
43.     }  
44.   
45.     /****************** 添加尾节点，与上面添加头结点原理一样 ******************/  
46.     public void addLast(E e) {  
47.         linkLast(e);  
48.     }  
49.   
50.     void linkLast(E e) {  
51.         final Node<E> l = last;  
52.         final Node<E> newNode = new Node<>(l, e, null);  
53.         last = newNode;  
54.         if (l == null)  
55.             first = newNode;  
56.         else  
57.             l.next = newNode;  
58.         size++;  
59.         modCount++;  
60.     }  
61.   
62.     /****************** 在非空节点succ之前插入新节点e ************************/  
63.     void linkBefore(E e, Node<E> succ) {  
64.         // assert succ != null; //外界调用需保证succ不为null,否则程序会抛出空指针异常    
65.         final Node<E> pred = succ.prev;  
66.          //生成一个新结点e,其前向指针指向pred，后向指针指向succ    
67.         final Node<E> newNode = new Node<>(pred, e, succ);  
68.         succ.prev = newNode; //succ的前向指针指向newNode    
69.         if (pred == null)  
70.             //如果pred为null，则表示succ为头结点，此时头结点指向最新生成的结点newNode   
71.             first = newNode;  
72.         else  
73.             //pred的后向指针指向新生成的结点，此时已经完成了结点的插入操作  
74.             pred.next = newNode;  
75.         size++;  
76.         modCount++;  
77.     }  
78.   
79.     /*********************** 删除头结点,并返回头结点的值 *********************/  
80.     public E removeFirst() {  
81.         final Node<E> f = first;  
82.         if (f == null)  
83.             throw new NoSuchElementException();  
84.         return unlinkFirst(f); //private方法  
85.     }  
86.       
87.     private E unlinkFirst(Node<E> f) {  
88.         // assert f == first && f != null; //需确保f为头结点,且链表不为Null    
89.         final E element = f.item; //获得节点的值  
90.         final Node<E> next = f.next; //获得头结点下一个节点  
91.         f.item = null;  
92.         f.next = null; // help GC  
93.         first = next;  
94.         if (next == null)  
95.             //如果next为null，则表示f为last结点，此时链表即为空链表   
96.             last = null;  
97.         else  
98.             //修改next的前向指针，因为first结点的前向指针为null   
99.             next.prev = null;  
100.         size--;  
101.         modCount++;  
102.         return element;  
103.     }  
104.   
105.     /********************** 删除尾节点，并返回尾节点的值 ********************/  
106.     public E removeLast() {  
107.         final Node<E> l = last;  
108.         if (l == null)  
109.             throw new NoSuchElementException();  
110.         return unlinkLast(l); //private方法  
111.     }  
112.   
113.     private E unlinkLast(Node<E> l) {  
114.         // assert l == last && l != null;  
115.         final E element = l.item;  
116.         final Node<E> prev = l.prev;  
117.         l.item = null;  
118.         l.prev = null; // help GC  
119.         last = prev;  
120.         if (prev == null)  
121.             first = null;  
122.         else  
123.             prev.next = null;  
124.         size--;  
125.         modCount++;  
126.         return element;  
127.     }  
128.   
129.     /******************** 删除为空节点x，并返回该节点的值 ******************/  
130.     E unlink(Node<E> x) {  
131.         // assert x != null; //需确保x不为null，否则后续操作会抛出空指针异常    
132.         final E element = x.item;  
133.         final Node<E> next = x.next;  
134.         final Node<E> prev = x.prev;  
135.   
136.         if (prev == null) {  
137.             //如果prev为空，则x结点为first结点，此时first结点指向next结点（x的后向结点）  
138.             first = next;  
139.         } else {  
140.             prev.next = next; //x的前向结点的后向指针指向x的后向结点    
141.             x.prev = null; //释放x的前向指针    
142.         }  
143.   
144.         if (next == null) {  
145.             //如果next结点为空，则x结点为尾部结点，此时last结点指向prev结点(x的前向结点)  
146.             last = prev;  
147.         } else {  
148.             next.prev = prev; //x的后向结点的前向指针指向x的前向结点  
149.             x.next = null; //释放x的后向指针    
150.         }  
151.   
152.         x.item = null; //释放x的值节点,此时x节点可以完全被GC回收    
153.         size--;  
154.         modCount++;  
155.         return element;  
156.     }  
157.   
158.     /********************** 获得头结点的值 ********************/  
159.     public E getFirst() {  
160.         final Node<E> f = first;  
161.         if (f == null)  
162.             throw new NoSuchElementException();  
163.         return f.item;  
164.     }  
165.   
166.     /********************** 获得尾结点的值 ********************/  
167.     public E getLast() {  
168.         final Node<E> l = last;  
169.         if (l == null)  
170.             throw new NoSuchElementException();  
171.         return l.item;  
172.     }  
173.   
174.     /*************** 判断元素（值为o）是否在链表中 *************/  
175.     public boolean contains(Object o) {  
176.         return indexOf(o) != -1; //定位元素  
177.     }  
178.   
179.     //返回元素个数  
180.     public int size() {  
181.         return size;  
182.     }  
183.   
184.     //向链表尾部添加元素e  
185.     public boolean add(E e) {  
186.         linkLast(e);  
187.         return true;  
188.     }  
189.   
190.     /*************** 删除值为o的元素 *************/  
191.     public boolean remove(Object o) {  
192.         if (o == null) {  
193.             for (Node<E> x = first; x != null; x = x.next) {  
194.                 if (x.item == null) { //找到即返回  
195.                     unlink(x);  
196.                     return true;  
197.                 }  
198.             }  
199.         } else {//o不为空  
200.             for (Node<E> x = first; x != null; x = x.next) {  
201.                 if (o.equals(x.item)) {  
202.                     unlink(x);  
203.                     return true;  
204.                 }  
205.             }  
206.         }  
207.         return false;  
208.     }  
209.   
210.     /*************** 将集合e中所有元素添加到链表中 *************/  
211.     public boolean addAll(Collection<? extends E> c) {  
212.         return addAll(size, c);  
213.     }  
214.     //从index开始，向后添加的  
215.     public boolean addAll(int index, Collection<? extends E> c) {  
216.         checkPositionIndex(index); //判断index是否越界  
217.   
218.         Object[] a = c.toArray(); //将集合c转换为数组  
219.         int numNew = a.length;  
220.         if (numNew == 0)  
221.             return false;  
222.   
223.         Node<E> pred, succ;  
224.         if (index == size) {//即index个节点在尾节点后面  
225.             succ = null;  
226.             pred = last; //pred指向尾节点  
227.         } else {  
228.             succ = node(index); //succ指向第index个节点  
229.             pred = succ.prev; //pred指向succ的前向节点  
230.         }  
231.   
232.         //for循环结束后，a里面的元素都添加到当前链表里了，向后添加  
233.         for (Object o : a) {  
234.             @SuppressWarnings("unchecked") E e = (E) o;  
235.             Node<E> newNode = new Node<>(pred, e, null);  
236.             if (pred == null)  
237.                 first = newNode; //如果pred为null，则succ为头结点  
238.             else  
239.                 pred.next = newNode; //pred的后向指针指向新节点  
240.             pred = newNode; //pred指向新节点，即往后移动一个节点，用于下一次循环  
241.         }  
242.   
243.         if (succ == null) { //succ为null表示index为尾节点之后  
244.             last = pred;  
245.         } else {  
246.             //pred表示所有元素添加好之后的最后那个节点，此时pred的后向指针指向之前记录的节点，即index处的节点  
247.             pred.next = succ;  
248.             succ.prev = pred; //之前记录的结点指向添加元素之后的最后结点  
249.         }  
250.   
251.         size += numNew;  
252.         modCount++;  
253.         return true;  
254.     }  
255.   
256.     /******************** 清空链表 *************************/  
257.     public void clear() {  
258.         for (Node<E> x = first; x != null; ) {  
259.             Node<E> next = x.next;  
260.             x.item = null; //释放值结点，便于GC回收    
261.             x.next = null; //释放前向指针    
262.             x.prev = null; //释放前后指针    
263.             x = next; //后向遍历    
264.         }  
265.         first = last = null; //释放头尾节点  
266.         size = 0;  
267.         modCount++;  
268.     }  
269.   
270.   
271.     /******************* Positional Access Operations ***********************/  
272.   
273.     //获得第index个节点的值  
274.     public E get(int index) {  
275.         checkElementIndex(index);  
276.         return node(index).item;  
277.     }  
278.   
279.     //设置第index元素的值  
280.     public E set(int index, E element) {  
281.         checkElementIndex(index);  
282.         Node<E> x = node(index);  
283.         E oldVal = x.item;  
284.         x.item = element;  
285.         return oldVal;  
286.     }  
287.   
288.     //在index个节点之前添加新的节点  
289.     public void add(int index, E element) {  
290.         checkPositionIndex(index);  
291.   
292.         if (index == size)  
293.             linkLast(element);  
294.         else  
295.             linkBefore(element, node(index));  
296.     }  
297.   
298.     //删除第index个节点  
299.     public E remove(int index) {  
300.         checkElementIndex(index);  
301.         return unlink(node(index));  
302.     }  
303.   
304.     //判断index是否为链表中的元素下标  
305.     private boolean isElementIndex(int index) {  
306.         return index >= 0 && index < size;  
307.     }  
308.   
309.     //判断index是否为链表中的元素下标。。。包含了size  
310.     private boolean isPositionIndex(int index) {  
311.         return index >= 0 && index <= size;  
312.     }  
313.   
314.     private String outOfBoundsMsg(int index) {  
315.         return "Index: "+index+", Size: "+size;  
316.     }  
317.   
318.     private void checkElementIndex(int index) {  
319.         if (!isElementIndex(index))  
320.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
321.     }  
322.   
323.     private void checkPositionIndex(int index) {  
324.         if (!isPositionIndex(index))  
325.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
326.     }  
327.   
328.     //定位index处的节点  
329.     Node<E> node(int index) {  
330.         // assert isElementIndex(index);  
331.         //index<size/2时，从头开始找  
332.         if (index < (size >> 1)) {  
333.             Node<E> x = first;  
334.             for (int i = 0; i < index; i++)  
335.                 x = x.next;  
336.             return x;  
337.         } else { //index>=size/2时，从尾开始找  
338.             Node<E> x = last;  
339.             for (int i = size - 1; i > index; i--)  
340.                 x = x.prev;  
341.             return x;  
342.         }  
343.     }  
344.   
345.     /*************************** Search Operations *************************/  
346.   
347.     //返回首次出现指定元素值o的节点索引  
348.     public int indexOf(Object o) {  
349.         int index = 0;  
350.         if (o == null) {  
351.             for (Node<E> x = first; x != null; x = x.next) {  
352.                 if (x.item == null)  
353.                     return index;  
354.                 index++;  
355.             }  
356.         } else {  
357.             for (Node<E> x = first; x != null; x = x.next) {  
358.                 if (o.equals(x.item))  
359.                     return index;  
360.                 index++;  
361.             }  
362.         }  
363.         return -1; //没有则返回-1  
364.     }  
365.   
366.     //返回最后一次出现指定元素值o的节点索引  
367.     public int lastIndexOf(Object o) {  
368.         int index = size;  
369.         if (o == null) {  
370.             for (Node<E> x = last; x != null; x = x.prev) {  
371.                 index--;  
372.                 if (x.item == null)  
373.                     return index;  
374.             }  
375.         } else {  
376.             for (Node<E> x = last; x != null; x = x.prev) {  
377.                 index--;  
378.                 if (o.equals(x.item))  
379.                     return index;  
380.             }  
381.         }  
382.         return -1;  
383.     }  
384.   
385.     /***************************** Queue operations ***********************/  
386.     //下面是与栈和队列相关的操作了  
387.     //实现栈的操作，返回第一个元素的值  
388.     public E peek() {  
389.         final Node<E> f = first;  
390.         return (f == null) ? null : f.item; //不删除  
391.     }  
392.   
393.     //实现队列操作，返回第一个节点  
394.     public E element() {  
395.         return getFirst();  
396.     }  
397.   
398.     //实现栈的操作，弹出第一个节点  
399.     public E poll() {  
400.         final Node<E> f = first;  
401.         return (f == null) ? null : unlinkFirst(f); //删除  
402.     }  
403.   
404.     //实现队列操作，删除节点  
405.     public E remove() {  
406.         return removeFirst();  
407.     }  
408.   
409.     //添加节点  
410.     public boolean offer(E e) {  
411.         return add(e);  
412.     }  
413.   
414.     /************************* Deque operations **********************/  
415.     //下面都是和双端队列相关的操作了  
416.     //添加头结点  
417.     public boolean offerFirst(E e) {  
418.         addFirst(e);  
419.         return true;  
420.     }  
421.   
422.     //添加尾节点  
423.     public boolean offerLast(E e) {  
424.         addLast(e);  
425.         return true;  
426.     }  
427.   
428.     //返回头结点的值  
429.     public E peekFirst() {  
430.         final Node<E> f = first;  
431.         return (f == null) ? null : f.item;  
432.      }  
433.   
434.     //返回尾节点的值  
435.     public E peekLast() {  
436.         final Node<E> l = last;  
437.         return (l == null) ? null : l.item;  
438.     }  
439.   
440.     //弹出头结点  
441.     public E pollFirst() {  
442.         final Node<E> f = first;  
443.         return (f == null) ? null : unlinkFirst(f); //删除  
444.     }  
445.   
446.     //弹出尾节点  
447.     public E pollLast() {  
448.         final Node<E> l = last;  
449.         return (l == null) ? null : unlinkLast(l); //删除  
450.     }  
451.   
452.     //栈操作，添加头结点  
453.     public void push(E e) {  
454.         addFirst(e);  
455.     }  
456.   
457.     //栈操作，删除头结点  
458.     public E pop() {  
459.         return removeFirst();  
460.     }  
461.   
462.     //删除第一次出现o的节点  
463.     public boolean removeFirstOccurrence(Object o) {  
464.         return remove(o);  
465.     }  
466.   
467.     //删除最后一次出现o的节点  
468.     public boolean removeLastOccurrence(Object o) {  
469.         if (o == null) {  
470.             for (Node<E> x = last; x != null; x = x.prev) {  
471.                 if (x.item == null) {  
472.                     unlink(x);  
473.                     return true;  
474.                 }  
475.             }  
476.         } else {  
477.             for (Node<E> x = last; x != null; x = x.prev) {  
478.                 if (o.equals(x.item)) {  
479.                     unlink(x);  
480.                     return true;  
481.                 }  
482.             }  
483.         }  
484.         return false;  
485.     }  
486.   
487.     /************************* ListIterator ***********************/  
488.       
489.     public ListIterator<E> listIterator(int index) {  
490.         checkPositionIndex(index);  
491.         return new ListItr(index); //ListItr是一个双向迭代器  
492.     }  
493.   
494.     //实现双向迭代器  
495.     private class ListItr implements ListIterator<E> {  
496.         private Node<E> lastReturned = null;//记录当前节点信息  
497.         private Node<E> next; //当前节点的后向节点  
498.         private int nextIndex; //当前节点的索引  
499.         private int expectedModCount = modCount; //修改次数  
500.   
501.         ListItr(int index) {  
502.             // assert isPositionIndex(index);  
503.             next = (index == size) ? null : node(index);  
504.             nextIndex = index;  
505.         }  
506.   
507.         public boolean hasNext() {  
508.             return nextIndex < size;  
509.         }  
510.   
511.         public E next() {  
512.             checkForComodification();  
513.             if (!hasNext())  
514.                 throw new NoSuchElementException();  
515.   
516.             lastReturned = next; //记录当前节点  
517.             next = next.next; //向后移动一个位置  
518.             nextIndex++; //节点索引+1  
519.             return lastReturned.item; //返回当前节点的值  
520.         }  
521.   
522.         public boolean hasPrevious() {  
523.             return nextIndex > 0;  
524.         }  
525.   
526.         //返回前向节点的值  
527.         public E previous() {  
528.             checkForComodification();  
529.             if (!hasPrevious())  
530.                 throw new NoSuchElementException();  
531.   
532.             lastReturned = next = (next == null) ? last : next.prev;  
533.             nextIndex--;  
534.             return lastReturned.item;  
535.         }  
536.   
537.         public int nextIndex() { //返回当前节点的索引  
538.             return nextIndex;  
539.         }  
540.   
541.         public int previousIndex() { //返回当前节点的前一个索引  
542.             return nextIndex - 1;  
543.         }  
544.   
545.         public void remove() { //删除当前节点  
546.             checkForComodification();  
547.             if (lastReturned == null)  
548.                 throw new IllegalStateException();  
549.   
550.             Node<E> lastNext = lastReturned.next;  
551.             unlink(lastReturned);  
552.             if (next == lastReturned)  
553.                 next = lastNext;  
554.             else  
555.                 nextIndex--;  
556.             lastReturned = null;  
557.             expectedModCount++;  
558.         }  
559.   
560.         public void set(E e) { //设置当前节点的值  
561.             if (lastReturned == null)  
562.                 throw new IllegalStateException();  
563.             checkForComodification();  
564.             lastReturned.item = e;  
565.         }  
566.   
567.         //在当前节点前面插入新节点信息  
568.         public void add(E e) {  
569.             checkForComodification();  
570.             lastReturned = null;  
571.             if (next == null)  
572.                 linkLast(e);  
573.             else  
574.                 linkBefore(e, next);  
575.             nextIndex++;  
576.             expectedModCount++;  
577.         }  
578.   
579.         final void checkForComodification() {  
580.             if (modCount != expectedModCount)  
581.                 throw new ConcurrentModificationException();  
582.         }  
583.     }  
584.   
585.     private static class Node<E> {  
586.         E item;  
587.         Node<E> next;  
588.         Node<E> prev;  
589.   
590.         Node(Node<E> prev, E element, Node<E> next) {  
591.             this.item = element;  
592.             this.next = next;  
593.             this.prev = prev;  
594.         }  
595.     }  
596.   
597.     //返回前向迭代器  
598.     public Iterator<E> descendingIterator() {  
599.         return new DescendingIterator();  
600.     }  
601.   
602.     //通过ListItr.previous来提供前向迭代器，方向与原来相反  
603.     private class DescendingIterator implements Iterator<E> {  
604.         private final ListItr itr = new ListItr(size());  
605.         public boolean hasNext() {  
606.             return itr.hasPrevious();  
607.         }  
608.         public E next() {  
609.             return itr.previous();  
610.         }  
611.         public void remove() {  
612.             itr.remove();  
613.         }  
614.     }  
615.   
616.     @SuppressWarnings("unchecked")  
617.     private LinkedList<E> superClone() {  
618.         try {  
619.             return (LinkedList<E>) super.clone();  
620.         } catch (CloneNotSupportedException e) {  
621.             throw new InternalError();  
622.         }  
623.     }  
624.   
625.     //克隆操作，执行浅拷贝，只复制引用，没有复制引用指向的内存  
626.     public Object clone() {  
627.         LinkedList<E> clone = superClone();  
628.   
629.         // Put clone into "virgin" state  
630.         clone.first = clone.last = null;  
631.         clone.size = 0;  
632.         clone.modCount = 0;  
633.   
634.         // Initialize clone with our elements  
635.         for (Node<E> x = first; x != null; x = x.next)  
636.             clone.add(x.item);  
637.   
638.         return clone;  
639.     }  
640.   
641.     /*************************** toArray ****************************/  
642.     //返回LinkedList的Object[]数组  
643.     public Object[] toArray() {  
644.         Object[] result = new Object[size];  
645.         int i = 0;  
646.         for (Node<E> x = first; x != null; x = x.next)  
647.             result[i++] = x.item;  
648.         return result;  
649.     }  
650.   
651.     //返回LinkedList的模板数组，存储在a中  
652.     @SuppressWarnings("unchecked")  
653.     public <T> T[] toArray(T[] a) {  
654.         if (a.length < size)  
655.             //如果a的大小 < LinkedList的元素个数，意味着数组a不能容纳LinkedList的全部元素  
656.             //则新建一个T[]数组，T[]的大小为LinkedList大小，并将T[]赋给a  
657.             a = (T[])java.lang.reflect.Array.newInstance(  
658.                                 a.getClass().getComponentType(), size);  
659.         //如果a大小够容纳LinkedList的全部元素  
660.         int i = 0;  
661.         Object[] result = a;  
662.         for (Node<E> x = first; x != null; x = x.next)  
663.             result[i++] = x.item;  
664.   
665.         if (a.length > size)  
666.             a[size] = null;  
667.   
668.         return a;  
669.     }  
670.   
671.     private static final long serialVersionUID = 876323262645176354L;  
672.   
673.     /************************* Serializable **************************/  
674.     //java.io.Serializable的写入函数  
675.     //将LinkedList的“容量，所有元素值”写入到输出流中  
676.     private void writeObject(java.io.ObjectOutputStream s)  
677.         throws java.io.IOException {  
678.         // Write out any hidden serialization magic  
679.         s.defaultWriteObject();  
680.   
681.         // Write out size  
682.         s.writeInt(size); //写入容量  
683.   
684.         // Write out all elements in the proper order.  
685.         for (Node<E> x = first; x != null; x = x.next) //写入所有数据  
686.             s.writeObject(x.item);  
687.     }  
688.   
689.     //java.io.Serializable的读取函数：根据写入方式反向读出  
690.     //先将LinkedList的“容量”读出，然后将“所有元素值”读出  
691.     @SuppressWarnings("unchecked")  
692.     private void readObject(java.io.ObjectInputStream s)  
693.         throws java.io.IOException, ClassNotFoundException {  
694.         // Read in any hidden serialization magic  
695.         s.defaultReadObject();  
696.   
697.         // Read in size  
698.         int size = s.readInt(); //读出容量  
699.   
700.         // Read in all elements in the proper order.  
701.         for (int i = 0; i < size; i++) //读出所有元素值  
702.             linkLast((E)s.readObject());  
703.     }  
704. }  

    总结一下：

        1）. LinkedList是通过双向链表去实现的。

        2）. 从LinkedList的实现方式中可以看出，它不存在容量不足的问题，因为是链表。

        3）. LinkedList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写出“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

        4）. LinkdedList的克隆函数，即是将全部元素克隆到一个新的LinkedList中。

        5）. 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。

        6）. LinkedList可以作为FIFO（先进先出）的队列，作为FIFO的队列时，下标的方法等价：

[java] view plain copy

1. 队列方法       等效方法  
2. add(e)        addLast(e)  
3. offer(e)      offerLast(e)  
4. remove()      removeFirst()  
5. poll()        pollFirst()  
6. element()     getFirst()  
7. peek()        peekFirst()  

    7）. LinkedList可以作为LIFO（后进先出）的栈，作为LIFO的栈时，下表的方法等价：

[java] view plain copy

1. 栈方法        等效方法  
2. push(e)      addFirst(e)  
3. pop()        removeFirst()  
4. peek()       peekFirst()  

LinkedList遍历方式

        LinkedList支持多种遍历方式，建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。下面我们来看看每种遍历方式：

    1）. 通过Iterator迭代器遍历

[java] view plain copy

1. for(Iterator iter = list.iterator(); iter.hasNext();)  
2.     iter.next();  

    2）. 通过快速随机访问遍历

[java] view plain copy

1. int size = list.size();  
2.     for (int i=0; i<size; i++) {  
3.         list.get(i);          
4. }  

    3）. 通过for循环遍历

[java] view plain copy

1. for (Integer integ:list)   
2.     ;  

    4）. 通过pollFirst()或pollLast()来遍历

[java] view plain copy

1. while(list.pollFirst() != null)  
2.     ;  
3. while(list.pollLast() != null)  
4.     ;  

    5）. 通过removeFirst()或removeLast()来遍历

[java] view plain copy

1. while(list.removeFirst() != null)  
2.         ;  
3. while(list.removeLast() != null)  
4.         ;  

    下面通过一个测试用例来测试一下这些方法的效率：

[java] view plain copy

1. import java.util.Iterator;  
2. import java.util.LinkedList;  
3. import java.util.NoSuchElementException;  
4.   
5. /* 
6.  * @description 测试LinkedList的几种遍历方式和效率 
7.  * @author eson_15 
8.  */  
9. public class LinkedListThruTest {  
10.     public static void main(String[] args) {  
11.         // 通过Iterator遍历LinkedList  
12.         iteratorLinkedListThruIterator(getLinkedList()) ;  
13.           
14.         // 通过快速随机访问遍历LinkedList  
15.         iteratorLinkedListThruForeach(getLinkedList()) ;  
16.   
17.         // 通过for循环的变种来访问遍历LinkedList  
18.         iteratorThroughFor2(getLinkedList()) ;  
19.   
20.         // 通过PollFirst()遍历LinkedList  
21.         iteratorThroughPollFirst(getLinkedList()) ;  
22.   
23.         // 通过PollLast()遍历LinkedList  
24.         iteratorThroughPollLast(getLinkedList()) ;  
25.   
26.         // 通过removeFirst()遍历LinkedList  
27.         iteratorThroughRemoveFirst(getLinkedList()) ;  
28.   
29.         // 通过removeLast()遍历LinkedList  
30.         iteratorThroughRemoveLast(getLinkedList()) ;  
31.     }  
32.       
33.     private static LinkedList<Integer> getLinkedList() {  
34.         LinkedList<Integer> llist = new LinkedList<Integer>();  
35.         for (int i=0; i<500000; i++)  
36.             llist.addLast(i);  
37.   
38.         return llist;  
39.     }  
40.     /** 
41.      * 通过快迭代器遍历LinkedList 
42.      */  
43.     private static void iteratorLinkedListThruIterator(LinkedList<Integer> list) {  
44.         if (list == null)  
45.             return ;  
46.         long start = System.currentTimeMillis();  
47.           
48.         for(Iterator<Integer> iter = list.iterator(); iter.hasNext();)  
49.             iter.next();  
50.         long end = System.currentTimeMillis();  
51.         long interval = end - start;  
52.         System.out.println("iteratorLinkedListThruIterator：" + interval+" ms");  
53.     }  
54.   
55.     /** 
56.      * 通过快速随机访问遍历LinkedList 
57.      */  
58.     private static void iteratorLinkedListThruForeach(LinkedList<Integer> list) {  
59.         if (list == null)  
60.             return ;  
61.         long start = System.currentTimeMillis();   
62.         int size = list.size();  
63.         for (int i=0; i<size; i++) {  
64.             list.get(i);          
65.         }  
66.         long end = System.currentTimeMillis();  
67.         long interval = end - start;  
68.         System.out.println("iteratorLinkedListThruForeach：" + interval+" ms");  
69.     }  
70.   
71.     /** 
72.      * 通过另外一种for循环来遍历LinkedList 
73.      */  
74.     private static void iteratorThroughFor2(LinkedList<Integer> list) {  
75.         if (list == null)  
76.             return ;  
77.         long start = System.currentTimeMillis();  
78.           
79.         for (Integer integ : list)   
80.             ;  
81.         long end = System.currentTimeMillis();  
82.         long interval = end - start;  
83.         System.out.println("iteratorThroughFor2：" + interval+" ms");  
84.     }  
85.   
86.     /** 
87.      * 通过pollFirst()来遍历LinkedList 
88.      */  
89.     private static void iteratorThroughPollFirst(LinkedList<Integer> list) {  
90.         if (list == null)  
91.             return ;  
92.         long start = System.currentTimeMillis();  
93.         while(list.pollFirst() != null)  
94.             ;  
95.         long end = System.currentTimeMillis();  
96.         long interval = end - start;  
97.         System.out.println("iteratorThroughPollFirst：" + interval+" ms");  
98.     }  
99.   
100.     /** 
101.      * 通过pollLast()来遍历LinkedList 
102.      */  
103.     private static void iteratorThroughPollLast(LinkedList<Integer> list) {  
104.         if (list == null)  
105.             return ;  
106.         long start = System.currentTimeMillis();  
107.         while(list.pollLast() != null)  
108.             ;  
109.         long end = System.currentTimeMillis();  
110.         long interval = end - start;  
111.         System.out.println("iteratorThroughPollLast：" + interval+" ms");  
112.     }  
113.   
114.     /** 
115.      * 通过removeFirst()来遍历LinkedList 
116.      */  
117.     private static void iteratorThroughRemoveFirst(LinkedList<Integer> list) {  
118.         if (list == null)  
119.             return ;  
120.         long start = System.currentTimeMillis();  
121.         try {  
122.             while(list.removeFirst() != null)  
123.                 ;  
124.         } catch (NoSuchElementException e) {  
125.         }  
126.         long end = System.currentTimeMillis();  
127.         long interval = end - start;  
128.         System.out.println("iteratorThroughRemoveFirst：" + interval+" ms");  
129.     }  
130.   
131.     /** 
132.      * 通过removeLast()来遍历LinkedList 
133.      */  
134.     private static void iteratorThroughRemoveLast(LinkedList<Integer> list) {  
135.         if (list == null)  
136.             return ;  
137.         long start = System.currentTimeMillis();  
138.         try {  
139.             while(list.removeLast() != null)  
140.                 ;  
141.         } catch (NoSuchElementException e) {  
142.         }  
143.         long end = System.currentTimeMillis();  
144.         long interval = end - start;  
145.         System.out.println("iteratorThroughRemoveLast：" + interval+" ms");  
146.     }  
147.   
148. }  

    测试结果如下：

[java] view plain copy

1. iteratorLinkedListThruIterator：10 ms  
2. iteratorLinkedListThruForeach：414648 ms  
3. iteratorThroughFor2：10 ms  
4. iteratorThroughPollFirst：8 ms  
5. iteratorThroughPollLast：10 ms  
6. iteratorThroughRemoveFirst：7 ms  
7. iteratorThroughRemoveLast：6 ms  

        由此可见，遍历LinkedList时，使用removeFirst()或removeLast()效率最高。但是用它们遍历会删除原始数据；若只是单纯的取数据，而不删除，建议用迭代器方式或者for-each方式。

        无论如何，千万不要用随机访问去遍历LinkedList！除非脑门儿被驴给踢了... ...

        LinkedList源码就讨论这么多，如果错误，欢迎留言指正~

转载：http://blog.csdn.net/eson_15/article/details/51135944