在 Java 的 Collection 集合中,实现 List 接口的集合的一大特性是元素有序且可以重复,最常见的就是 ArrayList 和 LinkedList 了,那么这两者又有什么相同或不同之处呢?

对比

ArrayList 底层的数据结构是 Object 数组,所以插入和删除元素的时间复杂度受元素位置的影响,一般为 O(n)。比如执行 add(E e) 方法添加元素的时候,ArrayList 默认会将指定的元素追加到列表的末尾,这种情况的时间复杂度就是 O(1)。但是如果要在指定位置 i 插入元素的话(add(int index, E element)),时间复杂度就为 O(n),因为要将第 i 和第 i 个位置之后的元素都向后移动一位,以保证数组内存空间的连续性。也正因为数组内存空间的连续性,以及数组中存储的数据类型都相同,使得 ArrayList 支持快速随机访问,即根据元素的索引,通过寻址公式,快速地获取元素对象。

LinkedList 底层的数据结构是双链表插入和删除元素的时间复杂度均为 O(1),不受元素位置的影响,因为只需要处理好与插入或删除元素相邻的结点指针的指向关系即可,不需要移动一系列元素。但是基于双链表的 LinkedList 是不支持快速随机访问的,需要从双链表的一端开始逐个遍历,直到找到对应索引位置的元素。

对于内存空间的占用,ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间浪费则体现在它的每一个元素都需要消耗比在 ArrayList 中更多的空间,因为除了数据外还需要存储前驱指针和后继指针。

ArrayList 的扩容机制

首先,在构造 ArrayList 时,有三种方式来进行初始化

  1. 使用默认构造函数,初始化为一个空的 Object 数组。当真正向 ArrayList 中添加第一个元素,执行 add() 操作时,才将容量扩充为默认容量 10 。
  2. 使用带初始容量参数 (≧0) 的构造函数,初始化为一个指定容量的 Object 数组。
  3. 构造包含指定 Collection 元素的列表,这些元素利用该集合的迭代器按顺序返回。

关于 ArrayList 的扩容机制,大致有以下三个步骤:

1.确定最小需求容量

在向 ArrayList 中添加元素 (add) 的时候,可能会触发扩容机制。在进行 add 操作的时候,会将当前 ArrayList 的 size 加 1,与默认容量 10 进行比较, 取较大的值作为所需要的最小需求容量(minCapacity)

还可以由用户调用 ensureCapacity(int minCapacity) 方法来手动指定最小需求容量进行检查,此时也可能会触发扩容机制。建议在 add 大量元素之前调用 ensureCapacity() 方法,以减少增量重新分配的次数。

关于 size 和 length: ArrayList 的底层数据结构是一个 Object 数组 elementData,size 是 ArrayList 类的一个成员变量,表示 elementData 这个数组中当前有多少个元素,即当前 ArrayList 集合的实际大小;而 length 表示这个数组的长度,即 elementData.length ,也就是当前 ArrayList 集合的容量。

2.计算新容量

确定最小需求容量后,进行检验判断,如果这个最小需求容量大于当前 ArrayList 底层数组的 length(也就是大于旧容量),就调用 grow() 方法进行扩容操作。

在 grow() 方法中,通过代码:

1
2
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

来计算新容量,这里通过移位运算符 >> 将旧容量 oldCapacity 右移一位,其效果相当于将 oldCapacity 除以 2,然后向下取整。所以一般情况下 ArrayList 扩容之后容量会变为原来的 1.5 倍左右。

当旧容量太大时,进行加法运算可能会出现整数溢出,导致计算得到的新容量小于最小需求容量(minCapacity),此时会在最小需求容量和 ArrayList 允许的最大数组容量(MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8)中取较大值作为新容量(参见 hugeCapacity() 方法)。

3.数组拷贝进行扩容

关于 Arrays.copyOf() 和 System.arraycopy() 方法: 在 ArrayList 以及 JDK 的源码中,很多地方都调用了这两个方法,比如 add(int index, E element)toArray() 等方法以及这里 grow() 方法中的扩容操作。这两个方法都用于数组的复制操作,Arrays.copyOf() 方法本质上也是调用的 System.arraycopy() 方法,只是做了一些封装和简化。

方法 System.arraycopy() 用于从指定源数组中进行拷贝操作,指定开始位置,拷贝指定长度的元素到指定目标数组中。其声明如下:

1
2
// java.lang.System 类:
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

System.arraycopy() 方法使用 native 关键字修饰,是一个 JVM 本地方法,它通过一些底层手段优化了 Java 中数组的拷贝操作,这种方式比起直接进行 for 循环或 clone 是更加高效的,数组越大体现地越明显。