精尽 JDK 源码解析 —— 集合（二）链表 LinkedList

考虑到 LinkedList 和 ArrayList 是 List 绝代双骄，所以本文在编写的时候，尽量保持标题一致，方便胖友对比。 相比来说，LinkedList 会简单蛮多。看完本文后，胖友可以试着做下 设计链表 题目。

LinkedList ，基于节点实现的双向链表的 List ，每个节点都指向前一个和后一个节点从而形成链表。

相比 ArrayList 来说，我们日常开发使用 LinkedList 相对比较少。如果胖友打开 IDEA ，搜下项目中 LinkedList 后，会发现使用的少之又少。

LinkedList 实现的接口、继承的抽象类，如下图所示：
类图

如下 3 个接口是 ArrayList 一致的：

• java.util.List 接口
• java.io.Serializable 接口
• java.lang.Cloneable 接口

如下 1 个接口是少于 ArrayList 的：

• java.util.RandomAccess 接口，LinkedList 不同于 ArrayList 的很大一点，不支持随机访问。

如下 1 个接口是多于 ArrayList 的：

• java.util.Deque 接口，提供双端队列的功能，LinkedList 支持快速的在头尾添加元素和读取元素，所以很容易实现该特性。> 注意，以为 LinkedList 实现了 Deque 接口，所以我们在 「5. 添加单个元素」 和 「7. 移除单个元素」 中，会看到多种方法，胖友可以快速看过去即可。😈 因为确实蛮多的。

  也因为实现 Deque 即可以作为队列使用，也可以作为栈使用。当然，作为双端队列，也是可以的。

继承了 java.util.AbstractSequentialList 抽象类，它是 AbstractList 的子类，实现了只能连续访问 “数据存储”（例如说链表）的 #get(int index)、#add(int index, E element) 等等随机操作的方法。可能这样表述有点抽象，胖友点到 java.util.AbstractSequentialList 抽象类中看看这几个方法，基于迭代器顺序遍历后，从而实现后续的操作。

• 但是呢，LinkedList 和 ArrayList 多是一个有点 “脾气” 的小伙子，都为了结合自身的特性，更加高效的实现，多选择了重写了 AbstractSequentialList 的方法，嘿嘿。
• 不过一般情况下，对于支持随机访问数据的继承 AbstractList 抽象类，不支持的继承 AbstractSequentialList 抽象类。

LinkedList 一共有 3 个属性。如下图所示：

LinkedList

艿艿：发现自己真是画图鬼才，画的真丑，哈哈哈哈。

• 通过 Node 节点指向前后节点，从而形成双向链表。
• first 和 last 属性：链表的头尾指针。
  • 在初始时候，first 和 last 指向 null ，因为此时暂时没有 Node 节点。
  • 在添加完首个节点后，创建对应的 Node 节点 node1 ，前后指向 null 。此时，first 和 last 指向该 Node 节点。
  • 继续添加一个节点后，创建对应的 Node 节点 node2 ，其 prev = node1 和 next = null ，而 node1 的 prev = null 和 next = node2 。此时，first 保持不变，指向 node1 ，last 发生改变，指向 node2 。
• size 属性：链表的节点数量。通过它进行计数，避免每次需要 List 大小时，需要从头到尾的遍历。

对应代码如下：

transient int size = 0;

transient Node first;

transient Node last;

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;
}

}

ArrayList 一共有两个构造方法，我们分别来看看。代码如下：

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
this();

addAll(c);
}

相比 ArrayList 来说，因为没有容量一说，所以不需要提供 #ArrayList(int initialCapacity) 这样的构造方法。

#add(E e) 方法，顺序添加单个元素到链表。代码如下：

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++;
}

• <X> 处，调用 #linkLast(E e) 方法，将新元素添加到链表的尾巴。所以，#add(E e) 方法，实际就是 #linkLast(E e) 方法。
• 总体来说，代码实现比较简单。重点就是对 last 的处理。
• 相比 ArrayList 来说，无需考虑容量不够时的扩容。

看懂这个方法后，我们来看看 #add(int index, E element) 方法，插入单个元素到指定位置。代码如下：

public void add(int index, E element) {

checkPositionIndex(index);

if (index == size)
linkLast(element);

else
linkBefore(element, node(index));
}

• <1> 处，如果刚好等于链表大小，直接调用 #linkLast(E element) 方法，添加到尾部即可。
• <2> 处，先调用 #node(int index) 方法，获得第 index 位置的 Node 节点 node 。然后，调用 #linkBefore(E element, Node node) 方法，将新节点添加到 node 的前面。相当于说，node 的前一个节点的 next 指向新节点，node 的 prev 指向新节点。
• #node(int index) 方法，获得第 index 个 Node 节点。代码如下：
  Node node(int 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 做的一个小骚操作，根据 index 是否超过链表的一半大小，选择是否使用倒序遍历替代正序遍历，从而减少遍历次数。
• #linkBefore(E e, Node<E> succ) 方法，添加元素 e 到 succ 节点的前面。代码如下：
  void linkBefore(E e, Node succ) {
  final Node pred = succ.prev;
  final Node newNode = new Node<>(pred, e, succ);
  succ.prev = newNode;
  if (pred == null)
  first = newNode;
  else
  pred.next = newNode;
  size++;
  modCount++;
  }
  • 逻辑上，和 #linkLast(E e) 方法差不多。差别在于 <Y> 处，设置 succ 的前一个节点为新节点。

因为 LinkedList 实现了 Deque 接口，所以它实现了 #addFirst(E e) 和 #addLast(E e) 方法，分别添加元素到链表的头尾。代码如下：

public void addFirst(E e) {
linkFirst(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}

public void addLast(E e) {
linkLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}

• #linkLast(E e) 方法，和 #add(E e) 方法是一致的，就不哔哔了。
• #addFirst(E e) 方法，调用 #linkFirst(E 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++;
  }
  • 逻辑上，和 #linkLast(E e) 方法差不多。就不重复哔哔了。

因为 LinkedList 实现了 Queue 接口，所以它实现了 #push(E e) 和 #offer(E e) 方法，添加元素到链表的头尾。代码如下：

public void push(E e) {
addFirst(e);
}

public boolean offer(E e) {
return add(e);
}

总的来说，添加单个元素，分成三个情况：

• 添加元素到队头
• 添加元素到队尾
• 添加元素到中间

对于链表的操作，代码会比较简洁，胖友如果不太理解，可以在草稿纸上手绘下整个过程。

LinkedList 不存在扩容的需求，因为通过 Node 的前后指向即可。

#addAll(Collection<? extends E> c) 方法，批量添加多个元素。代码如下：

public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);

Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;

Node pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}

for (Object o : a) {

@SuppressWarnings(“unchecked”) E e = (E) o;
Node newNode = new Node<>(pred, e, null);

if (pred == null)
first = newNode;

else
pred.next = newNode;

pred = newNode;
}

if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}

size += numNew;

modCount++;

return true;
}

• #addAll(Collection<? extends E> c) 方法，其内部调用的是 #addAll(int index, Collection<? extends E> c) 方法，表示在队列之后，继续添加 c 集合。
• <2> 处，获得第 index 位置的节点 succ ，和其前一个节点 pred 。分成两种情况，胖友自己看注释。实际上，ArrayList 在添加 c 集合的时候，也是分成跟 LinkedList 一样的两种情况，只是说 LinkedList 在一个方法统一实现了。
• <3> 处，遍历 a 数组，添加到 pred 的后面。其实，我们可以把 pred 理解成 “尾巴”，然后不断的指向新节点，而新节点又称为新的 pred 尾巴。如此反复插入~
• <4> 处，修改 succ 和 pred 的指向。根据 <2> 处分的两种情况，进行处理。
• 😈 虽然很长，但是还是很简单的。

#remove(int index) 方法，移除指定位置的元素，并返回该位置的原元素。代码如下：

public E remove(int index) {
checkElementIndex(index);

return unlink(node(index));
}

• 首先，调用 #node(int index) 方法，获得第 index 的 Node 节点。然后偶，调用 #unlink(Node<E> x) 方法，移除该节点。
• #unlink(Node<E> x) 方法，代码如下：
  E unlink(Node x) {
  final E element = x.item;
  final Node next = x.next;
  final Node prev = x.prev;
  if (prev == null) {
  first = next;
  } else {
  prev.next = next;
  x.prev = null;
  }
  if (next == null) {
  last = prev;
  } else {
  next.prev = prev;
  x.next = null;
  }
  x.item = null;
  size—;
  modCount++;
  return element;
  }
  • <2> 处，将 prev 的 next 指向下一个节点。其中，<2.1> 处，是移除队头 first 的情况。
  • <3> 处，将 next 的 prev 指向上一个节点。其中，<3.1> 处，如果 next 为空，说明队尾 last 被移除的情况。
  • 其它步骤，胖友自己看看代码注释。

#remove(Object o) 方法，移除首个为 o 的元素，并返回是否移除到。代码如下：

public boolean remove(Object o) {
if (o == null) {

for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {

for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

• 相比 #remove(int index) 方法来说，需要去寻找首个等于 o 的节点进行移除。当然，最终还是调用 #unlink(Node<E> x) 方法，移除该节点。

#removeFirstOccurrence(Object o) 和 #removeLastOccurrence(Object o) 方法，分别实现移除链表首个节点和最后节点。代码如下：

public boolean removeFirstOccurrence(Object o) {
return remove(o);
}

public boolean removeLastOccurrence(Object o) {
if (o == null) {

for (Node x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {

for (Node x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

#remove() 方法，移除链表首个节点。代码如下：

public E remove() {
return removeFirst();
}

public E removeFirst() {
final Node f = first;

if (f == null)
throw new NoSuchElementException();

return unlinkFirst(f);
}

private E unlinkFirst(Node f) {

final E element = f.item;

final Node next = f.next;

f.item = null;

f.next = null;

first = next;

if (next == null)
last = null;
else
next.prev = null;

size—;

modCount++;
return element;
}

• <1> 处，如果链表为空，抛出 NoSuchElementException 异常。
• <2> 处，移除链表时首个元素。比较简单，胖友自己看看。😈 因为 LinkedList 有 first 和 last 头尾节点，所以添加和删除操作，都可能需要小心处理。

#removeLast() 方法，移除链表最后一个节点。代码如下：

public E removeLast() {
final Node l = last;

if (l == null)
throw new NoSuchElementException();

return unlinkLast(l);
}

private E unlinkLast(Node l) {

final E element = l.item;

final Node prev = l.prev;

l.item = null;

l.prev = null;

last = prev;

if (prev == null)
first = null;
else
prev.next = null;

size—;

modCount++;
return element;
}

• 和 #removeFirst() 方法相反，当然实现上是差不多。

#poll() 和 # 方法，移除链表的头或尾，差异点在于链表为空时候，不会抛出 NoSuchElementException 异常。代码如下：

public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}

public E pop() {
return removeFirst();
}

public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}

#removeAll(Collection<?> c) 方法，批量移除指定的多个元素。代码如下：

public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;

Iterator<?> it = iterator();

while (it.hasNext()) {

if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}

• 该方法，是通过父类 AbstractCollection 来实现的，通过迭代器来遍历 LinkedList ，然后判断 c 中如果包含，则进行移除。

#retainAll(Collection<?> c) 方法，求 LinkedList 和指定多个元素的交集。简单来说，恰好和 #removeAll(Collection<?> c) 相反，移除不在 c 中的元素。代码如下：

public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;

Iterator it = iterator();

while (it.hasNext()) {

if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}

• 逻辑比较简单，<X> 处的判断条件进行了调整。

#indexOf(Object o) 方法，查找首个为指定元素的位置。代码如下：

public int indexOf(Object o) {
int index = 0;
if (o == null) {

for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {

for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}

return -1;
}

而 #contains(Object o) 方法，就是基于该方法实现。代码如下：

public boolean contains(Object o) {
return indexOf(o) >= 0;
}

有时我们需要查找最后一个为指定元素的位置，所以会使用到 #lastIndexOf(Object o) 方法。代码如下：

public int lastIndexOf(Object o) {
int index = size;
if (o == null) {

for (Node x = last; x != null; x = x.prev) {
index—;
if (x.item == null)
return index;
}
} else {

for (Node x = last; x != null; x = x.prev) {
index—;
if (o.equals(x.item))
return index;
}
}

return -1;
}

#get(int index) 方法，获得指定位置的元素。代码如下：

public E get(int index) {
checkElementIndex(index);

return node(index).item;
}

• 随机访问 index 位置的元素，时间复杂度为 O(n) 。

因为 LinkedList 实现了 Deque 接口，所以它实现了 #peekFirst() 和 #peekLast() 方法，分别获得元素到链表的头尾。代码如下：

public E peekFirst() {
final Node f = first;
return (f == null) ? null : f.item;
}

public E peekLast() {
final Node l = last;
return (l == null) ? null : l.item;
}

因为 LinkedList 实现了 Queue 接口，所以它实现了 #peek() 和 #peek() 和 #element() 方法，分别获得元素到链表的头。代码如下：

public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}

public E element() {
return getFirst();
}
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

#set(int index, E element) 方法，设置指定位置的元素。代码如下：

public E set(int index, E element) {
checkElementIndex(index);

Node x = node(index);
E oldVal = x.item;

x.item = element;
return oldVal;
}

#toArray() 方法，将 ArrayList 转换成 [] 数组。代码如下：

public Object[] toArray() {

Object[] result = new Object[size];

int i = 0;
for (Node x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}

实际场景下，我们可能想要指定 T 泛型的数组，那么我们就需要使用到 #toArray(T[] a) 方法。代码如下：

public T[] toArray(T[] a) {

if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);

int i = 0;
Object[] result = a;
for (Node x = first; x != null; x = x.next)
result[i++] = x.item;

if (a.length> size)
a[size] = null;

return a;
}

#hashCode() 方法，求 LinkedList 的哈希值。代码如下：

public int hashCode() {
int hashCode = 1;

for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}

• 该方法，是通过父类 AbstractList 来实现的，通过 for 来遍历 LinkedList ，然后进行求哈希。可能有胖友不了解 for(:) 语法糖，它最终会编译转换成 Iterator 迭代器。

#equals(Object o) 方法，判断是否相等。代码如下：

public boolean equals(Object o) {

if (o == this)
return true;

if (!(o instanceof List))
return false;

ListIterator e1 = listIterator();
ListIterator e2 = ((List) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1null ? o2null : o1.equals(o2)))
return false;
}

return !(e1.hasNext() || e2.hasNext());
}

• 该方法，是通过父类 AbstractList 来实现的，通过迭代器，实现遍历比对。

#clear() 方法，清空链表。代码如下：

public void clear() {

for (Node x = first; x != null; ) {

Node next = x.next;

x.item = null;
x.next = null;
x.prev = null;

x = next;
}

first = last = null;

size = 0;

modCount++;
}

#writeObject(java.io.ObjectOutputStream s) 方法，实现 LinkedList 的序列化。代码如下：

@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {

s.defaultWriteObject();

s.writeInt(size);

for (Node x = first; x != null; x = x.next)
s.writeObject(x.item);
}

#readObject(java.io.ObjectInputStream s) 方法，反序列化数组。代码如下：

@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {

s.defaultReadObject();

int size = s.readInt();

for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}

#clone() 方法，克隆 LinkedList 对象。代码如下：

public Object clone() {

LinkedList clone = superClone();

clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;

for (Node x = first; x != null; x = x.next)
clone.add(x.item);

return clone;
}

• 注意，first、last 等都是重新初始化进来，不与原 LinkedList 共享。

#subList(int fromIndex, int toIndex) 方法，创建 ArrayList 的子数组。代码如下：

public List subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size());

return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}

• 该方法，是通过父类 AbstractList 来实现的。
• 根据判断 RandomAccess 接口，判断是否支持随机访问，从而创建 RandomAccessSubList 或 SubList 对象。这里，我们就不拓展开解析这两个类，感兴趣的胖友自己去瞅瞅噢。

#iterator() 方法，创建迭代器。代码如下：

public Iterator iterator() {
return listIterator();
}

public ListIterator listIterator() {
return listIterator(0);
}

public abstract ListIterator listIterator(int index);

• 该方法，是通过父类 AbstractSequentialList 来实现的。
• 整个调用过程是，iterator() => listIterator() => listIterator(int index) 的顺序，就是我们在代码里贴进去的顺序。最终呢，是调用 LinkedList 对 #listIterator(int index) 的实现，我们在 「22. 创建 ListIterator 迭代器」 小节来看。

#listIterator(int index) 方法，创建 ListIterator 迭代器。代码如下：

public ListIterator listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}

• 创建 ListItr 迭代器。

因为 ListItr 的实现代码比较简单，我们就不逐个来看了，直接贴加了注释的代码。代码如下：

private class ListItr implements ListIterator {

private Node lastReturned;

private Node next;

private int nextIndex;

private int expectedModCount = modCount;

ListItr(int 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;
}

public boolean hasPrevious() {
return nextIndex > 0;
}

public E previous() {

checkForComodification();

if (!hasPrevious())
throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;

nextIndex—;

return lastReturned.item;
}

public int nextIndex() {
return nextIndex;
}

public int previousIndex() {
return nextIndex - 1;
}

public void remove() {

checkForComodification();

if (lastReturned == null)
throw new IllegalStateException();

Node lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)
next = lastNext;
else
nextIndex—;

lastReturned = null;

expectedModCount++;
}

public void set(E e) {

if (lastReturned == null)
throw new IllegalStateException();

checkForComodification();

lastReturned.item = e;
}

public void add(E e) {

checkForComodification();

lastReturned = null;

if (next == null)
linkLast(e);
else
linkBefore(e, next);

nextIndex++;

expectedModCount++;
}

public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);

