ArrayList & LinkedList

🔍 基于JDK1.8的ArrayList和LinkedList的源码解析。

⚡ 涉及的API：Arrays#copyOf(U[] original, int newLength, Class<? extends T[]> newType)

用于数组克隆，参数如下：

original：原数组
newLength：新数组长度
newType：新数组类型

克隆时会有以下两种情况：

如果新数组的长度大于原数组，那么多出的部分用null填充。
如果新数组的长度小于原数组，那么多出的部分直接丢弃。

ArrayList

基本知识

始于：JDK 1.2
作者：Josh Bloch, Neal Gafter
实现：List, RandomAccess, Cloneable, Serializable
特点：
- 可存储任何类型数据（包括null）
- 可存储重复数据
- 存储数据保证有序性
- 非线程安全
类图：

基本属性

// 默认容量(10)
private static final int DEFAULT_CAPACITY = 10;

// 初始化容量为0使用
private static final Object[] EMPTY_ELEMENTDATA = {};

// 无参构造方法使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存放元素
transient Object[] elementData; 

// 数组长度/元素数量
private int size;

// 最大容量(2147483647 - 8 = 2147483639)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 继承自AbstractList，记录结构变化次数
protected transient int modCount = 0;

构造方法

// 带初始化容量的构造器
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() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 集合构造器，复制另一个集合中的全部内容
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

用途：向数组末尾添加元素。

public boolean add(E e) {
	// 确保容量足够
    ensureCapacityInternal(size + 1);
    // 添加到数组尾部
    elementData[size++] = e;
    return true;
}

// 确保容量足够
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算所需容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 说明刚刚创建
        return Math.max(DEFAULT_CAPACITY, minCapacity);  // 则取初始化容量和所需容量的最大值
    }
    return minCapacity; // 满足需要的最小容量
}

// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 结构改变次数+1

    // 需要的最小容量大于数组长度，则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容
private void grow(int minCapacity) {
    // 原数组长度
    int oldCapacity = elementData.length;
    // 新数组长度 = 原数组长度 * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 1.5倍不够则给予所需容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新的容量超过最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将原数组内容复制到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 更大的容量
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果所需最小容量大于2147483639，那么只能扩容到2147483647
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

首先确保容量，所需容量 = size + 1。

对于刚刚创建的ArrayList：所需容量 = max(初始化容量10，当前容量)。

如果所需容量大于数组长度，则进行扩容，默认扩容为1.5倍，不够则给予所需容量；

如果所需容量大于最大容量，那么只能扩容为Integer.MAX_VALUE。

最后将元素添加到数组尾部。

get方法

用途：获取执行下标的元素。

public E get(int index) {
    // 越界检查
    rangeCheck(index);
    return elementData(index);
}

// 越界则抛出异常
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 直接根据下标返回数组元素并进行类型转换
E elementData(int index) {
    return (E) elementData[index];
}

先进行越界检查，然后直接根据下标返回数组元素。

remove方法

用途：移除指定下标的元素。

public E remove(int index) {
    // 越界检查
    rangeCheck(index);

    // 结构改变次数+1
    modCount++;
    // 需要删除的元素
    E oldValue = elementData(index);

    // 需要移动的元素数量，oldValue后面所有的元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将oldValue后面的元素全部向前移动一个单位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // size - 1
    elementData[--size] = null; // clear to let GC do its work

    // 返回删除的值
    return oldValue;
}

先进行越界检查，然后将需要删除的元素之后的元素全部向前移动一位，并将数组尾部元素置为null。

trimToSize方法

用途：将数组容量调整为实际元素个数大小，当ArryList元素个数不发生改变时，可以调用该方法减少内存占用。

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        // 数组长度为0，则置为空数组
        // 否则复制一份新数组，长度为当前大小
        elementData = (size == 0) ? 
            EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }
}

LinkedList

基本知识

始于：JDK 1.2
作者：Josh Bloch
实现：List, Deque, Cloneable, Serializable
特点：
- 可存储任何类型数据（包括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;
    }
}

// 链表长度/元素数量
transient int size = 0;

// 头节点
transient Node<E> first;

// 尾节点
transient Node<E> last;

// 继承自AbstractList，记录结构变化次数
protected transient int modCount = 0;

构造方法

// 空参构造
public LinkedList() {
}

// 集合构造
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

add方法

获取指定下标的元素。

public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在链表尾部插入元素
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;
    // 链表长度+1
    size++;
    // 改变次数+1
    modCount++;
}

先获取尾节点（用于判断链表是否为空），创建新节点存放当前元素，并将新节点设置为新的尾节点。

若链表为空，则将新节点设置为新的头节点，否则将新节点连接到尾节点的后面，然后将链表长度和改变次数+1。

get方法

获取指定下标的元素。

public E get(int index) {
    // 越界检查
    checkElementIndex(index);
    return node(index).item;
}

// 越界则抛出异常
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 检查是否越界
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

// 获取指定索引的元素
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 使用二分法，比较index与size/2
    // 若 index < size / 2，说明index靠近头节点，从头向后遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } 
    // 若 index >= size / 2，说明index靠近尾节点，从尾向前遍历
    else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

先进行越界检查，然后根据索引与链表长度关系决定是从头开始遍历还是从尾开始遍历。

remove方法

移除指定下标的元素。

public E remove(int index) {
    // 越界检查
    checkElementIndex(index);
    return unlink(node(index));
}

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与前点断开连接
        x.prev = null;
    }
	
    // 后点为空，直接将尾节点设置为前点
    if (next == null) {
        last = prev;
    } 
    // 后点非空，将后继的前驱节点设置为前点
    else {
        next.prev = prev;
        // 将x与后点断开连接
        x.next = null;
    }

    // 将删除节点置为null，help GC
    x.item = null;
    // 链表长度-1
    size--;
    // 操作次数+1
    modCount++;
    // 返回被删除结点的值
    return element;
}