摘要：我們來看相關源碼我們看到封裝的和操作其實就是對頭結點的操作。迭代器通過指針，能指向下一個節點，無需做額外的遍歷，速度非常快。不同的遍歷性能差距極大，推薦使用迭代器進行遍歷。

上一篇文章我們介紹了JDK中ArrayList的實現，ArrayList底層結構是一個Object[]數組，通過拷貝，復制等一系列封裝的操作，將數組封裝為一個幾乎是無限的容器。今天我們來介紹JDK中List接口的另外一種實現，基于鏈表結構的LinkedList。ArrayList由于基于數組，所以在隨機訪問方面優勢比較明顯，在刪除、插入方面性能會相對偏弱些(當然與刪除、插入的位置有很大關系)。那么LinkedList有哪些優勢呢？它在刪除、插入方面的操作很簡單(只是調整相關指針而已)。但是隨機訪問方面要遜色寫。下面我們還是從源碼上來看下這種鏈表結構的List。

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node last;

我們看到字段非常少，size表示當前節點數量，first指向鏈表的起始元素、last指向鏈表的最后一個元素。

從上面主要字段看出，LinkedList鏈表的Item就是一個Node結構，那么Node結構是怎樣的呢？源碼如下：

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

我們看到Node結構包含一個前驅prev指針，item(value)、后繼next指針三個部分。結合上面的描述，我們知道了LinkedList的主要結構。如圖：

LinkedList相關方法解析 構造函數

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collections
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<);

由于LinkedList是通過prev與next指針鏈接起來的，有元素添加時只需要一個個設置指針將其鏈接起來即可，所以構造函數相對較簡潔。我們重點來看下第二個構造函數中的addAll方法。

/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the specified
 * collections iterator.  The behavior of this operation is undefined if
 * the specified collection is modified while the operation is in
 * progress.  (Note that this will occur if the specified collection is
 * this list, and its nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<);return addAll(size, c);
}

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collections iterator.
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection<);if (numNew == 0)
        return false;

    Node pred, succ;
    if (index == size) {
        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;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

addAll方法是將Collection集合插入鏈表。下面我們來仔細分析整個過程(涉及比較多的指針操作)。

首先代碼檢查index的值的正確性，如果index位置不合理會直接拋出異常。

然后將待插入集合轉化成數組，判斷集合長度。

根據index值，分別設置pred和succ指針。如果插入的位置是當前鏈表尾部，那么pred指向最后一個元素，succ暫時設置為NULL即可。如果插入位置在鏈表中間，那么先通過node方法找到當前鏈表的index位置的元素，succ指向它。pred指向待插入位置的前一個節點，succ指向當前index位置的節點，新插入的節點就是在pred和succ節點之間。

for循環創建Node節點，先將pred.next指向新創建的節點，然后pred指向后移，指向新創建的Node節點，重復上述過程，這樣一個個節點就被創建，鏈接起來了。

最后根據情況不同，將succ指向的那個節點作為最后的節點，當然如果succ為NULL的話，last指針指向pred。

removeFirst方法會返回當前鏈表的頭部節點值，然后將頭結點指向下一個節點，我們通過源碼來分析：

/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node f) {
    // assert f == first && 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)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

我們看到主要邏輯在unlinkFirst方法中，邏輯還是比較清晰的，first指針指向next節點，該節點作為新的鏈表頭部，只是最后需要處理下邊界值(next==null)的情況。removeLast方法類似，大家可以去分析源碼。

addFirst方法是將新節點插入鏈表，并且將新節點作為鏈表頭部，下面我們來看源碼：

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node f = first;
    final Node newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

代碼邏輯比較清晰，newNode節點在創建時，由于是作為新的頭結點的，所以prev必須是NULL的，next是指向當前頭結點f。接下來就是設置first，處理邊界值了。
下面我們來看下addLast方法，源碼如下：

/**
 * Appends the specified element to the end of this list.
 *
 * 
This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}

/**
 * Links e as last element.
 */
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++;
}

這兩個方法是我們使用頻率很高的方法，我們來看下其內部實現：

/**
 * Appends the specified element to the end of this list.
 *
 * 
This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * (o==null );if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
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 {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * Unlinks non-null node x.
 */
E unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

我們看到add方法其實就是對linkLast方法的封裝(當然，這是末尾添加)。remove方法邏輯會復雜些，需要先找到指定節點，然后調用unlink方法。
unlink方法解析
我們看到unlink方法首先將需要刪除的節點的prev和next保存起來，因為后面需要將兩者連接起來。然后將prev和next分別判斷設置(包括邊界值的考慮)，最后將x節點的數據設置為NULL。

/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
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++;
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E peek() {
    final Node f = first;
    return (f == null) );return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E element() {
    return getFirst();
}

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node f = first;
    return (f == null) );return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E remove() {
    return removeFirst();
}

/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}

// Deque operations
/**
 * Inserts the specified element at the front of this list.
 *
 * @param e the element to insert
 * @return {@code true} (as specified by {@link Deque#offerFirst})
 * @since 1.6
 */
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

/**
 * Inserts the specified element at the end of this list.
 *
 * @param e the element to insert
 * @return {@code true} (as specified by {@link Deque#offerLast})
 * @since 1.6
 */
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

/**
 * Retrieves, but does not remove, the first element of this list,
 * or returns {@code null} if this list is empty.
 *
 * @return the first element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
public E peekFirst() {
    final Node f = first;
    return (f == null) );if this list is empty.
 *
 * @return the last element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
public E peekLast() {
    final Node l = last;
    return (l == null) );if this list is empty.
 *
 * @return the first element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
public E pollFirst() {
    final Node f = first;
    return (f == null) );if this list is empty.
 *
 * @return the last element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
public E pollLast() {
    final Node l = last;
    return (l == null) );

/**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 *
 * 
This method is equivalent to {@link #addFirst}.
 *
 * @param e the element to push
 * @since 1.6
 */
public void push(E e) {
    addFirst(e);
}

/**
 * Pops an element from the stack represented by this list.  In other
 * words, removes and returns the first element of this list.
 *
 * 
This method is equivalent to {@link #removeFirst()}.
 *
 * @return the element at the front of this list (which is the top
 *         of the stack represented by this list)
 * @throws NoSuchElementException if this list is empty
 * @since 1.6
 */
public E pop() {
    return removeFirst();
}

private class ListItr implements ListIterator {
    private Node lastReturned;
    private Node next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) );hasNext() {
        return nextIndex < size;
    }

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

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

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

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) );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++;
    }

    public void forEachRemaining(Consumer<);while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

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

List list=new LinkedList<>();
for(int i=0;i<10000;i++) {
	list.add(String.valueOf(i));
}

//遍歷方法一
long time=System.currentTimeMillis();
for(int i=0;i iterator=list.iterator();
while (iterator.hasNext()) {
	iterator.next();
}
iterator.remove();
System.out.println(System.currentTimeMillis()-time);

size:10000的情況
120
2
size:100000的情況
28949
2

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}