while (modCount == expectedModCount && nextIndex < size) {

action.accept(next.item);

lastReturned = next;

next = next.next;

nextIndex++;
}

checkForComodification();
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

}

• 虽然有点长，但是保持淡定哟。

咳咳咳，总体还是有点长，不过相比 ArrayList 来说，LinkedList 确实简单蛮多。主要篇幅长的原因，还是因为 LinkedList 实现了 Deque 接口，需要多实现很多方法。

下面，我们来对 LinkedList 做一个简单的小结：

• LinkedList 基于节点实现的双向链表的 List ，每个节点都指向前一个和后一个节点从而形成链表。
• LinkedList 提供队列、双端队列、栈的功能。> 因为 first 节点，所以提供了队列的功能的实现的功能。
  因为 last 节点，所以提供了栈的功能的实现的功能。
  因为同时具有 first + last 节点，所以提供了双端队列的功能。

• LinkedList 随机访问平均时间复杂度是 O(n) ，查找指定元素的平均时间复杂度是 O(n) 。
• LinkedList 移除指定位置的元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。> 最好时间复杂度发生在头部、或尾部移除的情况。

• LinkedList 移除指定位置的元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。> 最好时间复杂度发生在头部移除的情况。

• LinkedList 添加元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。> 最好时间复杂度发生在头部、或尾部添加的情况。

因为 LinkedList 提供了多种添加、删除、查找的方法，会根据是否能够找到对应的元素进行操作，抛出 NoSuchElementException 异常。我们整理了一个表格，避免胖友错误使用。

😈 这个表主要整理了 List 和 Queue 的操作，暂时没有整理 Deque 的操作。因为，Deque 相同前缀的方法，表现结果同 Queue 。

OK ，还是在结尾抛个拓展，在 Redis List 的数据结构，实现方式是类似 Java LinkedList 的方式，感兴趣的胖友可以自己去瞅瞅。
http://svip.iocoder.cn/JDK/Collection-LinkedList/