共计 4750 个字符，预计需要花费 12 分钟才能阅读完成。
1. 概述
LinkedList是基于双向链表来编写的，不需要考虑容量的问题，但节点需要额外的空间存储前驱和后继的引用。有序可重复，可存储 null 值，非线程安全。
1.1 继承体系
LinkedList实现了 Deque 接口，这样 LinkedList 就具备了双端队列的功能，本文旨在介绍 LinkedList 的List功能，队列功能不再进行说明。
LinkedList没有实现 RandomAccess 接口，所以不要通过访问下标方式（for(int i=0;i<size;i++)）遍历，否则效率极差。
2. 源码分析
本文主要针对 LinkedList 的常用操作进行分析，代码如下。
List<String> linkedList = new LinkedList<>();
//add(E e)
linkedList.add("QQ");
linkedList.add("WW");
linkedList.add("EE");
linkedList.add("RR");
linkedList.add("TT");
linkedList.add("YY");
linkedList.add("UU");
linkedList.add("II");
linkedList.add("OO");
//add(int index, E element)插入元素到指定结点
linkedList.add(2, "BaseC");
//get
System.out.println(linkedList.get(2));
//traverse(遍历)
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {iterator.next();
}
//remove(Object o)
linkedList.remove("EE");
//remove(int index)删除中间元素
linkedList.remove(3);
//remove(int index)删除链表头元素
linkedList.remove(0);
//remove(int index)删除链表尾元素
linkedList.remove(linkedList.size() - 1);
System.out.println(linkedList);2.1 属性
// 元素个数
transient int size = 0;
// 链表首结点
transient Node<E> first;
// 链表尾结点
transient Node<E> last;
// 链表结点类
private static class Node<E> {
// 结点中的值
E item;
// 指向之前的节点
Node<E> prev;
// 指向之后的节点
Node<E> next;
// 构造方法
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}2.2 新增
2.2.1add(E e)
// 将元素添加到列表尾部
public boolean add(E e) {linkLast(e);
return true;
}
// 将 e 元素添加链表末端
void linkLast(E e) {
// 声明 l 变量保存当前 last 对象
final Node<E> l = last;
// 以 e 为 item 声明一个新的 last 对象
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// 第一次添加元素时
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}首次添加元素如下图所示：
非首次添加元素如下如图所示：
2.2.2add(int index, E element)
// 将元素插入到指定 index，之前在此 index 及其之后的元素向右移动。public void add(int index, E element) {// 判断 index 是否在 [0,size] 之间，注意包含 0 和 size。checkPositionIndex(index);
// 如果 index 等于当前 size，调用 linkLast(E e)方法，否则调用 linkBefore(E e)方法
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// 返回指定 index 上的非空结点
Node<E> node(int index) {
// 假设 index 合法
//size>>1 返回 size 的一半，判断 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;
}
}
// 在非空的 succ 结点之前插入元素
void linkBefore(E e, Node<E> succ) {
// 获取 succ 结点的 prev 结点
final Node<E> pred = succ.prev;
// 在 pred 和 succ 之间生成 item 为 e 的结点
final Node<E> newNode = new Node<>(pred, e, succ);
// 将 succ 的 prev 指向 newNode
succ.prev = newNode;
// 如果 succ 是头元素，将 first 指向 newNode
if (pred == null)
first = newNode;
else
// 否则将 pred 的 next 结点指向 newNode
pred.next = newNode;
size++;
modCount++;
}添加流程如下图所示：
在链表首尾添加元素很高效，时间复杂度为O(1)。
在链表中间添加元素比较低效，时间复杂度为O(N)。
2.3 查找
// 返回指定位置上的值
public E get(int index) {
// 检查 index 是否合法
checkElementIndex(index);
//node(int index)方法已在上文列出，此处不在展示。return node(index).item;
}查找方法的重点在于 node(int index) 方法。由于需要通过从头或从尾查找元素，时间复杂度为O(N)。
2.4 遍历
在分析源码之前，先看下 iterator() 的调用流程。首先调用 linkedList.iterator() 进入 AbstractSequentialList 的iterator()方法。
public Iterator<E> iterator() {return listIterator();
}此方法调用了其父类 AbstractList 的listIterator()方法。
public ListIterator<E> listIterator() {return listIterator(0);
}而在此方法中调用了 listIterator(final int index) 方法，此方法 LinkedList 将其重写了，所以程序就会去调用 LinkedList 中的 listIterator(int index) 方法。通过这个流程我们也巩固下 Java 多继承下方法的调用流程。下面咱们就来看源码吧。
public ListIterator<E> listIterator(int index) {// 判断 index 是否在 [0,size] 之间，注意包含 0 和 size。checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
// 上一次返回的值
private Node<E> lastReturned;
// 当前要返回的值
private Node<E> next;
// 当前 index 值
private int nextIndex;
// 用于 fail-fast 校验
private int expectedModCount = modCount;
ListItr(int index) {
// 如果 index 是当前 size 值，则 next 为 null，否则返回对应 index 的结点。next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {return nextIndex < size;}
public E next() {
//fail-fast 判断
checkForComodification();
// 判断当前是否还有值，调用方可直接调用 next()方法获取下个值，不必额外进行 hasNext（）的判断。if (!hasNext())
throw new NoSuchElementException();
// 即将返回 next，将 next 传给 lastReturned
lastReturned = next;
// 获取下次将要返回的结点
next = next.next;
nextIndex++;
return lastReturned.item;
}
// 省略其余代码。。。}2.5 删除
2.5.1remove(Object o)
// 删除 o 在列表中第一次存储的位置
public boolean remove(Object o) {
// 当 o 为 null 时
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;
}
// 删除非空结点
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 {
// 将 prev 结点的 next 指针指向 next 结点, 将被删除结点的 prev 置为 null
prev.next = next;
x.prev = null;
}
// 删除尾元素时
if (next == null) {last = prev;} else {
// 将 next 结点的 prev 指针指向 prev 结点, 将被删除结点的 next 置为 null
next.prev = prev;
x.next = null;
}
// 将 x 的 item 变为 null，便于 GC
x.item = null;
size--;
modCount++;
return element;
}unlink(Node x)其流程如下图所示：
2.5.2remove(int index)
// 删除指定 index 处的元素，后面的元素向左移动一位，返回被删除的元素。public E remove(int index) {// 检验 index 是否在 [0,index) 之内
checkElementIndex(index);
// 通过 node(int index)查找结点，将其传入 unlink(Node node)方法
return unlink(node(index));
}在链表首尾删除元素很高效，时间复杂度为O(1)。
在链表中间删除元素比较低效，时间复杂度为O(N)。
3. 参考
LinkedList 源码分析(JDK 1.8)
死磕 java 集合之 LinkedList 源码分析
正文完
