LinkedList也是Java开发中非常常见的一种集合类，LinkedList是基于链表实现的集合容器。它具备List集合的典型特征：
- 存取有序
- 支持索引访问
- 允许存储重复元素
同时它还具备Deque集合的特征：
- 先进先出
- 支持双端操作
它自身最突出的特点是：
- 对元素进行插入或删除时，只需要修改少量引用关系，不需要像数组那样移动大量元素。
下面依然通过源码分析，来看看LinkedList是如何实现这些特性的。
Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations,and permits all elements (including {@code null}).
也就是说，LinkedList是List接口和Deque接口的双向链表实现，支持List中的全部可选操作，并且可以存储所有元素，包括{@code null}。
public class LinkedList extends AbstractSequentialList
implements List, Deque, Cloneable, ja va.io.Serializable 可以看到，LinkedList实现了Deque接口。这意味着LinkedList不仅具备List的特性，同时也具备Deque的能力。那么Deque到底是什么呢？
public interface Deque extends Queue
public interface Queue extends Collection 原来Deque是继承自Collection体系中的另一个接口Queue。
Queue就是我们常说的队列，它最典型的特性是FIFO（First In First Out），也就是先进先出。它的核心操作通常只有两个：
- 把元素放入队列尾部
- 从队列头部取出元素
这和日常排队办事的场景非常相似。
而作为Queue的子接口，Deque除了具备这两种操作之外，还比普通队列提供了更多功能：
- 既可以把元素添加到队尾，也可以添加到队头
- 既可以从队尾取出元素，也可以从队头取出元素
这样看起来，两端都可以充当队头和队尾，因此Deque也被称为双端队列。
理所当然，LinkedList同样实现了这些特性，并且还具备Doubly-linked（双向链表）的结构特点。
那么，链表又是什么呢？
链表本质上是一种线性存储结构。简单来说，数据会存放在一个个存储单元中，而每个存储单元除了保存当前数据本身，还会保存与其他存储单元之间的关联地址或引用。
双向链表顾名思义，就是每个存储单元不仅保存下一个存储单元的地址，还保存上一个存储单元的地址。这样在查找数据时，就可以根据这些引用关系向前或向后定位目标元素。
成员变量：
transient int size = 0;
transient Node first;
transient Node last; 成员变量只有三个：size表示LinkedList中实际存储的元素数量。那么这里的Node又是什么呢？
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} 它是LinkedList内部定义的数据结构Node，也是LinkedList最基础的存储单元，更能直接体现LinkedList双向链表的实现方式。
大致就是这样的结构。
其中prev用于保存上一个节点的引用（地址），next用于保存下一个节点的引用，item则是真正要存储的数据。
first和last分别用于标识链表的头节点和尾节点。
添加数据：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
} 默认情况下，add(E e)调用的是尾部添加方法。前面提到过，LinkedList的基础存储单元是Node，因此新增的数据会被封装到Node的item属性中。同时，新节点的prev会指向前一个节点，而前一个节点的next会指向这个新节点。
大致可以这样理解。不过要注意，图中的连线只是便于理解的示意方式，正如前面所说，Node中的prev和next本质上保存的是引用，通过引用才能定位到前一个Node或后一个Node。
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
} 实际上，LinkedList中存在不少名称不同但底层逻辑相近的方法。这是因为LinkedList既可以当作List使用，也可以表示Queue、Deque，甚至可以模拟Stack等数据结构。即便都是在队头或队尾插入元素，使用语义更明确的方法名，能显著提高代码可读性。例如，把LinkedList当作栈时，可以使用push()、pop()、peek()；把它当作队列时，则更适合使用add()、offer()等方法。（当然，从设计角度看，使用多态会更理想。）
删除数据：
//删除头Node
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//删除操作
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//删除尾Node
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//删除操作
private E unlinkLast(Node l) {
// assert l == last && l != null;
//拿到最后一个元素存放的数据
final E element = l.item;
//拿到最后一个元素的prev前元素的引用
final Node prev = l.prev;
//将它们赋值为null
l.item = null;
l.prev = null; // help GC
//现在前元素是list(最后一个Node)
last = prev;
//如果前元素已经是null说明没有Node了
if (prev == null)
first = null;
else
//说明前面还有元素，那么前元素的next就存放null
prev.next = null;
size--;
modCount++;
return element;
} 先看比较简单的删除逻辑。这里删除的是头节点和尾节点，因此只需要判断删除后相邻Node的prev或next是否还存在：如果存在，说明链表中还有其他节点；如果不存在，就说明LinkedList已经为空。
怎样才算真正删除了头Node或尾Node？只要它的next或prev不再与链表保持有效连接，也就是没有可达引用能再从LinkedList访问到它，我们就可以认为这个Node已经从链表中移除了。由于无法再通过引用链找到它，因此GC很快也会将这个Node回收。
上面只是删除头尾Node，那么如果要删除中间位置的Node呢？这就需要结合下面的查找和插入一起理解。
查找元素：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
// assert isElementIndex(index);
//如果索引小于元素个数的一半，就从前遍历
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//否则从后遍历
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
} 数组天然具备下标，可以直接通过索引快速获取对应位置的元素。但LinkedList底层并没有维护一个连续数组，那么它是如何知道第几个元素是什么的呢？
方法其实很直接：既然我有size个元素，而你给了一个index，那就沿着链表一个一个找过去即可。因为每个Node都记录着相邻节点的引用（地址），所以可以顺着引用不断向前或向后遍历。
如果index小于size的一半，就从前往后找；如果index大于等于size的一半，就从后往前找。正因为LinkedList是双向链表，并且同时保存了first和last引用，所以它可以从距离更近的一端开始查找，以减少遍历次数。
也正因如此，在LinkedList中按索引查找元素并不算高效，最坏情况下可能需要遍历接近size/2次才能定位目标位置。
不过，只要找到了目标位置对应的Node，那么在这个位置进行插入或删除就会变得非常方便。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node x) {
// assert x != null;
//拿到所要删除的Node的item
final E element = x.item;
//后一个Node
final Node next = x.next;
//前一个Node
final Node prev = x.prev;
//如果前一个Node为null(说明是第一个Node)
if (prev == null) {
//那么后一个Node作为first
first = next;
} else {//否则说明前面有Node
//那前一个Node的下一个Node引用变为后一个Node
prev.next = next;
//当前的前引用变成null
x.prev = null;
}
//如果后一个Node为null(说明是最后一个Node)
if (next == null) {
//那么前一个Node作为last
last = prev;
} else {//否则说明后面还有Node
//那后一个Node的下一个Node引用变为前一个Node
next.prev = prev;
//当前的后引用变为null
x.next = null;
}
//保存的元素也设为null
x.item = null;
//元素-1
size--;
//修改次数+1
modCount++;
return element;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
//要插入位置的前一个Node
final Node pred = succ.prev;
//新Node，前引用是前一个Node，后引用是当前位置的Node
final Node newNode = new Node<>(pred, e, succ);
//后一个Node的前引用变为这个新Node
succ.prev = newNode;
//如果没有前一个Node
if (pred == null)
//说明添加的就是第一个Node了
first = newNode;
else//说明前面还有Node
//将前一个Node的后引用变为这个新的Node
pred.next = newNode;
//元素+1
size++;
modCount++;
} 可以看到，本质上只是修改了存储单元Node中的prev和next引用关系，我们就能够认为某个Node被成功插入或删除了。
结合代码注释再配合下图来看，会更容易理解整个过程。阅读源码时要特别注意其中的命名，最好自己顺手画一下结构图或记一下变量含义，这样更不容易混淆。
如果是插入元素，把这个过程反过来理解即可。
关于遍历：
通过前面的分析我们可以知道，LinkedList最大的性能消耗通常出现在node(index)这一步，因为它需要先定位目标元素所在的Node。但一旦定位完成，后续的插入和删除操作就会非常方便。
因此，对于get(index)这个方法一定要谨慎使用。如果只是偶尔查看某个位置的元素，用它没有问题；但如果是遍历LinkedList，就千万不要这样写：
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i).equals(Obj);
}因为在每一次循环中，get(i)都可能需要从前往后或从后往前遍历若干次。即使考虑了get方法里>>1的优化，这种写法整体上仍然接近O(n^2)时间复杂度，效率会非常低。
所以，LinkedList专门提供了内部Iterator迭代器供我们进行高效遍历：
private class ListItr implements ListIterator {
private Node lastReturned;
private Node next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
} 它的本质就是不断调用next()获取当前Node，再基于这个Node进行后续操作。这样遍历的时间复杂度就是O(n)，不会产生大量重复且无意义的查找过程。
总结：LinkedList插入快、删除快，这种说法其实是有前提的。
LinkedList在执行插入、删除操作时，慢的地方在于先找到具体位置；快的地方在于只需要修改前后Node之间的引用关系。
ArrayList在执行插入、删除操作时，慢的地方在于数组元素的批量复制（例如前文提到的System.arraycopy）；快的地方则在于按索引查找和随机访问。
当待插入或删除的元素位于数据结构前半段，尤其是非常靠前的位置时，LinkedList的效率往往会明显优于ArrayList，因为ArrayList需要搬移大量元素。不过，越往后，对于LinkedList来说，由于它本质上是双向链表，在第2个元素后插入数据和在倒数第2个元素后插入数据，效率几乎没有本质差别；而ArrayList随着需要复制的元素越来越少，执行速度也会逐渐追上，甚至超过LinkedList。
总之，Java集合选型一定要结合具体业务场景来决定。最稳妥的做法还是根据实际需求进行性能测试，这样才能获得更高的程序执行效率。
