List接口——ArrayList学习笔记
ArrayList底层采用的是一个可以动态再分配的对象数组。
对ArrayList
学习的最好方法就是学习ArrayList
的源码,通过学习源码,就可以知道它是怎么对数据进行增、删、改、查操作的。
(一)底层实现原理
如果想要探究ArrayList
底层实现原理的话,那么,我们就需要通过解读源码来一探究竟。而解读源码的入口,就是构造器。
1. 从构造器入手
进入ArrayList
类,找到默认构造器,我们发现默认构造器的代码是这样写的:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
……
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
private static final int DEFAULT_CAPACITY = 10;
通过代码可以看到,当通过默认构造器实例化一个ArrayList
对象时,一个空的对象数组(DEFAULTCAPACITY_EMPTY_ELEMENTDATA
)被赋值给元素集合(elementData
)了。此时,一个空的ArrayList
对象就被创造出来了,这个对象的值为null
,长度是0
,此时还不能往对象中添加任何元素。
2. 添加元素
当向集合中添加元素时,分为两种情况:一种是直接在集合已有元素后新增元素;另一种是在已有元素的情况下,根据索引值插入新元素。这两种新增元素的实现逻辑不同,因此需要分开学习。
2.1 新增元素
当给新创建的ArrayList
对象添加元素时,一般是通过add()
方法。那么add()
方法的代码是怎么写的呢?
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
从最后一行代码可以看到,经过一番逻辑处理后,最后的返回值是true
,代表着新元素被添加进元素集合了。那么,在返回true
之前,元素集合内发生了什么呢?
我们从下往上看代码,看方法体的第二行elementData[size++] = e;
,这行代码是向元素集合中,索引下标为size++
的位置添加新元素e
。如果此时是在ArrayList
对象刚被创建出来后,第一次添加新元素,那么此时size++
的值为0
。
需要注意的是,在创建ArrayList
对象时,构造器只是将一个空数组对象给了元素集合,此时的元素集合为null
,是无法向其中添加新元素的。那么Java
又是怎么向空的元素集合中添加新元素的呢?原因就在第一行代码ensureCapacityInternal(size + 1);
中。
(1)计算容纳量
当第一次向集合中添加元素时,需要对原本为空的集合对象进行扩容,而扩容的前置条件就是要先计算出集合需要多大的容量才合适。
此时的集合就像是一个还没开工建设的蓄水池,建设蓄水池的土地已经规划好,现在就差设计蓄水池的尺寸了,而集合的容量就是蓄水池的尺寸。
那么我们接下来看看Java
是怎么计算集合容量的。
还是接着看代码,进入到ensureCapacityInternal()
方法内,可以看到以下代码:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
我们先从入参minCapacity
看起,入参minCapacity
的值为size + 1
,此时size
的值为0
。因此,入参minCapacity
的值为0 + 1 = 1
。
接着,我们进入到方法体中,第一行代码是个判断if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
,先判断元素集合elementData
是否是空对象(DEFAULTCAPACITY_EMPTY_ELEMENTDATA
的值为{}
,空对象),如果为空的话,说明是第一次添加元素,需要先确定最小容纳量(minCapacity
);如果不为空的话,直接使用入参的最小容纳量minCapacity
。最小容纳量是取DEFAULT_CAPACITY
和minCapacity
两值中的最大值,其中,minCapacity
的值为1
,DEFAULT_CAPACITY
的值为一个常量,从代码中可以看到其值为:
private static final int DEFAULT_CAPACITY = 10;
从这里就可以看出,ArrayList
集合的初始的长度是10
。
现在元素集合的最小容纳量minCapacity
的值已经知道了,那就是10
。接下来就要确认这个最小容纳量minCapacity
是否适合给集合使用。
(2)确认最小容纳量
最小容纳量已经确定值为10
了,那么接下来就需要确认这个值是否真正适合集合使用。
接着看代码,进入ensureExplicitCapacity()
方法中:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
第一行代码是记录集合进行变长操作的次数,可以先不管它。
主要是看下面几行的代码,先判断给的最小容纳量minCapacity
是否能包住集合内现有元素的个数,如果最小容纳量minCapacity
大于此时集合内元素个数的话,那么就执行grow()
方法,否则就不对集合进行操作。
确定计算出的最小容纳量minCapacity
是适合集合的,那么就要对集合进行扩容了(此时的集合还为空)。
(3)扩容集合
进入grow()
方法内,最小容纳量minCapacity
为入参。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
从grow()
方法的处理逻辑可以总结成以下几步:
- 获取元素集合现在的长度,并把值赋给
oldCapacity
,int oldCapacity = elementData.length;
- 在原有长度的基础上,扩大约1.5倍(
oldCapacity >> 1
是位运算,等同于除以2
),并赋值给newCapacity
,int newCapacity = oldCapacity + (oldCapacity >> 1);
- 判断新算出来的集合长度是否小于传入的最小容纳量
minCapacity
,若是,则集合的新长度为最小容纳量;否则,使用新算出来的数值当作集合新的长度if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
- 集合新长度与数组允许的最大长度(
MAX_ARRAY_SIZE
的值为Integer.MAX_VALUE - 8
,即0x7fffffff - 8 = 2147483647 - 8 = 2147483639
)进行比较,若计算出的集合长度大于数组允许的最大长度,则调用hugeCapacity()
方法(return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
);否则,集合的长度就使用计算出的值if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
- 对数组进行拷贝(长度使用计算出的新集合长度),此时,数组会被
new
出来,集合中若有数据到话也会被复制到被实例化的数组中elementData = Arrays.copyOf(elementData, newCapacity);
自此,向集合中添加新元素的操作完成。
2.2 插入元素
插入新元素的话,需要使用add(index, element)
方法。这个方法不仅仅需要传入新元素的值element
,同时也要传入要插入的索引值index
。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
- 检查传入的索引值是否已经超过集合的长度或索引值为负数
rangeCheckForAdd(index);
- 计算容纳量(同2.1新增元素中的(1)计算容纳量)
ensureCapacityInternal(size + 1);
- 对数组进行重新拷贝
System.arraycopy(elementData, index, elementData, index+1, size - index);
(System.arraycopy(初始数组, 初始数组中需要移动元素的开始索引值, 目标数组, 目标数组中需要移动元素的开始索引值, 需要移动元素的个数);
) - 将新元素的值赋值给集合中对应索引位置
elementData[index] = element;
- 集合的长度加一
size++;
tips:
需要额外解释的是第三、四、五步的逻辑:对数组进行重新拷贝System.arraycopy(elementData, index, elementData, index+1, size - index);
(System.arraycopy(初始数组, 初始数组中需要移动元素的开始索引值, 目标数组, 目标数组中需要移动元素的开始索引值, 需要移动元素的个数);
);将新元素的值赋值给集合中对应索引位置elementData[index] = element;
;集合的长度加一size++;
。
- 假设有一个长度为
5
的对象数组elementData
,其元素分布为:
0 : [test1]
1 : [test2]
2 : [test3]
3 : [test4]
4 : [test5]
- 现在,我希望在索引值为
1
的元素位置上插入一个新的元素test100
。 - 那么我可以对原始数组
elementData
进行复制,这个新的数组我还是称它为elementData
,其长度也为5
,第一个元素的值同样是test1
。 - 不同的是,从第二个元素开始,此后的所有元素将要被往后移动一个索引值。也就是说,在原始数组中索引值是
index
的元素,在新数组中的索引值要变成index+1
,总共要操作4
(size - index
)个元素。
0 : [test1]
→ [test100]
1 : [test2] ↓
2 : [test3] ↓
3 : [test4] ↓
4 : [test5] ↓
- 由于插入了新的元素,因此,集合的长度要加一,由原来的
5
变成了6
。那么,经过这一番操作后,新数组的元素分布为:
0 : [test1]
1 : [test100]
2 : [test2]
3 : [test3]
4 : [test4]
5 : [test5]
3. 修改元素
修改集合中的元素,可以通过ArrayList
类本身的set()
方法,也可以通过迭代器(ListItr
)的set()
方法修改。需要注意的是,通过迭代器修改元素的话,需要先遍历集合,而且只能修改被遍历过的最后一个元素,而且其底层的实现也是调用ArrayList
类本身的set()
方法,因此,这里只对ArrayList
类本身的set()
方法进行源码解读。
废话少说,上set()
方法的代码。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
可以看到方法的入参有两个,分别是要修改元素的索引index
、被修改的元素element
。
方法体中第一行代码rangeCheck(index);
是对索引进行检查,看看是否超过集合长度,如果超过了集合的长度就抛出IndexOutOfBoundsException
的异常。
接下来是保存将要被修改元素的原始值,赋值给oldValue
(最后将会被返回)。
最后是通过索引,将新元素赋值给索引对应的集合位置,完成元素的替换。
4. 查看元素
查看元素的值非常简单,同修改元素类似,也有两种查看方式。一种是通过ArrayList
类自带的get()
方法查看;另一种方法是通过迭代器的方式遍历查看。两种方法的处理逻辑类似,都是通过索引的方式获取元素并返回。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
查看元素的逻辑非常简单,第一步还是先检查入参的索引`index是否超过了集合的长度;第二步是返回集合对应索引位置的元素。
5. 删除元素
当我们希望删除一个元素时,需要知道被删除的元素的索引或元素本身的值。通过使用remove()
方法,入参可以是索引值,也可以是元素本身的值。
5.1 通过索引值删除元素
首先先解读通过索引值删除元素的代码。
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;
return oldValue;
}
- 检查给定的索引值是否超过了集合的长度
rangeCheck(index);
- 记录集合被操作的次数
modCount++;
- 保存将要被删除元素的值
E oldValue = elementData(index);
,最后将要返回该值 - 获取需要被移动元素的个数
int numMoved = size - index - 1;
- 对数组进行重新拷贝
System.arraycopy(elementData, index+1, elementData, index, numMoved);
(System.arraycopy(初始数组, 初始数组中需要移动元素的开始索引值, 目标数组, 目标数组中需要移动元素的开始索引值, 需要移动元素的个数);
) - 对集合的最后一个元素进行置空操作
elementData[--size] = null;
tips:
需要额外解释的是第四步和第五步的逻辑:获取需要被移动元素的个数int numMoved = size - index - 1;
;对数组进行重新拷贝System.arraycopy(elementData, index+1, elementData, index, numMoved);
。
- 假设有一个长度为
5
的对象数组elementData
,其元素分布为:
0 : [test1]
1 : [test2]
2 : [test3]
3 : [test4]
4 : [test5]
- 现在,我希望移除索引值为
1
的元素,即第二个元素[test2]
。那么我可以对原始数组elementData
进行复制,这个新的数组我还是称它为elementData
,其长度也为5
,第一个元素的值同样是test1
。 - 不同的是,第二个元素将要被移除,从第三个元素(
index+1
)开始,往后的每个元素都要被往前挪一个位置。也就是说,在原始数组中索引值是index+1
的元素,在新数组中的索引值要变成index
,总共要操作3
(numMoved
)个元素。
0 : [test1]
1 : [test2] ×
2 : [test3] ↑
3 : [test4] ↑
4 : [test5] ↑
- 最后一个元素直接置为空。那么,经过这一番操作后,新数组的元素分布为:
0 : [test1]
1 : [test3]
2 : [test4]
3 : [test5]
4 : []
5.2 通过元素值删除元素
也可以通过元素值来删除元素。
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;
}
通过元素值删除元素的逻辑是通过遍历的方式,找到元素值符合的元素,通过调用fastRemove()
方法进行删除,如果方法不报错,则返回true
,否则,返回false
。
fastRemove()
方法的代码与通过索引值删除元素的逻辑差不多,具体代码如下:
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;
}
可以看到,这段代码的逻辑与通过索引值删除元素的逻辑差不多,较大的差别是,通过索引值删除元素的返回值是被删除的元素,而这段代码没有返回值。
(二)总结
通过从默认构造器入手,到添加元素、修改元素、查看元素、删除元素这四中操作,可以说对ArrayList
的实现原理有了基本的了解。
ArrayList
就是通过操作可变数组来实现对数据的增、删、改、查操作。采用可变数组的方式擅长随机访问元素,但是在数组的中间插入和移除元素时较慢。所以,当我们在使用List
时,需要根据实际情况,考虑是否选择ArrayList
。