前话：本次解析基于JDK1.8.0，SDK26。

一、数据结构

和ArrayList基于数组的不同，LinkedList实现思想是基于双向链表。所以在LinkedList类的内部，维护了链表的表头和表尾两个节点。有了表头和表尾节点，当然就可以对链表做任何想要的操作了。
既然是是基于链表，那么肯定离不开链表中每一个节点的定义，LinkedList内部维护了一个静态内部类Node.class（静态内部类有很多优势，自行脑补吧）用来表示节点。

//泛型，表示我们可以存储任意类型（基本类型除外）
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;
        }
    }

二、构造方法

在看构造方法之前，先看一下LinkedList类的重要的成员变量：

//当前链表的长度，（transient为序列化知识点，先不讨论）
transient int size = 0;
//表头，默认为null
transient Node<E> first;
//表尾，默认为null
transient Node<E> last;

1、最简单的无参构造方法

    //没错，就是什么都没有干！LinkedList只有在真正添加元素的时候才会初始化新节点，并把新节点连在链表上。
    public LinkedList() {
    }

2、有参构造方法：

public LinkedList(Collection<? extends E> c) {
        //调用无参构造方法，还是什么都没干。。。
        this();
        //划重点，将传入的集合参数全部添加到链表，后续分析addAll。
        addAll(c);
    }

三、add方法

public boolean add(E e) {
        //直接调用linkLast，把元素e直接link到链表的尾部。
        linkLast(e);
        return true;
    }

void linkLast(E e) {
        //将尾结点暂时赋值给 l
        final Node<E> l = last;
        //真正创建节点的地方！！！
        final Node<E> newNode = new Node<>(l, e, null);
        //将新节点重新置为尾节点
        last = newNode;
        if (l == null)
            // l==null,说明是第一次添加数据，直接链表中只有一个节点，既是头结点也是尾节点
            first = newNode;
        else
            //将新的节点连接到原来的尾节点
            l.next = newNode;
        //每增加一个元素，size++
        size++;
        modCount++;
    }

当然，默认情况下add方法会将新的数组直接连接到链表的尾部，LinkedList也提供了其他的add方法:addFirst(),addLast()，在添加元素的时候link到链表的不同位置。但是原理都是对链表的link操作。

四、get方法

根据元素的下标获取元素，先检查下标的合法性，如果合法再去链表中循环找到对应的下标。

public E get(int index) {
        //检查合法性
        checkElementIndex(index);
        //node(index)方法会返回index对应的Node节点，然后返回节点的item。
        return node(index).item;
    }

private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

Node<E> node(int index) {
        //size>>1，位运算，相当于size/2
        //二分法的思想
        if (index < (size >> 1)) {
            //如果index小于链表长度的一半，那么从链表头循环查找index对应的node
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //如果index大于链表长度的一半，则从链表尾循环递减查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

可以看出，在使用index查找元素的时候，LinkedList的性能要远低于ArrayList。

五、set方法

 public E set(int index, E element) {
        //检查index合法性
        checkElementIndex(index);
        //查找链表中的index位置的节点并赋值给x
        Node<E> x = node(index);
        //直接将新的value替换
        E oldVal = x.item;
        x.item = element;
        //返回就得vaule
        return oldVal;
    }

六、add(index,e)方法

向指定的位置index添加元素

public void add(int index, E element) {
        //检查合法性
        checkPositionIndex(index);
        //如果index == size，就直接将该元素link到链表的尾部
        if (index == size)
            linkLast(element);
        else
            //1、node（index）方法先找到index对应的原来的元素，然后再把新的元素link进去
            //例如：假设链表有2，5，3三个元素，现在要把4插入到index==1的位置，也就是link到5的前边。
            linkBefore(element, node(index));
    }

七、remove方法

public E remove(int index) {
        //检查合法性
        checkElementIndex(index);
        //调用unlink方法,也就是把这个节点从当前的链表中解构出来。
        return unlink(node(index));
    }

八、LinkedList和ArrayList的性能比较：

1、ArrayList：

在数组尾部添加和删除数据，性能开销很小，只是有时候需要对数组扩容。在数组中部添加和删除数据，需要将该数据后边的所有数据平移，性能开销很大。在进行按index查找数据时，数组的结构发挥了很大的优势，性能最高。在按value查找的时候，实际是将整个数组遍历一遍，性能较差。

2、LinkedList：

在链表尾部或头部添加和删除数据，性能开销很小。在链表的中部添加删除数据时，由于链表的特性，只需要操作该元素的前后指针，性能最高。在按index进行查找，LinkedList做了一次二分查找，但是还是需要循环链表到index的位置，所以性能很差。按value查找的时候，也是遍历整个链表，性能也很差。

总结：

当需要频繁的删除和插入数据时，使用LinkedList。
当需要频繁的按Index不断查找数据时，使用ArrayList。