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，即数组的大小。

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

标记字 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))

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 效果。

🔗Reference：

---

1. Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8? ↩

2. Anatomy of a Java array object ↩

3. Anatomy of a Java object ↩

4. [Difference between if (a - b < 0) and if (a < b)] ↩