程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> java集合框架04——LinkedList和源碼分析

java集合框架04——LinkedList和源碼分析

編輯：JAVA綜合教程

java集合框架04——LinkedList和源碼分析

上一章學習了ArrayList，並分析了其源碼，這一章我們將對LinkedList的具體實現進行詳細的學習。依然遵循上一章的步驟，先對LinkedList有個整體的認識，然後學習它的源碼，深入剖析LinkedList。

LinkedList簡介

首先看看LinkedList與Collection的關系：

LinkedList的繼承關系如下：

java.lang.Object
   ?     java.util.AbstractCollection
         ?     java.util.AbstractList
               ?     java.util.AbstractSequentialList
                     ?     java.util.LinkedList

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, 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:

LinkedList的API
boolean       add(E object)
void          add(int location, E object)
boolean       addAll(Collection collection)
boolean       addAll(int location, Collection collection)
void          addFirst(E object)
void          addLast(E object)
void          clear()
Object        clone()
boolean       contains(Object object)
Iterator   descendingIterator()
E             element()
E             get(int location)
E             getFirst()
E             getLast()
int           indexOf(Object object)
int           lastIndexOf(Object object)
ListIterator     listIterator(int location)
boolean       offer(E o)
boolean       offerFirst(E e)
boolean       offerLast(E e)
E             peek()
E             peekFirst()
E             peekLast()
E             poll()
E             pollFirst()
E             pollLast()
E             pop()
void          push(E e)
E             remove()
E             remove(int location)
boolean       remove(Object object)
E             removeFirst()
boolean       removeFirstOccurrence(Object o)
E             removeLast()
boolean       removeLastOccurrence(Object o)
E             set(int location, E object)
int           size()
T[]       toArray(T[] contents)
Object[]     toArray()

LinkedList包含三個重要的成員：first、last和size：first是雙向鏈表的表頭，last是雙向鏈表的尾節點，size是雙向鏈表中的節點個數。

LinkedList源碼分析（基於JDK1.7）

下面通過分析LinkedList的源碼更加深入的了解LinkedList原理。由於LinkedList是通過雙向鏈表實現的，所以源碼也比較容易理解：

package java.util;

