ArrayList：可变长数组
ArrayList的定义
1 | public class ArrayList<E> extends AbstractList<E> |
- 支持泛型
- 继承AbstractList
- 实现了List，实现了所有可选列表操作
- 实现了RandomAccess，支持随机访问
- 实现了Cloneable，支持clone()
- 实现了java.io.Serializable，支持序列化操作
ArrayList的构造函数
1 | /** |
以无参构造方法创建ArrayList时，实际上是创建了一个空数组。当真正对数组进行添加元素时，才真正分配容量，即向数组添加第一个元素时，数组容量扩为10。
一步一步分析ArrayList的扩容机制
- ArrayList的add()方法
1
2
3
4
5
6
7
8
9
10/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
//先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//为数组最后一位赋值
elementData[size++] = e;
return true;
} - ArrayList的ensureCapacityInternal()方法
1
2
3
4
5//传入最小容量，判断扩容
private void ensureCapacityInternal(int minCapacity) {
//根据calculateCapacity方法得到最小容量并传入ensureExplicitCapacity中
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
} - ArrayList的calculateCapacity()方法
1
2
3
4
5
6
7
8
9//通过数组长度和最小容量得出新的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果数组为空，则比较默认初始容量大小（10）和最小容量，返回其中的较大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//数组不为空，则直接返回原最小容量
return minCapacity;
} - ArrayList的ensureExplicitCapacity()方法
1
2
3
4
5
6
7
8
9
10//根据最小容量判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
//结构性修改次数+1
modCount++;
//如果最小容量>数组长度，则需要进行扩容
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}- 分析
- 当我们要add进第1个元素到ArrayList时，
elementData.length为0（因为还是一个空的list），因为执行了ensureCapacityInternal()方法，所以minCapacity此时为10。此时，minCapacity-elementData.length>0成立，所以会进入grow(minCapacity)方法。 - 当add第2个元素时，
minCapacity为2，此时elementData.length(容量)在添加第一个元素后扩容成10了。此时，minCapacity-elementData.length>0不成立，所以不会进入（执行）grow(minCapacity)方法。 - 添加第3、4···到第10个元素时，依然不会执行
grow方法，数组容量都为10。 - 直到添加第11个元素，
minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。
- 当我们要add进第1个元素到ArrayList时，
- 分析
- ArrayList的grow()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
* 要分配的最大数组大小。某些VM在数组中保留一些标头字。尝试分配更大的阵列可能会导致OutOfMemoryError：请求的阵列大小超出VM限制。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
* @param minCapacity 所需的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
//旧容量是数组长度
int oldCapacity = elementData.length;
//新容量是旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//判断新容量是否<最小容量，若是，则新容量变成最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断新容量是否>最大容量，若是，则调用hugeCapacity传进最小容量来获取新容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//根据原数组和新容量来调用copyOf方法来创建新的数组
// minCapacity通常与size的大小相似，因此这是一个胜利
elementData = Arrays.copyOf(elementData, newCapacity);
} - ArrayList的hugeCapacity()方法
1
2
3
4
5
6
7
8
9
10//根据最小容量获得新容量
private static int hugeCapacity(int minCapacity) {
//若最小容量<0，则溢出，抛OMM
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//判断最小容量是否>最大容量，若是，则返回Integer最大值，否则返回最大容量
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
ArrayList的核心方法
| 方法名 | 时间复杂度 |
|---|---|
| get(int index) | O(1) |
| add(E e) | O(1) |
| add(int index, E element) | O(n) |
| remove(int index) | O(n) |
| set(int index,E element) | O(1) |
- ArrayList的get()方法
1
2
3
4
5
6
7
8
9
10
11
12
13/**
* 返回此列表中指定位置的元素。
*
* @param index 要返回的元素的索引
* @return 此列表中指定位置的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//检查索引是否越界
rangeCheck(index);
return elementData(index);
} - ArrayList的rangeCheck()方法
1
2
3
4
5
6
7/**
* 检查给定的索引是否在范围内。如果不是，则抛出适当的运行时异常。该方法不检查索引是否为负：始终在数组访问之前立即使用，如果索引为负，则抛出ArrayIndexOutOfBoundsException。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} - ArrayList的add()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/**
* 将指定的元素插入此列表中的指定位置。将当前在该位置的元素（如果有）和任何后续元素右移（将其索引加一）。
*
* @param index 指定元素要插入的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//检查越界
rangeCheckForAdd(index);
//扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//对数组进行复制处理，目的是空出index的位置，并将index后的元素右移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
//size+1
size++;
}
/**
* 检查越界
* add和addAll使用的rangeCheck版本。
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} - ArrayList的remove()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* 删除此列表中指定位置的元素。将所有后续元素向左移动（从其索引中减去一个）。
* @param index 要删除的元素的索引
* @return 从列表中删除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//检查索引是否越界
rangeCheck(index);
//结构性修改次数+1
modCount++;
//记录要删除的元素
E oldValue = elementData(index);
//需要左移的元素个数
int numMoved = size - index - 1;
//左移
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//size-1，将索引为size-1处的元素置null，让GC起作用
elementData[--size] = null; // clear to let GC do its work
return oldValue;
} - ArrayList的set()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/**
* 用指定的元素替换此列表中指定位置的元素。
* @param index 替换元素的索引
* @param element 要存储在指定位置的元素
* @return 先前位于指定位置的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//检查索引是否越界
rangeCheck(index);
//替换
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
ArrayList使用到了迭代器模式