今天来看一下 LinkedList 原理。本文解析的LinkedList源代码基于 JDK 1.8 。
LinkedList 是 Java 集合框架中一个重要的实现，其底层采用的双向链表结构。和 ArrayList 一样，LinkedList 也支持空值和重复值。由于 LinkedList 基于链表实现，存储元素过程中，无需像 ArrayList 那样进行扩容。但有得必有失，LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。另一方面，LinkedList 在链表头部和尾部插入效率比较高，但在指定位置进行插入时，效率一般。原因是，在指定位置插入需要定位到该位置处的节点，此操作的时间复杂度为O(N)。最后，LinkedList 是非线程安全的集合类，并发环境下，多个线程同时操作 LinkedList，会引发不可预知的错误。
链表
在分析LinkedList之前我们先复习一下链表这种数据结构
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻 辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表按照指向可以分为单向链表跟双向链表
单向链表
从head节点开始，next指针只想下一个节点的数据，tail节点的next指针指向null
双向链表
每个节点有连个指针，pre跟next，除了head节点pre指针跟tail节点的next指针都指向null之外，其余的相邻节点的指针不管是从头到尾还是反过来，当前节点的两个指针包含了相邻节点的指向。
单向链表和双向链表
单向循环链表跟单向链表的区别在于，tail节点指向head节点的数据
继承体系
LinkedList 的继承体系较为复杂，继承自 AbstractSequentialList，同时又实现了 List 和 Deque 接口。继承体系图如下：
另外，LinkedList 还实现了 Deque (double ended queue)，Deque 又继承自 Queue 接口。这样 LinkedList 就具备了队列的功能。
源码分析
Node
LinkedList 既然作为链表，那么肯定会有节点了，我们看下节点的定义：
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;
}
}
每个节点都包含了前一个节点 prev 以及后一个节点 next ，item 就是要当前节点要存储的元素。
add(E e)
public boolean add(E e) {
// 直接往队尾加元素
linkLast(e);
return true;
}
void linkLast(E e) {
// 保存原来链表尾部节点，last 是全局变量，用来表示队尾元素
final Node<E> l = last;
// 为该元素 e 新建一个节点
final Node<E> newNode = new Node<>(l, e, null);
// 将新节点设为队尾
last = newNode;
// 如果原来的队尾元素为空，那么说明原来的整个列表是空的，就把新节点赋值给头结点
if (l == null)
first = newNode;
else
// 原来尾结点的后面为新生成的结点
l.next = newNode;
// 节点数 +1
size++;
modCount++;
}
在 linkLast(E e) 中，先去判断了原来的尾节点是否为空。如果尾节点是空的，那么就说明原来的列表是空的。会将头节点也指向该元素；如果不为空，直接在后面追加即可。
其实在 first 之前，还有一个为 null 的 head 节点。head 节点的 next 才是 first 节点。
get(int index)
checkElementIndex(index);
return node(index).item;
}
在内部调用了 node(index) 方法，而 node(index) 方法在上面已经分析过了。就是判断在前半段还是在后半段，然后遍历得到即可。
remove(int index)
checkElementIndex(index);
return unlink(node(index));
}
remove(int index) 中调用了 unlink(Node<E> x) 方法来移除该节点。
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果要删除的是头节点，那么设置头节点为下一个节点
if (prev == null) {
first = next;
} else {
// 设置该节点的前节点的 next 为该节点的 next
prev.next = next;
x.prev = null;
}
// 如果要删除的是尾节点，那么设置尾节点为上一个节点
if (next == null) {
last = prev;
} else {
// 设置该节点的下一个节点的 prev 为该节点的 prev
next.prev = prev;
x.next = null;
}
// 设置 null 值，size--
x.item = null;
size--;
modCount++;
return element;
}
remove(Object o)
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
remove(Object o) 的代码就是遍历链表，然后得到相等的值就把它 unlink(x) 了。至于 unlink(Node<E> x) 的代码，上面已经分析过啦。
set(int index, E element)
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
// 设置 x 节点的值为新值，然后返回旧值
x.item = element;
return oldVal;
}
clear()
public void clear() {
// 遍历链表，然后一一删除置空
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
以上分析源码完了，下面再来对比下LinkedList和ArrayList
LinkedList和ArrayList的对比
1、顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList
2、因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存
3、数据遍历的速度，看最后一部分，这里就不细讲了，结论是：使用各自遍历效率最高的方式，ArrayList的遍历效率会比LinkedList的遍历效率高一些
4、有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：
（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址
（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址
LinkedList 相对于 ArrayList 来说，源码会复杂一点。因为涉及到了链表，所以会有 prev 和 next 之分。但是静下心来阅读，还是可以看懂的。