/*雙向鏈表*/
public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
	/**
	* 這裡先說一下transient關鍵字的用法：
	* 一個對象只要實現了Serilizable接口，這個對象就可以被序列化，java的這種序列化模式為開發者提供了很多便利，可以不必關系具體序列化的過程，
	* 只要這個類實現了Serilizable接口，這個的所有屬性和方法都會自動序列化。但是有種情況是有些屬性是不需要序列號的，所以就用到這個關鍵字。
	* 只需要實現Serilizable接口，將不需要序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。
	*/
    transient int size = 0; //LinkedList中元素的個數
    transient Node first; //鏈表的頭結點
    transient Node last; //鏈表的尾節點

    public LinkedList() { //默認構造函數，創建一個空鏈表
    }

    //按照c中的元素生成一個LinkedList
    public LinkedList(Collection c) {
        this();
        addAll(c); //將c中的元素添加到空鏈表的尾部
    }

    /***************************** 添加頭結點 ********************************/
	public void addFirst(E e) {
        linkFirst(e);
    }

    private void linkFirst(E e) {
        final Node f = first; //f指向頭結點
		//生成一個新結點e，其前向指針為null，後向指針為f  
        final Node newNode = new Node<>(null, e, f);
        first = newNode; //first指向新生成的結點，f保存著老的頭結點信息  
        if (f == null)
            last = newNode; //如果f為null，則表示整個鏈表目前是空的，則尾結點也指向新結點
        else
            f.prev = newNode;
        size++;
        modCount++; //修改次數+1
    }

    /****************** 添加尾節點，與上面添加頭結點原理一樣 ******************/
	public void addLast(E e) {
        linkLast(e);
    }

    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /****************** 在非空節點succ之前插入新節點e ************************/
    void linkBefore(E e, Node succ) {
        // assert succ != null; //外界調用需保證succ不為null,否則程序會拋出空指針異常  
        final Node pred = succ.prev;
		 //生成一個新結點e,其前向指針指向pred，後向指針指向succ  
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode; //succ的前向指針指向newNode  
        if (pred == null)
			//如果pred為null，則表示succ為頭結點，此時頭結點指向最新生成的結點newNode 
            first = newNode;
        else
			//pred的後向指針指向新生成的結點，此時已經完成了結點的插入操作
            pred.next = newNode;
        size++;
        modCount++;
    }

    /*********************** 刪除頭結點,並返回頭結點的值 *********************/
    public E removeFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f); //private方法
    }
    
    private E unlinkFirst(Node f) {
        // assert f == first && f != null; //需確保f為頭結點,且鏈表不為Null  
        final E element = f.item; //獲得節點的值
        final Node next = f.next; //獲得頭結點下一個節點
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
			//如果next為null，則表示f為last結點，此時鏈表即為空鏈表 
            last = null;
        else
			//修改next的前向指針，因為first結點的前向指針為null 
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    /********************** 刪除尾節點，並返回尾節點的值 ********************/
	public E removeLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l); //private方法
    }

    private E unlinkLast(Node l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    /******************** 刪除為空節點x，並返回該節點的值 ******************/
    E unlink(Node x) {
        // assert x != null; //需確保x不為null，否則後續操作會拋出空指針異常  
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;

        if (prev == null) {
			//如果prev為空，則x結點為first結點，此時first結點指向next結點（x的後向結點）
            first = next;
        } else {
            prev.next = next; //x的前向結點的後向指針指向x的後向結點  
            x.prev = null; //釋放x的前向指針  
        }

        if (next == null) {
			//如果next結點為空，則x結點為尾部結點，此時last結點指向prev結點(x的前向結點)
            last = prev;
        } else {
            next.prev = prev; //x的後向結點的前向指針指向x的前向結點
            x.next = null; //釋放x的後向指針  
        }

        x.item = null; //釋放x的值節點,此時x節點可以完全被GC回收  
        size--;
        modCount++;
        return element;
    }

    /********************** 獲得頭結點的值 ********************/
    public E getFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    /********************** 獲得尾結點的值 ********************/
    public E getLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    /*************** 判斷元素（值為o）是否在鏈表中 *************/
    public boolean contains(Object o) {
        return indexOf(o) != -1; //定位元素
    }

    //返回元素個數
    public int size() {
        return size;
    }

    //向鏈表尾部添加元素e
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /*************** 刪除值為o的元素 *************/
    public boolean remove(Object o) {
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null) { //找到即返回
                    unlink(x);
                    return true;
                }
            }
        } else {//o不為空
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /*************** 將集合e中所有元素添加到鏈表中 *************/
    public boolean addAll(Collection c) {
        return addAll(size, c);
    }
	//從index開始，向後添加的
    public boolean addAll(int index, Collection c) {
        checkPositionIndex(index); //判斷index是否越界

        Object[] a = c.toArray(); //將集合c轉換為數組
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node pred, succ;
        if (index == size) {//即index個節點在尾節點後面
            succ = null;
            pred = last; //pred指向尾節點
        } else {
            succ = node(index); //succ指向第index個節點
            pred = succ.prev; //pred指向succ的前向節點
        }

		//for循環結束後，a裡面的元素都添加到當前鏈表裡了，向後添加
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode; //如果pred為null，則succ為頭結點
            else
                pred.next = newNode; //pred的後向指針指向新節點
            pred = newNode; //pred指向新節點，即往後移動一個節點，用於下一次循環
        }

        if (succ == null) { //succ為null表示index為尾節點之後
            last = pred;
        } else {
			//pred表示所有元素添加好之後的最後那個節點，此時pred的後向指針指向之前記錄的節點，即index處的節點
            pred.next = succ;
            succ.prev = pred; //之前記錄的結點指向添加元素之後的最後結點
        }

        size += numNew;
        modCount++;
        return true;
    }

    /******************** 清空鏈表 *************************/
    public void clear() {
        for (Node x = first; x != null; ) {
            Node next = x.next;
            x.item = null; //釋放值結點，便於GC回收  
            x.next = null; //釋放前向指針  
            x.prev = null; //釋放前後指針  
            x = next; //後向遍歷  
        }
        first = last = null; //釋放頭尾節點
        size = 0;
        modCount++;
    }


    /******************* Positional Access Operations ***********************/

    //獲得第index個節點的值
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    //設置第index元素的值
    public E set(int index, E element) {
        checkElementIndex(index);
        Node x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    //在index個節點之前添加新的節點
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    //刪除第index個節點
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    //判斷index是否為鏈表中的元素下標
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    //判斷index是否為鏈表中的元素下標。。。包含了size
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    //定位index處的節點
    Node node(int index) {
        // assert isElementIndex(index);
		//index> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { //index>=size/2時，從尾開始找
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /*************************** Search Operations *************************/

    //返回首次出現指定元素值o的節點索引
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1; //沒有則返回-1
    }

    //返回最後一次出現指定元素值o的節點索引
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

    /***************************** Queue operations ***********************/
    //下面是與棧和隊列相關的操作了
    //實現棧的操作，返回第一個元素的值
    public E peek() {
        final Node f = first;
        return (f == null) ? null : f.item; //不刪除
    }

    //實現隊列操作，返回第一個節點
    public E element() {
        return getFirst();
    }

    //實現棧的操作，彈出第一個節點
    public E poll() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f); //刪除
    }

    //實現隊列操作，刪除節點
    public E remove() {
        return removeFirst();
    }

    //添加節點
    public boolean offer(E e) {
        return add(e);
    }

    /************************* Deque operations **********************/
    //下面都是和雙端隊列相關的操作了
	//添加頭結點
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    //添加尾節點
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    //返回頭結點的值
    public E peekFirst() {
        final Node f = first;
        return (f == null) ? null : f.item;
     }

    //返回尾節點的值
    public E peekLast() {
        final Node l = last;
        return (l == null) ? null : l.item;
    }

    //彈出頭結點
    public E pollFirst() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f); //刪除
    }

    //彈出尾節點
    public E pollLast() {
        final Node l = last;
        return (l == null) ? null : unlinkLast(l); //刪除
    }

    //棧操作，添加頭結點
    public void push(E e) {
        addFirst(e);
    }

    //棧操作，刪除頭結點
    public E pop() {
        return removeFirst();
    }

    //刪除第一次出現o的節點
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    //刪除最後一次出現o的節點
    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /************************* ListIterator ***********************/
	
    public ListIterator listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index); //ListItr是一個雙向迭代器
    }

    //實現雙向迭代器
    private class ListItr implements ListIterator {
        private Node lastReturned = null;//記錄當前節點信息
        private Node next; //當前節點的後向節點
        private int nextIndex; //當前節點的索引
        private int expectedModCount = modCount; //修改次數

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next; //記錄當前節點
            next = next.next; //向後移動一個位置
            nextIndex++; //節點索引+1
            return lastReturned.item; //返回當前節點的值
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

		//返回前向節點的值
        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() { //返回當前節點的索引
            return nextIndex;
        }

        public int previousIndex() { //返回當前節點的前一個索引
            return nextIndex - 1;
        }

        public void remove() { //刪除當前節點
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) { //設置當前節點的值
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

		//在當前節點前面插入新節點信息
        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    //返回前向迭代器
    public Iterator descendingIterator() {
        return new DescendingIterator();
    }

    //通過ListItr.previous來提供前向迭代器，方向與原來相反
    private class DescendingIterator implements Iterator {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }

    @SuppressWarnings("unchecked")
    private LinkedList superClone() {
        try {
            return (LinkedList) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    //克隆操作，執行淺拷貝，只復制引用，沒有復制引用指向的內存
    public Object clone() {
        LinkedList clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }

    /*************************** toArray ****************************/
    //返回LinkedList的Object[]數組
	public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    //返回LinkedList的模板數組，存儲在a中
    @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        if (a.length < size)
			//如果a的大小 < LinkedList的元素個數，意味著數組a不能容納LinkedList的全部元素
			//則新建一個T[]數組，T[]的大小為LinkedList大小，並將T[]賦給a
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
		//如果a大小夠容納LinkedList的全部元素
        int i = 0;
        Object[] result = a;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

    private static final long serialVersionUID = 876323262645176354L;

    /************************* Serializable **************************/
    //java.io.Serializable的寫入函數
    //將LinkedList的“容量，所有元素值”寫入到輸出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size); //寫入容量

        // Write out all elements in the proper order.
        for (Node x = first; x != null; x = x.next) //寫入所有數據
            s.writeObject(x.item);
    }

    //java.io.Serializable的讀取函數：根據寫入方式反向讀出
    //先將LinkedList的“容量”讀出，然後將“所有元素值”讀出
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt(); //讀出容量

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++) //讀出所有元素值
            linkLast((E)s.readObject());
    }
}

