概述

Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces.
Implements all optional list operations, and permits all elements (including {@code null}).

List和Deque的双向链表 实现；

LinkedList支持所有的元素，包括null；

All of the operations perform as could be expected for a doubly-linked list.
Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Note that this implementation is not synchronized.
If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it <i>must</i> be synchronized externally.
This is typically accomplished by synchronizing on some object that naturally encapsulates the list.

If no such object exists, the list should be "wrapped" using the {@link Collections#synchronizedList Collections.synchronizedList} method.

LinkedList是线程非同步的；

如果并发修改LinkedList，需要在外部实现同步；

可以使用Collections.synchronizedList；

The iterators returned by this class's {@code iterator} and {@code listIterator} methods are <i>fail-fast</i>: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own {@code remove} or {@code add} methods, the iterator will throw a {@link ConcurrentModificationException}.
Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

LinkedList的iterator是fail-fast：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{

        private static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;
        }

        transient int size = 0;
        transient Node<E> first;
        transient Node<E> last;
    }

链路

add(E e)

// java.util.LinkedList.add(E)
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

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

get(int index)

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    // java.util.LinkedList.node
    LinkedList.Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {                          // 二分查找  size>>1 = 中间位index
            LinkedList.Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            LinkedList.Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

add(int index, E element)

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));    // node(index)：找出指定index的元素 -> linkBefore:将新元素link到old pre后、old之前；
    }

    // java.util.LinkedList.node
    LinkedList.Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {                          // 二分查找  size>>1 = 中间位index
            LinkedList.Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            LinkedList.Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    // java.util.LinkedList.linkBefore
    void linkBefore(E e, LinkedList.Node<E> succ) {
        // assert succ != null;
        final LinkedList.Node<E> pred = succ.prev;
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }