Java 容器源码分析之 LinkedList（1）

look_w

概览同 ArrayList 一样，LinkedList 也是对 List 接口的一种具体实现。不同的是，ArrayList 是基于数组来实现的，而 LinkedList 是基于双向链表实现的。LinkedList 类的声明如下：

1 2 3

public class LinkedList<E>     extends AbstractSequentialList<E>     implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 继承自 AbstractSequentialList，实现了 List 接口，同时还实现了 Deque 接口。AbstractSequentialList 是 AbstractList 的子类，为基于顺序访问的链表提供了一些基本的实现。LinkedList 实现了 Deque 接口，Deque 接口是一种双端队列，可以作为 FIFO 队列和 LIFO 队列（栈）来使用。LinkedList 支持所有元素，包括 null。
下面基于JDK 8 中的代码对LinkedList的实现加以分析。
底层结构LinkedList 基于双向链表进行实现，并使用两个引用 first 和 last 分别指向双向链表的头尾元素。同 ArrayList 一样，使用 modCount 来记录结构化修改的次数，并依此实现 fail-fast 机制。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || *            (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || *            (last.next == null && last.item != null) */ transient Node<E> last;

双向链表的节点结构如下，分别用 prev 和 next 指向该节点的前驱和后继结点。

1 2 3 4 5 6 7 8 9 10 11

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