啃透JDK源码-LinkedLis

JavaEdge

发布于 2020-05-26 17:00:36

4940

文章被收录于专栏：JavaEdgeJavaEdge

0 前言

与 ArrayList 一样实现了 List 接口，只是 LinkedList 底层结构为链表.在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 稍逊.

其允许元素包括 null.除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

该类还实现了 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）.

1 继承体系

LinkedList 继承自 AbstractSequentialList，又实现了 List、Deque、Cloneable、Serializable等接口. AbstractSequentialList相较于AbstractList(ArrayList的父类),只支持次序访问，而不支持随机访问，因为它的get(int index) ,set(int index, E element), add(int index, E element), remove(int index) 都是基于迭代器实现的。

Deque - 线性 collection，支持在两端插入和移除元素，定义了双端队列的操作.

2 属性

双向链表定义方式.

头节点的指针.不变性约束条件：(first == null && last == null) || (first.prev == null && first.item != null)

尾节点的指针.不变性约束条件:(first == null && last == null) || (last.next == null && last.item != null)

表示 LinkedList 的大小

节点Node

可以看出，这是一个典型的双向链表的结构

3 构造方法

3.1 无参

构造一个空list

3.2 有参

构造一个包含指定 collection 中的元素的list，这些元素按其 collection 的迭代器返回的顺序排列。

下面开始看各大核心 API 细节.

4 add

4.1 末尾添加

add(E e)

将指定元素添加到此 list 的末尾

linkLast(E e)

add(E e)等价于addLast(E e),因为 LinkedList 实现了 Deque 接口.

addLast(E e)

核心都是linkLast方法.

图解末尾添加

4.2 首位添加

addFirst(E e)

linkFirst(E e)

图解首位添加

主要流程：

将原 first 节点保存到 f
将插入元素封装成 newNode，并且该新节点的next指向原来的头节点，即f
若原来的头节点 f 为null，那么新插入头节点也是 last 尾节点，否则设置 f 的前置节点为NewNode，即 NewNode 现在是first 头节点.
size加一，修改计数器加一

4.3 指定位置插入

add(int index, E element)

首先调用checkPositionIndex检查index值是否在范围内

checkPositionIndex

isPositionIndex

判断参数是否为迭代器或者添加操作的有效位置的索引.

如果index在最后的话，就调用在尾部插入的函数，否则调用LinkBefore

LinkBefore

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

void linkBefore(E e, Node<E> succ) { //在succ节点前插入newNode // assert succ != null; // 将 succ 的前驱结点记为 pred final Node<E> pred = succ.prev; // 以 pred 为前驱结点，以 succ 为后继节点新建 newNode final Node<E> newNode = new Node<>(pred, e, succ); // 将 newNode 设为 succ 的前驱节点 succ.prev = newNode; if (pred == null) // 若原 succ 的前驱节点为null，则新插入的就是 first 头节点 first = newNode; else // 否则，要把newNode设为原来pred节点的后继节点 pred.next = newNode; size++; modCount++; }

图解指定位置插入元素

5 remove

因为 Deque 接口，所以本类也实现了如下方法支持双端操作:

5.1 removeFirst()

unlinkFirst(Node f)

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

private E unlinkFirst(Node<E> f) { // assert f == first && f != null; // 将 f.item 暂存 element final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // 辅助 GC // next成为实际的first节点 first = next; if (next == null) // next为空的话，因为next是第一个节点，所以链表都是空的，last也为空 last = null; else next.prev = null; // next不为空，也要将它的前驱节点记为null，因为next是第一个节点 size--; // 节点数减一 modCount++; // 修改计数器加1 return element; }

5.2 removeLast

unlinkLast

删除非空的尾节点

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; // 将尾节点的前驱节点记为 prev，它将成为last节点 final Node<E> prev = l.prev; l.item = null; l.prev = null; // 辅助 GC // 设置刚才记录的前驱节点为last last = prev; if (prev == null) // prev 为 null，说明要删除的l前面原来没前驱节点，那么删了l，整个链表为空 first = null; else // prev成为最后一个节点，没有后继节点 prev.next = null; size--; modCount++; return element; }

remove(int index)

在指定index删除

检验index是否合法.如果删除成功，返回删除的节点。具体实现在unlink

unlink

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25	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; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }

图解 unlink 过程

流程如下:
- 将删除的节点保存在element，同时把要删除节点的前驱节点标记为prev,后继节点标记为next
- 若prev为null，则 next 节点直接为 first 节点，反之把prev的next指向next节点，如图上面弯曲的红色箭头
- 若 next 为空，那么prev节点直接为last节点，反之把next的prev指向prev节点，如图下面弯曲的蓝色箭头
- 把要删除的节点置空，返回第一步保存的element