前话：本次解析基于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。
