源码阅读(6)：Java中主要的List、Deque结构——LinkedList集合（上）

1.java.util.LinkedList结构解析

LinkedList将是本专题讲解的最后一个主要List结构，也将是本专题讲解的第一个Queue结构的实现，也就是说LinkedList同时具有两种结构的基本特性。如下图所示：

从上图可以看出，LinkedList集合同时（间接）实现了List接口和Queue接口，而通过之前文章的介绍我们知道这两个接口分别代表了Java中三大集合结构（List、Queue、Set）的其中两个大类。为什么会有这样的设计呢？这是由LinkedList内部的组织结构决定的，且在JDK1.2之后，JDK1.6之前官方推荐使用LinkedList集合模拟“栈”结构。

1.1. LinkedList集合的组织结构

LinkedList集合中的主要结构是“双向链表”，双向连表中的若干节点并不要求有连续的存储。在这样的结构下双向链表一旦需要新增节点，就不需要像ArrayList数组那样一次性申请一块较大的连续的存储空间，而可以“按需”申请存储空间。LinkedList集合中每一个链表节点使用一个java.util.LinkedList.Node类的实例进行描述，下图描述了一个链表的基本结构：

由上图可知LinkedList.Node类的定义中有三个重要元素，

• item属性：这是一个泛型属性，用来在当前节点上存储具体的数据——实际上是指向堆内存地址的对象引用。
• next属性：这个属性的类型也是LinkedList.Node，它表示当前节点指向的下一个节点。
• prev属性：这个属性的类型同样也是LinkedList.Node，它表示当前节点指向的上一个节点。

请注意上图中所示双向链表的“头”“尾”结构，这两个位置所包括的在任何场景下都有效的规则是：

• “头”节点的prev属性在任何时候都为null。
• “尾”节点的next属性在任何时候都为null。

以下是LinkedList.Node类的详细代码——实际上描述代码很简单：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
  // ......
  // Node类的定义很简单
  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;
	}
  }
  // ......
} 

要有效构造、使用“双向链表”，LinkedList集合就需要一种手段对已存在的“双向链表”进行记录——一共三个变量完成记录：使用first变量记录链表的“头”节点；使用last变量记录链表的“尾”节点，并使用size变量记录链表的当前长度。代码片段如下所示：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // ......
    // 记录当前双向链表的长度
    transient int size = 0;
    /**
     * 指向当前双向链表的“头”节点
     * Invariant: (first == null && last == null) || (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    /**
     * 指向当前双向链表的“尾”节点
     * Invariant: (first == null && last == null) ||  (last.next == null && last.item != null)
     */
    transient Node<E> last;
    // ......
}

那么以下场景都是可能出现的正确场景：

• first == null && last == null
  
  当双向链表中没有任何节点时，first变量和last变量都指向null。LinkedList集合所描述的双向链表要么first变量和last变量都有引用，要么都指向null。

• first == last
  
  当双向链表中只有一个节点时，first变量和last变量将指向同一个节点的引用。

• first != null && last != null
  
  当双向链表中至少有一个节点时，first变量和last变量都不可能为null。

那么以下场景是不可能出现的：

• first != null && last == null 以及 first == null && last != null

是的，这个条件很好理解：上文已经说过，first变量和last变量，要么都不为null，要么都为null。

1.2. LinkedList集合的添加操作

由于LinkedList集合中的双向链表构造，导致了LinkedList集合和ArrayList集合的添加操作完全不一样。本小节我们将进行详细介绍。从JDK 1.8+ 版本开始，LinkedList集合中有三个关键的方法用于在链表的不同位置添加新的节点，它们是：linkFirst(E e)方法、linkLast(E e)方法和linkBefore(E e, Node succ)方法。

1.2.1. linkFirst(E e) 方法

linkFirst(E e)方法将会在双向链表的头部添加一个新的节点，并调整当前first变量的指向信息。以下是该方法的详细代码说明：

private void linkFirst(E e) {
  // 使用一个临时变量记录操作前first变量的信息
  final Node<E> f = first;
  // 创建一个数据信息为e的新节点，此节点的前置引用为null，后置引用指向原来的头结点
  final Node<E> newNode = new Node<>(null, e, f);
  // 这句很关键，由于是在双向链表的头部添加新的节点，所以实际上就是将first变量的信息基于newNode进行重设定
  first = newNode;
  // 如果条件成立，说明当前进行添加操作时双向链表没有任何节点
  // 于是需要将双向链表的last变量也同时指向这个新节点，让first标量和last指向同一个节点
  if (f == null)
    last = newNode;
  // 如果条件不成立，说明在操作前双向链表中至少有一个节点
  // 这时只需要将原来头结点的前置引用指向新的头结点newNode
  else
    f.prev = newNode;
  // 链表大小 + 1
  size++;
  // LinkedList集合的操作次数 + 1
  modCount++;
}

以上代码片段的注释已经非常详细，但是有的读者可能还是觉得有点头晕。没关系，我们用图形化的方式来表示以上的操作步骤，如下图所示：

1.2.2. linkLast(E e) 方法

linkLast(E e) 方法将在当前双向链表的“尾”节点之后添加一个新的节点，并调整当前last变量的指向。以下是该方法的详细代码说明：

void linkLast(E e) {
  // 使用一个临时变量记录操作前last变量的信息
  final Node<E> l = last;
  // 创建一个数据信息为e的新节点，此节点的前置引用为原来的“尾”节点，后置引用指向null
  final Node<E> newNode = new Node<>(l, e, null);
  // 这句很关键，由于是在双向链表的尾部添加新的节点，所以实际上就是将last变量的信息基于newNode进行重设定
  last = newNode;
  // 如果条件成立，说明当前进行添加操作时双向链表没有任何节点
  // 于是需要将双向链表的first变量也同时指向这个新节点，让first标量和last指向同一个节点
  if (l == null)
    first = newNode;
  // 如果条件不成立，说明在操作前双向链表中至少有一个节点
  // 这时只需要将原来尾结点的后置引用指向新的尾结点newNode
  else
    l.next = newNode;
  // 链表大小 + 1
  size++;
  // LinkedList集合的操作次数 + 1
  modCount++;
}

以上代码的注释信息也非常详细了，不过我们还是使用一张图例来表达以上的各个操作步骤：

1.2.3. linkBefore(E e, Node succ) 方法

linkBefore(E e, Node succ) 方法在指定的succ节点之前的位置插入一个新的节点，新的节点的item属性的值为e。请注意，LinkedList集合的操作逻辑保证了这里的succ入参节点一定不为null，且一定已经存在于当前LinkedList集合的某个位置。以下是该方法的详细代码：

void linkBefore(E e, Node<E> succ) {
  // 创建一个变量pred，记录当前succ节点的前置节点（注意，可能为null）
  final Node<E> pred = succ.prev;
  // 创建一个新的节点newNode，该节点的前倾节点指向succ节点的前倾节点
  // 该节点的后置节点指向succ节点
  final Node<E> newNode = new Node<>(pred, e, succ);
  // 将succ节点的前倾节点重新设置为创建的新节点newNode
  succ.prev = newNode;
  // 如果条件成立，说明当前succ节点原本就是双向链表的“头”节点
  // 也就是说，当前操作的实质是在链表的头部增加一个新节点
  // 这时将LinkedList集合中标识“头”节点first变量指向新创建的节点newNode。
  if (pred == null)
      first = newNode;
  // 其它情况下移动pred的后置节点为当前创建的新的节点newNode
  else
      pred.next = newNode;
  size++;
  modCount++;
}