ArrayList简介
ArrayList 是 Java 集合框架中比较常用的数据结构了。ArrayList是可以动态增长和缩减的索引序列&＃xff0c;内部封装了一个动态再分配的Object[]数组
这里我们可以看到ArrayList继承抽象类AbstractList&＃xff0c;实现了 List 接口&＃xff0c;同时还实现了 RandomAccess、Cloneable、Serializable 接口&＃xff0c;所以ArrayList 是支持快速访问、复制、序列化的。
主要成员变量
// 底层存储元素的数组transient Object[] elementData; // ArrayList的实际大小private int size;
注意&＃xff1a;size 才是 elementData数组中实际的元素个数&＃xff0c;而 elementData.length 为数组的容量&＃xff0c;表示最多可以容纳多少个元素。
// ArrayList的默认初始化容量private static final int DEFAULT_CAPACITY &＃61; 10;
ArrayList的默认初始容量大小为 10。
// 记录对List操作的次数protected transient int modCount &＃61; 0;
这个变量是定义在 AbstractList 中的&＃xff0c;主要使用是在 Iterator&＃xff0c;目的是防止在List在迭代的过程中被修改。
// 空的Object类型数组private static final Object[] EMPTY_ELEMENTDATA &＃61; {};// 空的Object类型数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA &＃61; {};
两个空的数组有什么区别呢&＃xff1f;简单来讲就是第一次添加元素&＃xff08;使用add方法&＃xff09;时知道elementData是从空的构造函数还是有参构造函数被初始化的。以便确认下一步的扩容机制。
构造函数
ArrayList类共有三种构造函数&＃xff1a;
- 无参构造函数
- 带有参数为初始容量initialCapacity的构造函数
- 带有参数为Collection集合的构造函数
1、无参构造函数
public ArrayList() {this.elementData &＃61; DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
注意&＃xff1a;虽然在源码的注释中说该构造函数构造一个容量大小为 10 的空的ArrayList&＃xff0c;但实际上构造函数只是给 elementData 赋值了一个空的数组&＃xff08;DEFAULTCAPACITY_EMPTY_ELEMENTDATA&＃xff09;&＃xff0c;在第一次向ArrayList添加元素时容量才扩大至10的。
2、带有参数为初始容量initialCapacity的构造函数
public ArrayList(int initialCapacity) {// 如果initalCapacity大于0&＃xff0c;直接创建一个长度Object数组赋值为elementData&＃xff1b;if (initialCapacity > 0) {this.elementData &＃61; new Object[initialCapacity];}// 如果initalCapcity等于0&＃xff0c;直接将空数组EMPETY_ELEMENTDATA复制给elementDataelse if (initialCapacity &＃61;&＃61; 0) {this.elementData &＃61; EMPTY_ELEMENTDATA;}// 如果initalCapcity小于于0&＃xff0c;则抛出异常IllegalArgumentExceptionelse {throw new IllegalArgumentException("Illegal Capacity: "&＃43;initialCapacity);}}
当 initialCapacity 为0时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。 当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object 数组并赋值给 elementData。
3、带有参数为Collection集合的构造函数
public ArrayList(Collection c) {// 将 Collection 转化为数组并赋值给elementDataelementData &＃61; c.toArray();// 把elementData中元素的个数赋值给size并判断其是否为0if ((size &＃61; elementData.length) !&＃61; 0) {// 如果 size 不为零&＃xff0c;则判断 elementData 的 class 类型是否为 Object[]&＃xff0c;不是的话则做一次转换。if (elementData.getClass() !&＃61; Object[].class)elementData &＃61; Arrays.copyOf(elementData, size, Object[].class);} // 如果 size 为零&＃xff0c;则把 EMPTY_ELEMENTDATA 赋值给 elementData&＃xff0c;相当于new ArrayList(0)。else {this.elementData &＃61; EMPTY_ELEMENTDATA;}}
该构造方法主要就是将Collection集合的实现类转换为ArrayList。
主要操作方法
add方法&＃xff08;添加单个元素&＃xff09;
public boolean add(E e) {// 先确认ArrayList集合容量大小ensureCapacityInternal(size &＃43; 1);// 先给elementData中size位置赋值为e&＃xff0c;然后size自增 elementData[size&＃43;&＃43;] &＃61; e;return true;}
private void ensureCapacityInternal(int minCapacity) {// 如果elementData为默认的空数组&＃xff0c;则给minCapacity赋值为初始的默认容量if (elementData &＃61;&＃61; DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity &＃61; Math.max(DEFAULT_CAPACITY, minCapacity);}// modCount自增&＃xff0c;并确定容量大于数组的长度ensureExplicitCapacity(minCapacity);}
private void ensureExplicitCapacity(int minCapacity) {// modCount自增&＃xff0c;修改次数加1modCount&＃43;&＃43;;// 如果minCapacity超过了数组长度&＃xff0c;则进行扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}
上述三个函数的调用关系很简单&＃xff0c;也很清楚。
- 在add方法中&＃xff0c;每次添加元素到ArrayList中时都会先确认下集合容量大小&＃xff0c;然后将size位置的元素赋值为e&＃xff0c;size再进行自增。
- 在ensureCapacityInternal方法中先对elementData进行判断 &＃xff0c;如果elementData为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是10。这就是 EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别所在。同时也验证了上面的说法&＃xff1a;使用无参构造函数时是在第一次添加元素时初始化容量为10 。
- ensureExplicitCapacity 方法中首先对modCount 自增1&＃xff0c;记录操作次数&＃xff0c;然后如果 minCapacity 大于 elementData 的长度&＃xff0c;则对集合进行扩容。显然当第一次添加元素时 elementData 的长度为零。那我们来看看 grow 函数。
private void grow(int minCapacity) {// ArrayList的旧容量为数组长度int oldCapacity &＃61; elementData.length;// 将新容量赋值为原容量的1.5倍&＃xff08;左移一位相当于除以二&＃xff09;int newCapacity &＃61; oldCapacity &＃43; (oldCapacity >> 1);// 如果此时新容量还是小于添加元素后的容量&＃xff0c;则将新容量直接赋值为添加元素后的容量if (newCapacity - minCapacity <0)newCapacity &＃61; minCapacity;// 如果此时新容量大于数组的最大大小&＃xff0c;则返回上限最大的容量if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity &＃61; hugeCapacity(minCapacity);// 把旧的数组elementData拷贝到新的elementData&＃xff0c;并将容量设置为newCapacityelementData &＃61; Arrays.copyOf(elementData, newCapacity);
}
默认将list的容量扩容至原来容量的 1.5 倍。但是扩容之后也不一定适用&＃xff0c;有可能太小&＃xff0c;有可能太大。所以才会有下面两个 if 判断。如果1.5倍太小的话&＃xff0c;则将增加元素的容量大小赋值给newCapacity&＃xff0c;如果1.5倍太大或者我们需要的容量太大&＃xff0c;则调用hugeCapacity函数&＃xff0c;给newCapacity赋一个合适的值。最后将原数组中的数据复制到大小为 newCapacity 的新数组中&＃xff0c;并将新数组赋值给 elementData。
private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0&＃xff0c;就抛出异常if (minCapacity <0) // overflowthrow new OutOfMemoryError();// 如果此时增加元素后得minCapacity大于数组的最大长度就返回整数最大值&＃xff0c;否则返回数组最大值return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
add方法&＃xff08;批量添加&＃xff0c;在指定位置添加&＃xff09;
public void add(int index, E element) {// 检查index是否越界rangeCheckForAdd(index);ensureCapacityInternal(size &＃43; 1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index &＃43; 1, size - index);elementData[index] &＃61; element;size&＃43;&＃43;;
}public boolean addAll(Collection c) {Object[] a &＃61; c.toArray();int numNew &＃61; a.length;ensureCapacityInternal(size &＃43; numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size &＃43;&＃61; numNew;return numNew !&＃61; 0;
}public boolean addAll(int index, Collection c) {rangeCheckForAdd(index);Object[] a &＃61; c.toArray();int numNew &＃61; a.length;ensureCapacityInternal(size &＃43; numNew); // Increments modCountint numMoved &＃61; size - index;if (numMoved > 0)System.arraycopy(elementData, index, elementData, index &＃43; numNew, numMoved);System.arraycopy(a, 0, elementData, index, numNew);size &＃43;&＃61; numNew;return numNew !&＃61; 0;
}
这三个方法基本思路与上述add方法基本思路是一致&＃xff0c;博主这里就不再赘述了。
remove方法
public E remove(int index) {// 检查index是否越界&＃xff0c;如果越界则抛出异常rangeCheck(index);// modCount自增&＃xff0c;修改次数加一modCount&＃43;&＃43;;// 获取elementData在index位置的值E oldValue &＃61; elementData(index);// 获取后移的位置长度int numMoved &＃61; size - index - 1;// 如果大于零&＃xff0c;则调用System.arraycopy方法完成数组移动if (numMoved > 0)System.arraycopy(elementData, index&＃43;1, elementData, index, numMoved);// size自减&＃xff0c;并将elementData索引值为size的元素引用赋值为空&＃xff0c;让GC对他进行回收elementData[--size] &＃61; null; // 返回index位置的值return oldValue;
}
当我们调用 remove(int index) 时&＃xff0c;首先会检查 index 是否合法&＃xff0c;然后再判断要删除的元素是否位于数组的最后一个位置。如果 index 不是最后一个&＃xff0c;就再次调用 System.arraycopy() 方法拷贝数组。说白了就是将从 index &＃43; 1 开始向后所有的元素都向前挪一个位置。然后将数组的最后一个位置空&＃xff0c;size - 1。如果 index 是最后一个元素那么就直接将数组的最后一个位置空&＃xff0c;size - 1即可。
public boolean remove(Object o) {// 如果o为空&＃xff0c;则查找数组中为空的索引&＃xff0c;并调用fastRemove方法进行删除&＃xff0c;并返回trueif (o &＃61;&＃61; null) {for (int index &＃61; 0; index }
下面我们在看fastRemove方法&＃xff0c;fastRemove方法相较于remove&＃xff08;int index&＃xff09;方法少了一步对index的判断&＃xff0c;因为remove&＃xff08;Object o&＃xff09;就是在数组中进行查询一定是合法的&＃xff0c;所以在fastRemove中没必要对index进行判断。
private void fastRemove(int index) {modCount&＃43;&＃43;;int numMoved &＃61; size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index&＃43;1, elementData, index,numMoved);elementData[--size] &＃61; null; // clear to let GC do its work
}
get方法
public E get(int index) {// 检查index是否合法&＃xff0c;是否越界rangeCheck(index);// 利用数组的特点&＃xff0c;直接访问数组中该索引位置上的元素return elementData(index);
}
总结
- ArrayList可以存放null。
- ArrayList本质上就是一个elementData数组。
- ArrayList区别于数组的地方在于能够自动扩展大小&＃xff0c;其中关键的方法就是gorw()方法。
- ArrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素&＃xff0c;而clear是全是删除集合中的元素。
- ArrayList由于本质是数组&＃xff0c;所以它在数据的查询方面会很快&＃xff0c;而在插入删除这些方面&＃xff0c;性能下降很多&＃xff0c;有移动很多数据才能达到应有的效果
- ArrayList实现了RandomAccess&＃xff0c;所以在遍历它的时候推荐使用for循环。
原文作者&＃xff1a;前程有光
原文链接&＃xff1a;https://juejin.cn/post/6911944296451506190
文章来源&＃xff1a;掘金
侵权请联系删除
京公网安备 11010802041100号