LinkedList

基本实现

LinkedList 类似 C/C++ 的双向链表，这种链表中任意一个存储单元都可以通过向前或者向后寻址的方式获取到其前一个存储单元和其后一个存储单元。而实现这一功能的储存单元是内部类 Node ：

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

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

Node 分别存储了 item（数据）与 next 、 prev（前后一个节点的引用)。

添加

老样子，我们先查看它的 add()方法

    transient int size = 0;

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

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

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

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

size、first 和 last 初始值分别为 0、null、null。add() 首先将新节点赋值给 last ,并在 first 为空时，同时赋值给 first。
否者，将旧的 last 节点 next 指向新节点。

移除

我们在观察它的 removeLast() 方法：

    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    /**
     * Unlinks non-null last node l.
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> 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;
    }

同样 removeLast() 将 last 设置为倒数第二为 Node，并且在倒数第二 Node 为 null (即原来的 LinkedList 只有一个元素时)，同时将 first 设置为 null 。

查询

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

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

get() 方法既可以向前查找，也可以向后查找。 get() 的实现先比较index 与 size >> 1 (size/2)，在选择是向前查找还是向后查找。

LinkedList 与 ArrayList

顺序插入速度 ArrayList 优于 LinkedList ，前者是已存在数组中添加引用，后者是需要 new Node 再链接。
由于需要同时保持前后一个对象的引用，LinkedList 需要的空间往往比 ArrayList 大（并不是绝对的）。
遍历速度上，在两者的使用优遍历方法时 ArrayList 优于 LinkedList。 LinkedList 在使用 for 时效率的确太过糟糕。而使用 foreach 是两者相似。
（在中间）插入删除速度上：
1. LinkedList 耗时的寻址步骤，而实际修改前后节点引用是很快的。
2. ArrayList 耗时在是 arrayCopy 步骤，寻址是十分迅速的
  如果能分析出插入步骤往往是在 List 的前半部分，那么 LinkedList 绝对优于 ArrayList。但如果靠尾部添加的话，ArrayList 会优秀与 LinkedList。