總結一下：

1）. LinkedList是通過雙向鏈表去實現的。

2）.從LinkedList的實現方式中可以看出，它不存在容量不足的問題，因為是鏈表。

3）. LinkedList實現java.io.Serializable的方式。當寫入到輸出流時，先寫入“容量”，再依次寫出“每一個元素”；當讀出輸入流時，先讀取“容量”，再依次讀取“每一個元素”。

4）. LinkdedList的克隆函數，即是將全部元素克隆到一個新的LinkedList中。

5）.由於LinkedList實現了Deque，而Deque接口定義了在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。

6）. LinkedList可以作為FIFO（先進先出）的隊列，作為FIFO的隊列時，下標的方法等價：

隊列方法       等效方法
add(e)        addLast(e)
offer(e)      offerLast(e)
remove()      removeFirst()
poll()        pollFirst()
element()     getFirst()
peek()        peekFirst()

7）. LinkedList可以作為LIFO（後進先出）的棧，作為LIFO的棧時，下表的方法等價：

棧方法        等效方法
push(e)      addFirst(e)
pop()        removeFirst()
peek()       peekFirst()

LinkedList遍歷方式

LinkedList支持多種遍歷方式，建議不要采用隨機訪問的方式去遍歷LinkedList，而采用逐個遍歷的方式。下面我們來看看每種遍歷方式：

