摘要：重要方法在鏈尾添加元素除了這個方法以外，還提供了等一些方法，都是為實現(xiàn)和方法服務的，因為雙向鏈表的原因，這些實現(xiàn)都很簡單。

LinkedList類聲明如下：

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

可以發(fā)現(xiàn) LinkedList繼承了 AbstractSequentialList抽象類，而不是像 ArrayList和 Vector那樣實現(xiàn) AbstractList，實際上，java類庫中只有 LinkedList繼承了這個抽象類，正如其名，它提供了對序列的連續(xù)訪問的抽象：

LinkedList的底層是 Deque雙向鏈表，實現(xiàn)了 Deque接口，而 Deque接口繼承于 Queue接口，因此，在java中，如果要實現(xiàn)隊列，一般都使用 LinkedList來實現(xiàn)。

LinkedList中關于鏈表結點的定義如下：

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;
        }
    }

每個結點都有一個前驅和后繼結點，并且在 LinkedList中也定義了兩個變量分別指向鏈表中的第一個和最后一個結點：

transient Node first;
transient Node last;

LinkedList中只有兩個構造方法，無參數(shù)的和帶有 Collection參數(shù)的：

public LinkedList() {
}
    
public LinkedList(Collection c) {
        this();
        addAll(c);
}

重點看一下第二個構造方法，它調用了 addAll()：

public boolean addAll(Collection c) {
        return addAll(size, c);
    }

這個方法將指定的 Collection添加到鏈表的結尾，如果在添加的過程中對 Collection進行了修改，則結點是不確定的。

public boolean addAll(int index, Collection c) {
        checkPositionIndex(index);//檢查是否越界
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node pred, succ;
        if (index == size) { //如果succ是null，說明是在結尾添加，如果不是，記錄index處的結點
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {// 雙向鏈表的插入操作
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {//相當于將鏈表后移
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

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

注意最終調用的是這個 addAll方法，這個方法是在指定位置 index 插入 Collection，使鏈表后面的元素右移，第一個 addAll中傳入的 index是 size，因此就是在結尾添加。

 public boolean add(E e) {
        linkLast(e);
        return true;
    }
 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++;
    }    

除了這個 linkLast方法以外，還提供了 linkFirst linkBefore unLink unLinkFirst等一些方法，都是為實現(xiàn) add和 remove方法服務的，因為雙向鏈表的原因，這些實現(xiàn)都很簡單。

因為底層實現(xiàn)不是數(shù)組，LinkedList中的 clear方法稍微復雜一些：

public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node x = first; x != null; ) {
            Node next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

clear方法中逐一取出每個結點，然后將它們的 item pre next都設為 null，有時候看以來不必要，但是為了防止在GC中，這些結點寄居在不同的年代中，因此最好這么做。

先看 clone方法的實現(xiàn)：

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;
    }
    
@SuppressWarnings("unchecked")
    private LinkedList superClone() {
        try {
            return (LinkedList) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }    

可以看到， LinkedList的 Clone方法只是簡單的將原來每個 node的 item放到克隆后的對象中，和 ArrayList的 clone方法一樣， LinkedList的 Clone方法也只是淺復制，如果元素為引用類型，那么修改原 list的值會影響克隆的 list的值。

如果仔細觀察，你會發(fā)現(xiàn)在 LinkedList中是沒有自己實現(xiàn) iterator的，如果這樣調用：

LinkedList list = new LinkedList<>();
Iterator it = list.iterator();

你會發(fā)現(xiàn)它調用的是 AbstractSequentialList中的 iterator()，返回的還是 AbstractList 中的 listIterator()，而在 LinkedList中實現(xiàn)了自己的 listIterator，因此如果進行迭代，還是老老實實用 LinkedList中的 listIterator比較好。
LinkedList中還提供了逆序的 Iterator—— DescendingIterator，實際上它也只是簡單的對 ListIterator進行了封裝：

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();
        }
    }

public Iterator descendingIterator() {
        return new DescendingIterator();
    }    

這里只是說一下大致的區(qū)別：

ArrayList繼承于 AbstractList， LinkedList繼承于 AbstractSequentialList；

ArrayList基于數(shù)組， LinkedList基于雙向鏈表，對于隨機訪問， ArrayList比較占優(yōu)勢，對于插入刪除，LinkedList占優(yōu)勢；

LinkedList沒有實現(xiàn)自己的 Iterator，但是有 ListIterator和 DescendingIterator；

LinkedList需要更多的內存，因為 ArrayList的每個索引的位置是實際的數(shù)據，而 LinkedList中的每個節(jié)點中存儲的是實際的數(shù)據和前后節(jié)點的位置；

ArrayList 和 LinkedList都是非同步的集合。