Java常用集合源码分析 Ⅰ
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
/**
* 默认初始化容量
*/
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[]
只做缓存数组,通常会预留容量,不够才扩容,因此序列化只取数组中需要的元素,节省空间和时间。
- 序列化写入到流中有:
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
读入元素数据 - 按序列化正确顺序存入存储数组中
- 因为构造此
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 数值说明
/**
* 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 上的部分解释提及到「内存模型里的对象头的组成」[1]
于是对于 Java数组对象 剖析[2]
IBM官方说到「与Java对象相比,区别在于数组对象有一个额外的元数据,用于表示 数组的大小」
剖析 Java对象 [3]
不同的JVM厂商对元数据数量的设计有差异,但通常包括:
- Class:指向类信息的指针,即类型指针。指向方法区中的类元信息。
- Flags:描述对象状态的标志集合,包括 hashcode 和 shape「对象是否为数组」
- Lock: 对象的同步信息「当前对象是否同步」
而 Java数组对象 还多一个 Size,即数组的大小。
标记字 Mark Word「哈希值、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳」在 32 位架构占 4 byte,64 位架构占 8 byte;类型指针Klass pointer 在 32 为架构上具有字长,但如果堆地址可以用 4 byte 编码,则依然可以占 4 byte。
📌:所以为了保险起见「防止OOM」,最大数组长度设置为 Integer.MAX_VALUE - 8
Ⅱ、Constructor
无参构造
/**
* 构造一个初始容量为10的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 这里的初始容量为 10,在字段
DEFAULT_CAPACITY = 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);
}
}
- 构造一个具有指定初始容量的空列表
- 如果入参为负数,则抛出异常
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
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 位置插入元素,其后的元素都向右移动
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++;
}
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 的元素
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;
}
// 上述使用到的方法实现
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
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;
}
// 没有返回值的 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()
- 清空所有元素值
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
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 先检查 index 的合法性
- 获取旧值;修改
- 返回旧值
查找 get(int index)
- 查找并返回 index 位置的值
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
扩容机制
- 确保存储数组的容量至少达到
minCapacity
的大小
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))
-
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))),不需要再判断。
- 确保明确的容量,做扩容前的最后一次确认
- 修改计数器自增
- 判断刚才计算的预期数组容量 是否大于 当前数组容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
📌官方在条件判断这里注解了 溢出警告「overflow-conscious」,这里涉及到 a < b
与 a - b < 0
区别的问题,[下文说明](#关于 a < b 与 a - b < 0 应用说明)。
- 扩容操作
- 获取旧容量,根据旧容量的 1.5 倍大小作为新容量,使用位运算提高效率。
- 两个特殊判断后,进行扩容,使用的是
Arrays.copyOf
扩容,这会创建出新数组覆盖原数组
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 数值说明)。
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 出来的,所以扩容会让存储数组变成不同对象
- 最终都会调用本地方法
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]:
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 前的判断:
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
官方也提出 溢出警告
-
使用
a < b
形式- 如果
minCapacity
过大,溢出变成负数,此时不会扩容,然而此情况是有扩容需求的
- 如果
-
使用
a - b < 0
形式- 如果
minCapacity
过大,溢出为负数,而减去一个正数又会回到正数,此时就会顺利进入扩容中
- 如果
grow()
:
// 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
// 存储数组
protected Object[] elementData;
// 真实元素的数量
protected int elementCount;
// 扩容因子,详细作用见扩容函数
protected int capacityIncrement;
Ⅱ、Constructor
无参构造
- 无参构造默认的数组长度是 10
public Vector() {
this(10);
}
有参构造
- 自定义数组长度,默认的扩容因子是 0,即扩容是 2 倍扩容
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
- 自定义数组长度 & 扩容因子
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
- 按照传入的集合初始化
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
相同
扩容机制
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
- 扩容前的检查
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- 📌扩容
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
- 使用的数据结构是 双向链表
- 继承了
List
和Deque
,所以可以当成列表集合 和 双端队列 - 非线程安全;使之线程安全的办法是调用
Collections
工具类的synchronizedList(List<T> list)
方法转化成线程安全的集合
List list = Collections.synchronizedList(new LinkedList(...));
Ⅰ、Field
// 节点(元素)个数
transient int size = 0;
// 指向第一个节点的指针。
transient Node<E> first;
// 指向末尾节点
transient Node<E> last;
根据双向链表储存特点
在运行中的不变量:
(first == null && last == null) || (first.prev == null && first.item != null)
(first == null && last == null) || (last.next == null && last.item != null)
静态内部类
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
无参构造
// Constructs an empty list.
public LinkedList() {
}
有参构造
- 将入参集合元素添加进新的
LinkedList
集合
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
Ⅲ、Method
添加 add(E e)
- 添加元素,使用[尾插法](#尾插法添加元素 linkLast(E e))
public boolean add(E e) {
linkLast(e);
return true;
}
添加 add(int index, E element)
- 添加元素到指定下标位置
- 检查下标合法性
- 判断插入位置是在末尾「[尾插](#尾插法添加元素 linkLast(E e))」还是在「[插入非空节点之前](#插入元素到非空节点之前 linkBefore(E e, Node<E> succ))」
- 「插入非空节点之前」用到 [node(int index)](#检索节点在链表的下标位置 node(int index)) 计算返回下标位置节点
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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))
public void addFirst(E e) {
linkFirst(e);
}
添加 addLast(E e)
- [插入元素到链表尾](#尾插法添加元素 linkLast(E e))
public void addLast(E e) {
linkLast(e);
}
删除 remove(Object o)
-
删除指定元素的第一个匹配项
-
if 待删除元素为
null
- 从头查找第一个
null
,从链表[断开节点](#删除节点 unlink(Node<E> x))
- 从头查找第一个
-
else 待删除元素不空
- 从头查找第一个值符合的元素,从链表[断开节点](#删除节点 unlink(Node<E> x))
-
if 待删除元素为
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
,前驱为l
即last
,后继为null
的节点,这么构造符合尾节点特点 - 链表尾指针移动到新链表尾
-
if 原链表尾是
null
- 说明「链表为空」,此时插入的为第一个节点,因此头指针也指向新节点
-
else 原链表不为
null
- 说明「链表不空」,尾插到链表上
-
size
&modCount
自增
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<E> succ)
- 断言
index
节点非空 - 获得
index
节点前驱pred
- 创建节点,值为
e
,前驱为pred
,后继为succ
- 后继连接上新节点
-
if 前驱为空
- 说明「插入位置在链表头」,头指针指向新节点
-
else 后继为空
- 说明「插入位置在中间」,前驱指向新节点
-
size
&modCount
自增
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
自增
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++;
}
删除节点 unlink(Node<E> x)
- 断言 节点不空
- 获取 该节点
element
、前驱prev
和后继next
-
if 前驱为空
- 说明「该节点为头节点」,头指针直接指向后继
-
else 前驱不空
- 说明「该节点非头节点」,前驱指向后继,再断「x 指向前驱」
- 双向链表,后面的方向道理同上
-
size
自减,modCount
自增,元素置空,返回删除的节点
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 下标在右半边
- 从后向中间检索
📌二分思想,利用好双向链表,同时头尾节点都是固定的。
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()
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
类型的方法在空链表时会返回null
,get
类型则抛出异常NoSuchElementException
LinkedList 作双端队列和栈的细节
因为 LinkedList
同时也实现了 Deque
接口,所以可以作为双端队列,自然也可以当做栈「一开一闭」。
- 栈
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]
- 队列
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()
获得「栈顶」| 「队头」元素,那么猜测队列首部和栈顶开口是同个方向的。
- 查看
Deque
的peek()
官方注释
/**
* 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()
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
获取左侧链表首部
- 查看
ArrayDeque
实现的peek()
public E peek() {
return peekFirst();
}
获取队列首部
📌结论:官方定义的左边(First)是栈首
,队列头
。由此才能实现一个方法达到相同的peek 效果。