原创文章，转载请注明出处
另一个常用的数据结构——LinkedList，也是我们熟悉的链表。和 ArrayList 一样，LinkedList 也是一个线性表，不同的是 LinkedList 中维护的结构并不是内存连续的数组，而是由多个
Node组成的链表。这赋予了 LinkedList 易于修改节点的特性，同时也牺牲了快速随机访问的性能。
内部结构
LinkedList 中主要维护的变量就三个：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
//...
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是 LinkedList 中的内部类，描述了一个节点，其中包含值与指向前后节点的引用，也就是说 LinkedList 是一个双向链表。这时回过头来看看类声明的地方：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
注意到 LinkedList 是实现了 Deque(Queue)接口的，正是由于双向链表可以“两头操作”和修改节点快速的特性，LinkedList 可以直接当做队列来使用。
基础链表操作
谈到链表，最根本的操作就是节点的增删改查，下面就主要分析 JDK 中 LinkedList 是怎样对链表进行操作的。
由于 LinkedList 实现了许多接口和抽象类，例如
AbstractSequentialList,Deque等。这些接口根据自身的使用范围来定义行为(方法名称)，例如Queue中的offer(E e)，在 LinkedList 内部实际上与Collection接口定义的add(E e)方法行为一致，最终调用的都是 LinkedList 自身的linkLast(E e)，下面所分析的都是linkLast(E e)这类从接口中剥离出来直接操作链表的方法
1.添加节点
添加节点主要分三种情况：
- 在头部添加
- 在尾部添加
- 在指定位置添加
相应的有三个实现方法：
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last 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++;
}
/**
* Inserts element e before non-null Node 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++;
}
以linkBefore为例，在指定节点之前插入新节点，通过下面的图可以帮助理解：
- 加链。由于是双向链表，需要考虑每个节点的
prev引用，所以首先要将newNode的“首尾”链接起来：newNode = new Node<>(pred, e, succ)。图中（1）， （2） - 断链、重连。将
nextNode.prev,prevNode.next均指向newNode，这样新的链表就完成了。
时间复杂度：通过对添加流程的分析可以看出（删除流程逻辑相反，但是操作大致相同），LinkedList的插入/删除操作不需要移动其他节点，只需要调整相应的引用，所以，在知道要操作节点的情况下，插入/删除的时间复杂度为O(1)，而ArrayList由于需要移动指定位置之后的元素，所以其插入/删除操作的时间复杂度为O(n)（在数组末尾添加的特殊情况时间复杂度为O(1)）。
空间复杂度：对于LinkedList来说，每个节点包含三个信息，代表本身信息的 E item, 前后节点的引用Node<E> next, Node<E> prev。当添加或者删除一个节点时，操作的是节点的引用，并没有多余的空间引入。而对于ArrayList，添加元素需要考虑的最大问题就是扩容，上一篇讲ArrayList的文章中有分析到，当数组的容量不够时，ArrayList将会进行扩容操作，一旦进行扩容操作将会导致ArrayList的性能急剧下降，因为涉及到数组所有元素的拷贝。
2. 查询操作
LinkedList拥有极高的插入/删除性能，但是相应的它牺牲了高效的随机访问性能。当需要访问LinkedList中的节点 get(int i) 时，LinkedList只能从头开始遍历，其时间复杂度为O(n)，而ArrayList只需要到数组的相应位置取出元素即可，时间复杂度为O(1)。
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;
}
}
由于是双向链表，LinkedList可以根据index的范围从首尾开始遍历，一定程度上加快了访问性能，但是由于链表遍历的时间是线性的，所以其时间复杂度仍然为O(n)。
总结
与ArrayList比较
通过与上一篇讲的ArrayList进行比较，可以看出：
- 对于插入/删除操作，LinkedList快，只需要处理引用。ArrayList慢，涉及到后面元素的移位、数组的扩容。
- 对于随机访问，ArrayList快，基于数组的随机访问，不需要遍历元素。LinkedList慢，需要从头开始遍历找到对应的元素。
两种List是在生产中使用非常多的数据结构，理解其原理是构建高效代码的第一步。对于无法估计个数并且有大量插入/删除操作的集合，考虑使用LinkedList，而对于元素很少随机插入，随机访问需求较多的集合，考虑使用ArrayList。
扩展
由于链表高效的插入/删除性能，LinkedList又可以被用作队列Queue来使用，其内部实现了Queue的offer等方法。而在并发环境下，需要保证操作的原子性，java.util.concurrent 包提供了 LinkedBlockingQueue 等结构，其内部也是用链表实现的，有兴趣的朋友可以进行延伸阅读。
