Java常用集合源码分析 Ⅰ

本文最后更新于:2021年8月10日 晚上

Java常用集合源码分析 Ⅰ

@Version: JDK 1.8

@IDE: IntellJ IDEA 2021.1

@Date: 2021/8/7

@Author: Hypocrite30

一、集合

  • 集合主要分为两大类:Collection & Map

Ⅰ、Collection接口

  • 有些实现类有序「List」,有些无序「Set」
  • 有些可放重复元素,有些不可以
  • Collection 接口没有直接的实现子类,通过子接口「Set」「List」实现

Ⅱ、Iterator接口

  • 因为Collection<E> extends Iterable<E> ,所以所有子类都可以通过获取 Iterator 遍历集合

常见方法:

boolean hashNext() Returns: true if the iteration has more elements
E next() Returns: the next element in the iteration
void remove() Removes from the underlying collection the last element returned by this iterator

📌:在调用 iterator.next() 之前必须调用 iterator.hasNext() 判断后面是否存在元素。若不调用,到最后一个元素,调用 next() 会抛出 NoSuchElementException

Ⅲ、List接口

  • 元素有序
  • 可重复
  • 支持索引
  • 每个元素有一个整数型序号,记录元素在容器中的位置,可用于存取

二、ArrayList

  • ArrayList 可以存放任何数据,包括 null
  • ArrayList 基本等同于 Vector,区别在于前者是线程不安全的「执行效率高」
  • ArrayList 内部存储数据结构为数组

Ⅰ、Field

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
26
27
28
29
30
31
/**
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空数组容量为0,有参构造默认使用的存储数据结构
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 空数组容量为0,无参构造时默认使用的存储数据结构
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 这ArrayList底层用到的存取数据的数组
* 非私有,以简化嵌套类访问
* transient 不允许序列化
*/
transient Object[] elementData;

/**
* 实际ArrayList集合大小
*/
private int size;