1）.通過Iterator迭代器遍歷

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

2）.通過快速隨機訪問遍歷

int size = list.size();
    for (int i=0; i 3）.通過for循環遍歷for (Integer integ:list) 
    ;
4）. 通過pollFirst()或pollLast()來遍歷

while(list.pollFirst() != null)
    ;
while(list.pollLast() != null)
    ;
5）.通過removeFirst()或removeLast()來遍歷

while(list.removeFirst() != null)
        ;
while(list.removeLast() != null)
        ;
下面通過一個測試用例來測試一下這些方法的效率：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/*
 * @description 測試LinkedList的幾種遍歷方式和效率
 * @author eson_15
 */
public class LinkedListThruTest {
    public static void main(String[] args) {
        // 通過Iterator遍歷LinkedList
        iteratorLinkedListThruIterator(getLinkedList()) ;
        
        // 通過快速隨機訪問遍歷LinkedList
        iteratorLinkedListThruForeach(getLinkedList()) ;

        // 通過for循環的變種來訪問遍歷LinkedList
        iteratorThroughFor2(getLinkedList()) ;

        // 通過PollFirst()遍歷LinkedList
        iteratorThroughPollFirst(getLinkedList()) ;

        // 通過PollLast()遍歷LinkedList
        iteratorThroughPollLast(getLinkedList()) ;

        // 通過removeFirst()遍歷LinkedList
        iteratorThroughRemoveFirst(getLinkedList()) ;

        // 通過removeLast()遍歷LinkedList
        iteratorThroughRemoveLast(getLinkedList()) ;
    }
    
    private static LinkedList getLinkedList() {
        LinkedList llist = new LinkedList();
        for (int i=0; i<500000; i++)
            llist.addLast(i);

        return llist;
    }
    /**
     * 通過快迭代器遍歷LinkedList
     */
    private static void iteratorLinkedListThruIterator(LinkedList list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        
        for(Iterator iter = list.iterator(); iter.hasNext();)
            iter.next();
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorLinkedListThruIterator：" + interval+" ms");
    }

    /**
     * 通過快速隨機訪問遍歷LinkedList
     */
    private static void iteratorLinkedListThruForeach(LinkedList list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis(); 
        int size = list.size();
        for (int i=0; i list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        
        for (Integer integ : list) 
            ;
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorThroughFor2：" + interval+" ms");
    }

    /**
     * 通過pollFirst()來遍歷LinkedList
     */
    private static void iteratorThroughPollFirst(LinkedList list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        while(list.pollFirst() != null)
            ;
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorThroughPollFirst：" + interval+" ms");
    }

    /**
     * 通過pollLast()來遍歷LinkedList
     */
    private static void iteratorThroughPollLast(LinkedList list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        while(list.pollLast() != null)
            ;
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorThroughPollLast：" + interval+" ms");
    }

    /**
     * 通過removeFirst()來遍歷LinkedList
     */
    private static void iteratorThroughRemoveFirst(LinkedList list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        try {
            while(list.removeFirst() != null)
                ;
        } catch (NoSuchElementException e) {
        }
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorThroughRemoveFirst：" + interval+" ms");
    }

    /**
     * 通過removeLast()來遍歷LinkedList
     */
    private static void iteratorThroughRemoveLast(LinkedList list) {
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        try {
            while(list.removeLast() != null)
                ;
        } catch (NoSuchElementException e) {
        }
        long end = System.currentTimeMillis();
        long interval = end - start;
        System.out.println("iteratorThroughRemoveLast：" + interval+" ms");
    }

}
測試結果如下：
 
iteratorLinkedListThruIterator：10 ms
iteratorLinkedListThruForeach：414648 ms
iteratorThroughFor2：10 ms
iteratorThroughPollFirst：8 ms
iteratorThroughPollLast：10 ms
iteratorThroughRemoveFirst：7 ms
iteratorThroughRemoveLast：6 ms