LinkedList

实现：

基于链表的数据结构实现，实现了List和Deque接口，有List和队列的特性，底层实现是一个双端链表，内部有个私有类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;
        }
    }

增删改查都是通过操作该类中item(当前节点)、prev(前驱节点)、next(后继结点)实现。

特性：

1. 插入和删除效率比较高
2. 继承了队列的先进先出以及拥有栈的先进后出特性
3. 保存了next和prev指针，浪费空间
4. 线程不安全

源码解析：

我们先来看一下LinkedList的内部结构图，方便我们更好的理解源码，如下： 结构

每个节点都保存了上/下节点的指针，第一个节点的prev和最后一个节点的next都为空，这就是LinkedList内部的结构。

接下来我们从源码角度分析add流程，get和remove这里不分析，与add是类似的。
通过Ctrl+鼠标左键进入到LinkedList源码中，搜索add(index, E element)方法，先看该方法：

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

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

调用checkPositionIndex,去检查index是否合法，不合法直接抛出异常，然后判断index是不是最后一个元素，如果是，调用linkLast(element)方法，否则调用linkBefore(element, node(index))将该元素插入index前。

我们来看LinkLast(element)源码：

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

先用一个局部变量l保存当前表中最后一个元素last，然后新建一个节点newNode，将l当成newNode的prev节点，next节点为空(请参考上面链表结构图)，然后将newNode指向last，完成最后一个节点的插入，如果l是空的，说明该链表之前就是个空列表，first节点也应该为newNode，如果不是，则需要更新l.next的指向，将l.next指向newNode，关联上链表，最后size加1.

接着看linkBefore(element, node(index))方法，我们先看他的第2个参数，需要通过index去查找到要插入的Node节点，这里通过node(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;
        }
    }

我们可以看到这里查找并不是一个一个去查的，而是将整个列表折半，看index在哪个区间，提升了一点效率。
接下来我们再看linkBefore(element, succ)方法本身，上源码：

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

这里我们先将要插入节点的succ.prev保存到pred中，然后创建一个新节点newNode，该节点就是要插入的节点，所以该新节点的前驱节点就是pred,当前节点就是element,后继结点就是succ本身，将newNode放到succ.prev中，节点就插入进去了，然后判断pred是不是为null,如果是，说明列表之前是空的，first节点就是newNode,如果不是，需要指定pred.next节点为newNode。
这样就完成了一个Node插入到指定的位置中，其他操作基本都是这样实现的。