两万字长文读懂 Java 集合( 八 ) _Java

文章插图
由于以双向链表作为数据结构，它是线程不安全的集合；存储的每个节点称为一个 Node，下图可以看到 Node 中保存了 next 和 prev 指针，item 是该节点的值。在插入和删除时，时间复杂度都保持为 O(1)

文章插图
关于 LinkedList，除了它是以链表实现的集合外，还有一些特殊的特性需要注意的。

优势：LinkedList 底层没有扩容机制，使用双向链表存储元素，所以插入和删除元素效率较高，适用于频繁操作元素的场景
劣势：LinkedList 不具备随机访问的特点，查找某个元素只能从 head 或 tail 指针一个一个比较，所以查找中间的元素时效率很低
查找优化：LinkedList 查找某个下标 index 的元素时做了优化，若 index > (size / 2)，则从 head 往后查找，否则从 tail 开始往前查找，代码如下所示：

LinkedList.Node<E> node(int index) {LinkedList.Node x;int i;if (index < this.size >> 1) { // 查找的下标处于链表前半部分则从头找x = this.first;for(i = 0; i < index; ++i) { x = x.next; }return x;} else { // 查找的下标处于数组的后半部分则从尾开始找x = this.last;for(i = this.size - 1; i > index; --i) { x = x.prev; }return x;}}

双端队列：使用双端链表实现，并且实现了 Deque 接口，使得 LinkedList 可以用作双端队列。下图可以看到 Node 是集合中的元素，提供了前驱指针和后继指针，还提供了一系列操作头结点和尾结点的方法，具有双端队列的特性。

文章插图
LinkedList 集合最让人关注的是它的链表结构，但是我们同时也要注意它是一个双端队列型的集合。
Deque<Object> deque = new LinkedList<>;

文章插图
Queue 接口
Queue 队列，在 JDK 中有两种不同类型的集合实现：单向队列（AbstractQueue）和双端队列（Deque）

文章插图
Queue 中提供了两套增加、删除元素的 API，当插入或删除元素失败时，会有两种不同的失败处理策略。

文章插图
选取哪种方法的决定因素：插入和删除元素失败时，希望抛出异常还是返回布尔值
add 和 offer 对比：
在队列长度大小确定的场景下，队列放满元素后，添加下一个元素时，add 会抛出 IllegalStateException 异常，而 offer 会返回 false。
但是它们两个方法在插入某些不合法的元素时都会抛出三个相同的异常。

文章插图
remove 和 poll 对比：
在队列为空的场景下，remove 会抛出 NoSuchElementException 异常，而 poll 则返回。
get 和 peek 对比：
在队列为空的情况下，get 会抛出 NoSuchElementException 异常，而 peek 则返回。

Deque 接口Deque 接口的实现非常好理解：从单向队列演变为双向队列，内部额外提供双向队列的操作方法即可：

文章插图
Deque 接口额外提供了针对队列的头结点和尾结点操作的方法，而插入、删除方法同样也提供了两套不同的失败策略。除了 add 和 offer，remove 和 poll 以外，还有 get 和 peek 出现了不同的策略。

AbstractQueue 抽象类AbstractQueue 类中提供了各个 API 的基本实现，主要针对各个不同的处理策略给出基本的方法实现，定义在这里的作用是让子类根据其方法规范（操作失败时抛出异常还是返回默认值）实现具体的业务逻辑。

文章插图

LinkedListLinkedList 在上面已经详细解释了，它实现了 Deque 接口，提供了针对头结点和尾结点的操作，并且每个结点都有前驱和后继指针，具备了双向队列的所有特性。

ArrayDeque使用数组实现的双端队列，它是无界的双端队列，最小的容量是8（JDK 1.8）。在 JDK 11 看到它默认容量已经是 16了。