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

「对象头的大小不能超过 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)] ↩

©著作权归作者所有,转载或内容合作请联系作者
禁止转载，如需转载请通过简信或评论联系作者。
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,294评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,493评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,790评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,595评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,718评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,906评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,053评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,797评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,250评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,570评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,711评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,388评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,018评论 3赞 316
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,796评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,023评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,461评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,595评论 2赞 350

推荐阅读更多精彩内容