/**
* 可分配的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

📌几点说明:

  • 无参构造,数组默认初始化容量是 10
  • 预先创建好两个空数组,在构造过程中,直接赋值给存储数组
  • 真正存储数据的数组是 Object[] elementData,并且被 transient 修饰,这样序列化不会将其写入流中,但是这样反序列化会丢失数据,需要分析 writeObject(ObjectOutputStream s)readObject(ObjectInputStream s) 得到[序列化如何实现](#ArrayList 序列化与反序列化)
  • 注意到 MAX_ARRAY_SIZE 数组最大长度是 Integer.MAX_VALUE - 8,[下面说明](#MAX_ARRAY_SIZE 数值说明)

ArrayList 序列化与反序列化

  • private void writeObject(java.io.ObjectOutputStream s) 序列化
    • 序列化写入到流中有:size & element元素值
    • elementData[] 只做缓存数组,通常会预留容量,不够才扩容,因此序列化只取数组中需要的元素,节省空间和时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 预期的修改次数,用于判断并发修改的问题
int expectedModCount = modCount;
s.defaultWriteObject();

// 写入 ArrayList size
s.writeInt(size);

// 写入每一个元素值
for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}
// 判断序列化的并发问题
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
  • private void readObject(java.io.ObjectInputStream s) 反序列化
    • 因为构造此 ArrayList 已经有模板和数据「序列化保存的size&element」所以使用 EMPTY_ELEMENTDATA 作为空数组,而不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    • 根据 size 读入元素数据
    • 按序列化正确顺序存入存储数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 这里的 EMPTY_ELEMENTDATA 就是字段中的用于给有参构造用的空数组
elementData = EMPTY_ELEMENTDATA;

// 按照 size 读入数据
s.defaultReadObject();

// 读取容量
s.readInt(); // ignored

if (size > 0) {
// 与 clone() 类似,根据大小而不是容量分配阵列
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);

Object[] a = elementData;
// 按正确顺序读入所有元素
for (int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}

MAX_ARRAY_SIZE 数值说明

1
2
3
4
5
6
7
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

官方注释解释,有些虚拟机会保留一些字段空间,如果用满 Integer.MAX_VALUE 可能会 OOM。

StackOverflow 上的部分解释提及到「内存模型里的对象头的组成」<span class=”hint–top hint–rounded” aria-label=”Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?

“>[1]

于是对于 Java数组对象 剖析<span class=”hint–top hint–rounded” aria-label=”Anatomy of a Java array object

“>[2]

IBM官方说到「与Java对象相比,区别在于数组对象有一个额外的元数据,用于表示 数组的大小

剖析 Java对象 <span class=”hint–top hint–rounded” aria-label=”Anatomy of a Java object

“>[3]

不同的JVM厂商对元数据数量的设计有差异,但通常包括:

  • Class:指向类信息的指针,即类型指针。指向方法区中的类元信息。
  • Flags:描述对象状态的标志集合,包括 hashcode 和 shape「对象是否为数组」
  • Lock: 对象的同步信息「当前对象是否同步」

Java数组对象 还多一个 Size,即数组的大小。

对象头的大小不能超过 8 字节

标记字 Mark Word「哈希值、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳」在 32 位架构占 4 byte,64 位架构占 8 byte;类型指针Klass pointer 在 32 为架构上具有字长,但如果堆地址可以用 4 byte 编码,则依然可以占 4 byte。

📌:所以为了保险起见「防止OOM」,最大数组长度设置为 Integer.MAX_VALUE - 8

Ⅱ、Constructor

无参构造

1
2
3
4
5
6
/**
* 构造一个初始容量为10的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
  • 这里的初始容量为 10,在字段 DEFAULT_CAPACITY = 10 体现出来的

有参构造

1
2
3
4
5
6
7
8
9
10
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
  • 构造一个具有指定初始容量的空列表
  • 如果入参为负数,则抛出异常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList(Collection<? extends E> c) {
// 按正确顺序包含此列表中所有元素的数组
Object[] a = c.toArray();
// 先更新 size 值,再判断。如果是空数组则直接使用默认空数组
if ((size = a.length) != 0) {
// 判断 c 集合是不是ArrayList,是则直接赋值
if (c.getClass() == ArrayList.class) {
elementData = a;
} else { // 否则手动拷贝一份 Object[]
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
  • 按照集合迭代器返回的顺序,构造包含指定集合元素的列表。即传入一个集合类
  • 传入 null 则抛出 NullPointerException

Ⅲ、Method

增添元素 add(E e)

  • 添加元素 e
1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
  • ensureCapacityInternal(int minCapacity) 检查是否扩容,确保容量至少达到 size + 1,在此过程中,modCount 会增加,因为扩容属于修改操作。

  • 确保容量够后,将值存入数组「elementData」同时 size ++

添加元素 add(int index, E element)

  • 在指定 index 位置插入元素,其后的元素都向右移动
1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
1
2
3
4
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
  • 先检查 index 的合法性
  • 检查是否扩容,确保容量至少达到 size + 1,期间 modCount 增加
  • [index, size] 的元素向后移动一个单位
  • 插入元素,更新 size 值

删除 remove(int index)

  • 删除下标为 index 的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; // 方便 GC

return oldValue;
}
1
2
3
4
5
6
7
8
// 上述使用到的方法实现
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
  • 检查 index 合法性,修改计数器 modCount ++
  • 获取旧元素,作为方法返回值
  • 计算需要还原的后面的元素个数为 size - index - 1
  • 后面的元素全部向前移动一个单位,旧元素被覆盖
  • 删除操作前数组的最后一位置空,方便 GC

删除 remove(Object o)

  • 删除指定元素 o
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
// 没有返回值的 remove(int index)
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 方便 GC
}
  • 简单的 for - loop 找值,同时也能找到存储进去的 null 值「非扩容部分的 null」条件是 index < size

删除 clear()

  • 清空所有元素值
1
2
3
4
5
6
7
public void clear() {
modCount++;
// 方便 GC
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
  • 修改计数器自增;元素置空,便于GC;最后修改 size

修改 set(int index, E element)

  • 将 index 位置的元素值修改为 element
1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
  • 先检查 index 的合法性
  • 获取旧值;修改
  • 返回旧值

查找 get(int index)

  • 查找并返回 index 位置的值
1
2
3
4
5
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

扩容机制

  • 确保存储数组的容量至少达到 minCapacity 的大小
1
2
3
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
  • 计算预期数组容量
    • elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 判断当前数组是不是无参构造创造出来的容量为0的数组
    • 如果是,则计算出来的数组容量即为 size + 1,即 0 + 1,因为默认空数组size == 0
    • 否则直接返回 minCapacity,即传进来的 [size + 1](#增添元素 add(E e))
1
2
3
4
5
6
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

📌Q:if 语句返回的一直都是 minCapacity「因为正数minCapacity > DEFAULT_CAPACITY (0)」,而 if 语句外也是返回 minCapacity。设计意义在哪?

A:假设传入的 minCapacity 是负数,即 add() 中的 size + 1 仍为负数,则会返回 DEFAULT_CAPACITY AKA 10,即无参构造默认创建容量为 10 的数组,所以这么设计可以解决非法入参。

Q:为什么要判断「elementData」是否是 默认空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA

A:其实此 if 语句只有第一次扩容会使用到,真正的扩容 grow() 在每一次扩容都会创建出新的数组覆盖掉 elementData,扩容之后肯定就能确保入参 minCapacity 是正数([size + 1](#增添元素 add(E e))),不需要再判断。

  • 确保明确的容量,做扩容前的最后一次确认
    • 修改计数器自增
    • 判断刚才计算的预期数组容量 是否大于 当前数组容量
1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

📌官方在条件判断这里注解了 溢出警告「overflow-conscious」,这里涉及到 a < ba - b < 0 区别的问题,[下文说明](#关于 a < b 与 a - b < 0 应用说明)。

  • 扩容操作
    • 获取旧容量,根据旧容量的 1.5 倍大小作为新容量,使用位运算提高效率。
    • 两个特殊判断后,进行扩容,使用的是 Arrays.copyOf 扩容,这会创建出新数组覆盖原数组
1
2
3
4
5
6
7
8
9
10
11
12
13
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // AKA 1.5倍扩容
// 只有第一次才会 true 修改新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量太大,则按照大容量处理方式
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

📌Q:第一个条件 newCapacity < minCapacity 判断奇怪,新容量为什么会比预测容量小。预测容量是 size + 1,即所有数据长度 + 1,而新容量是在原容量基础上扩大 1.5 倍,肯定比 minCapacity 要大。

A:在无参构造创建空数组时,oldCapacity 原容量为 0,扩大 1.5 倍仍然为 0。此时新容量自然比预测容量要小,将值为0的 newCapacity 更新为 预测容量。而在此之后,这一更新操作都不会进行,因为扩容容量肯定比预测容量大「(x1.5) > (+ 1)」。

  • 大容量处理方式
    • int 型一直累加到负数,说明已经超出 int 存储的最大值了,抛异常
    • 预测容量 > 允许的最大容量,则让新容量为 int 最大值,否则为 MAX_ARRAY_SIZE,即 Integer.MAX_VALUE - 8,相当于给一个稳妥的值,[不至于OOM](#MAX_ARRAY_SIZE 数值说明)。
1
2
3
4
5
6
7
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
  • Arrays 工具类扩容
    • 最终都会调用本地方法 arraycopy() 进行扩容
    • 可以看到,返回的 copy 数组都是 new 出来的,所以扩容会让存储数组变成不同对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);

关于 a < b 与 a - b < 0 应用说明

Q:看到上述扩容的很多条件判断使用的都是 a - b < 0 的形式,而不是直接比较,这种设计的好处在哪?

在数学中,这两个不等式是完全等价的。但在计算机中,需要考虑到存储的问题,有可能会出现变量 a | b 出现

溢出的情况。

🌰Demo [4]

1
2
3
4
int a = Integer.MAX_VALUE;
int b = Integer.MIN_VALUE;
if (a < b) System.out.println("a < b");
if (a - b < 0) System.out.println("a - b < 0");

结果:a - b < 0

  • 正常情况下,a 肯定小于 b
  • 但是结果是 a - b < 0 为 true,即 a < b

分析:a - b 超出 int 存储最大范围,于是溢出,变成负数

ArrayList 前的判断:

1
2
3
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);

官方也提出 溢出警告

  • 使用 a < b 形式

    • 如果 minCapacity 过大,溢出变成负数,此时不会扩容,然而此情况是有扩容需求的
  • 使用 a - b < 0 形式

    • 如果 minCapacity 过大,溢出为负数,而减去一个正数又会回到正数,此时就会顺利进入扩容中

grow() :

1
2
3
4
5
6
7
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

同样也有溢出警告

  • 使用 a < b 形式
    • newCapacity 如果扩容 1.5 倍后太大溢出为负数,则会小于 minCapacity,会更新 newCapacity = minCapacity;
    • 下一个条件判断,newCapacity 为负数 会小于 MAX_ARRAY_SIZE,所以不会进行 超大容量处理,则会出现问题
  • 使用 a - b < 0 形式
    • 第一个条件判断,溢出为负数的 newCapacity,减去正数 minCapacity 结果大于 0,不更新 newCapacity,即只有第一次扩容「空数组」会更新
    • 第二个条件判断,同理,会执行超大容量处理,合乎逻辑。

三、Vector

  • 因为方法上加了 synchronized,是方法级的锁,所以是线程安全的。
  • 大部分逻辑和设计与 ArrayList 相同

Ⅰ、Field

1
2
3
4
5
6
// 存储数组
protected Object[] elementData;
// 真实元素的数量
protected int elementCount;
// 扩容因子,详细作用见扩容函数
protected int capacityIncrement;

Ⅱ、Constructor

无参构造

  • 无参构造默认的数组长度是 10
1
2
3
public Vector() {
this(10);
}

有参构造

  • 自定义数组长度,默认的扩容因子是 0,即扩容是 2 倍扩容
1
2
3
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
  • 自定义数组长度 & 扩容因子
1
2
3
4
5
6
7
8
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
  • 按照传入的集合初始化
1
2
3
4
5
6
7
8
9
public Vector(Collection<? extends E> c) {
Object[] a = c.toArray();
elementCount = a.length;
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, elementCount, Object[].class);
}
}

Ⅲ、Method

  • 大部分方法都与 ArrayList 相同

扩容机制

1
2
3
4
5
6
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
  • 扩容前的检查
1
2
3
4
5
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
  • 📌扩容
1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity); // 扩容机制
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

newCapacity 是旧容量 加上一个值,三目运算符判断扩容因子是多少,如果是默认的 0 或者小于 0,则扩容两倍。

否则扩容 1 + capacityIncrement

四、LinkedList

  • 使用的数据结构是 双向链表
  • 继承了 ListDeque,所以可以当成列表集合 和 双端队列
  • 非线程安全;使之线程安全的办法是调用 Collections 工具类的 synchronizedList(List<T> list) 方法转化成线程安全的集合
1
List list = Collections.synchronizedList(new LinkedList(...));

Ⅰ、Field

1
2
3
4
5
6
// 节点(元素)个数
transient int size = 0;
// 指向第一个节点的指针。
transient Node<E> first;
// 指向末尾节点
transient Node<E> last;

根据双向链表储存特点

在运行中的不变量:

1
2
(first == null && last == null) || (first.prev == null && first.item != null)
(first == null && last == null) || (last.next == null && last.item != null)

静态内部类

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;
}
}
  • 由此可看出底层数据结构是 双向链表

Ⅱ、Constructor

无参构造

1
2
3
// Constructs an empty list.
public LinkedList() {
}

有参构造

  • 将入参集合元素添加进新的 LinkedList 集合
1
2
3
4
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

Ⅲ、Method

添加 add(E e)

  • 添加元素,使用[尾插法](#尾插法添加元素 linkLast(E e))
1
2
3
4
public boolean add(E e) {
linkLast(e);
return true;
}

添加 add(int index, E element)

  • 添加元素到指定下标位置
    • 检查下标合法性
    • 判断插入位置是在末尾「[尾插](#尾插法添加元素 linkLast(E e))」还是在「[插入非空节点之前](#插入元素到非空节点之前 linkBefore(E e, Node succ))」
    • 「插入非空节点之前」用到 [node(int index)](#检索节点在链表的下标位置 node(int index)) 计算返回下标位置节点
1
2
3
4
5
6
7
8
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
1
2
3
4
5
6
7
8
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 检查下标合法性 index ∈ [0, size]
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}

添加 addFirst(E e)

  • [插入元素到链表头](#插入元素到链表头 linkFirst(E e))
1
2
3
public void addFirst(E e) {
linkFirst(e);
}

添加 addLast(E e)

  • [插入元素到链表尾](#尾插法添加元素 linkLast(E e))
1
2
3
public void addLast(E e) {
linkLast(e);
}

删除 remove(Object o)

  • 删除指定元素的第一个匹配项

    • if 待删除元素为 null
      • 从头查找第一个 null,从链表[断开节点](#删除节点 unlink(Node x))
    • else 待删除元素不空
      • 从头查找第一个值符合的元素,从链表[断开节点](#删除节点 unlink(Node x))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

尾插法添加元素 linkLast(E e)

  • l 指针指向链表尾部,用于标记原链表尾
  • 根据 Node(Node<E> prev, E element, Node<E> next) 创建值为 e,前驱为 llast,后继为 null 的节点,这么构造符合尾节点特点
  • 链表尾指针移动到新链表尾
  • if 原链表尾是 null
    • 说明「链表为空」,此时插入的为第一个节点,因此头指针也指向新节点
  • else 原链表不为 null
    • 说明「链表不空」,尾插到链表上
  • size & modCount 自增
1
2
3
4
5
6
7
8
9
10
11
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

插入元素到非空节点之前 linkBefore(E e, Node succ)

  • 断言 index节点非空
  • 获得 index 节点前驱 pred
  • 创建节点,值为 e,前驱为 pred,后继为 succ
  • 后继连接上新节点
  • if 前驱为空
    • 说明「插入位置在链表头」,头指针指向新节点
  • else 后继为空
    • 说明「插入位置在中间」,前驱指向新节点
  • size & modCount 自增
1
2
3
4
5
6
7
8
9
10
11
12
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

插入元素到链表头 linkFirst(E e)

  • 获得头节点
  • 创建节点,值为 e,前驱为 null,后继为 f,即旧头结点
  • 头指针移到新节点
  • if 旧头节点为空
    • 说明「链表为空」,尾指针指向新节点
  • else 旧头节点不空
    • 说明「链表不空」,连接 新节点&旧头结点
  • size & modCount 自增
1
2
3
4
5
6
7
8
9
10
11
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
  • 断言 节点不空
  • 获取 该节点 element、前驱 prev 和后继 next
  • if 前驱为空
    • 说明「该节点为头节点」,头指针直接指向后继
  • else 前驱不空
    • 说明「该节点非头节点」,前驱指向后继,再断「x 指向前驱」
  • 双向链表,后面的方向道理同上
  • size 自减, modCount 自增,元素置空,返回删除的节点
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;
}

检索节点在链表的下标位置 node(int index)

  • 断言 index∈[0, size)
  • if 下标在左半边
    • 从头向中间检索
  • else 下标在右半边
    • 从后向中间检索

📌二分思想,利用好双向链表,同时头尾节点都是固定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

获取元素四种方法的区别

getFirst() & getLast() & peekFirst() & peekLast()

1
2
3
4
5
6
7
8
9
10
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
  • 很明显,peek 类型的方法在空链表时会返回 nullget 类型则抛出异常 NoSuchElementException

LinkedList 作双端队列和栈的细节

因为 LinkedList 同时也实现了 Deque 接口,所以可以作为双端队列,自然也可以当做「一开一闭」。

1
2
3
4
5
6
7
8
9
public class Solution {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack);
}
}

[3, 2, 1]

  • 队列
1
2
3
4
5
6
7
8
9
public class Solution {
public static void main(String[] args) {
Deque<Integer> queue = new ArrayDeque<Integer>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue);
}
}

[1, 2, 3]

既然可以同时作队列和栈,引发思考,同为 peek() 获得「栈顶」| 「队头」元素,那么猜测队列首部栈顶开口同个方向的。

  • 查看 Dequepeek() 官方注释
1
2
3
4
5
6
7
8
9
10
11
/**
* Retrieves, but does not remove, the head of the queue represented by
* this deque (in other words, the first element of this deque), or
* returns {@code null} if this deque is empty.
*
* <p>This method is equivalent to {@link #peekFirst()}.
*
* @return the head of the queue represented by this deque, or
* {@code null} if this deque is empty
*/
E peek();

peek() 返回 deque 队列头, 如果双端队列为空,则返回 null

  • 查看 LinkedList 实现的 peek()
1
2
3
4
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

获取左侧链表首部

  • 查看 ArrayDeque 实现的 peek()
1
2
3
public E peek() {
return peekFirst();
}

获取队列首部

📌结论:官方定义的左边(First)是栈首队列头。由此才能实现一个方法达到相同的peek 效果。

🔗Reference:


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!