深入ArrayList源码分析（JDK1.8）
深入ArrayList源码分析（JDK1.8）
Java 集合系列源码分析文章：
ArrayList源码分析（JDK1.8）
数据结构中有两种存储结构，分别是：顺序存储结构、链式存储结构。在 Java 中，对于这四种结构分别进行实现的类有：
-
顺序存储结构：ArrayList、Stack -
链式存储结构：LinkedList、Queue
这里只对 ArrayList 的源码进行分析，ArrayList 是一个数组队列，相当于 动态数组 。与Java 中的数组相比，它的容量能动态增长。
特点
-
基本的 ArrayList常用于随机访问元素，但是在 List 中间插入和移除元素较慢； -
ArrayList中的操作不是线程安全的。所以建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList，建议使用CopyOnWriteArrayList。
继承关系
上面可以看到，ArrayList 实现来四个接口一个抽象类。它继承类 AbstracList 抽象类，实现了 List 、 RandomAccess （随机访问）、 Cloneable （可克隆）、 Serializable （序列化）四个接口
-
ArrayList继承于AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能； -
ArrayList实现了RandmoAccess接口，即提供了随机访问功能； -
ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆； -
ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
成员变量
在 ArrayList 的源码中，主要成员变量如下：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
...
// 默认数组的长度
private static final int DEFAULT_CAPACITY = 10;
// 默认的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认的空数组，与上面的区别，在不同的构造函数中用到
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正用于存放数据的数组
transient Object[] elementData;
// 数组元素个数
private int size;
// 要分配的数组的最大大小，尝试分配更大的阵列可能会导致 OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
}
ArrayList 的底层实现是数组，默认的数组大小是 10。
构造函数
-
ArrayList()：构造一个初始容量为10的空列表 -
ArrayList(Collection<?extend E> c)：构造一个包含指定元素的列表 -
ArrayList( int initialCapcity )：构造一个具有初始容量值得空列表
// 第一种，调用ArrayList(10) 默认初始化一个大小为10的Object数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 第二种
public ArrayList(int initialCapacity) {
// 如果用户初始化大小大于0，则新建一个用户初始化值大小的Objec数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 等于0，则赋值为变量EMPTY_ELEMENTDATA，默认的空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 小于0，则抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 第三种：将容器数组化处理并将这个数组值赋给Object数组
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 当c.toArray 返回的不是 Object 类型的数组时，进行下面的转化
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
增删改查操作
对于增删改查的基本操作，在这里只给出一些比较重要的源代码进行解析。
增加操作
-
add(E e)：添加一个元素到列表的末尾。 -
add( int index, E element ) :在指定的位置添加元素 -
addAll( Collection<? extends E> c )：添加一个集合到元素的末尾.以上返回类型是boolean -
ensureCapcity（int minCapcity）：确保列表中含有minCapcity的最小容量
ArrayList默认的插入是插在数组的末尾，在不需要扩容时是一个时间复杂度O(1)的操作，需要扩容时复杂度为O(n)，所以如果预先能判断数据量的大小，可以指定初始化数组的大小，避免过多的扩容操作。下面代码看一些第一个增加元素的方法实现：
// 第一步：
public boolean add(E e) {
// 加入元素前检查数组的容量是否足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 第二步：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 如果添加元素后大于当前数组的长度，则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 第三步：扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 将数组的长度增加原来数组的一半，也就是1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩充一半后仍然不够，则 newCapacity = minCapacity；minCapacity实际元素的个数
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果扩充后的容量超过最大值变量MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 将elementData持有的元素复制到新的数组对象，最后将elementData的引用指向新的数组对象
// 原有的数组对象因为没有了引用，一段时间后将被回收。
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
ArrayList还支持在指定索引处插入。在指定索引处插入时，需要将指定索引及其之后的元素向后推一个位置，所以是一个复杂度O(n)的操作。源码如下：
// 第一步：
public void add(int index, E element) {
// 检查index的值是否在0到size之间，可以为size.
rangeCheckForAdd(index);
// 看 elementData 的长度是否足够，不够扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将 elementData 从 index 开始后面的元素往后移一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 第二步：
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 第三步：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
删除操作
-
remove(Object o)：删除列表中第一个出现O的元素 -
remove( int index)：删除列表中指定位置的元素 -
removeAll（Collection<?> c）：删除列表中包含C的所有元素 -
removeIf（Predictcate<? super E> filter）：删除列表中给定谓词的所有元素 -
removeRange( int from,int to )：删除从from到to的所有元素 -
clear（）：清除所有的元素。返回类型为void
ArrayList 删除元素时，需要将所删元素之后位置的元素都向前推一个位置，复杂度也是O(n)。所以ArrayList不适合需要频繁在指定位置插入元素及删除的应用场景，看代码实现：
public E remove(int index) {
// 第一步：如果index >= size，则抛出异常
rangeCheck(index);
modCount++;
// 第二步：获取删除元素的值
E oldValue = elementData(index);
// 第三步：将 index 后面所有的元素往前移一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
// 第四步：返回要删除的值
return oldValue;
}
再看一个其它的实现：
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
eturn true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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; // clear to let GC do its work
}
更改操作
-
retainAll( Collection<?> c )：仅仅保留列表中和C相同的元素，相当于&运算 -
set（int index,E element）：用element替换index位置上的元素。 -
size()：返回此列表的元素数 -
sort(Comparator<? super E> c)：按照指定的排序规则排序 -
subList( int from , int to )：返回从from到to之间的列表 -
toArray()：将列表转化为数组 -
trimToSize( )：修改当前实例的容量是列表的当前大小。
set方法** 确保set的位置小于当前数组的长度（size）并且大于0，获取指定位置（index）元素，然后放到oldValue存放，将需要设置的元素放到指定的位置（index）上，然后将原来位置上的元素oldValue返回给用户。
// 第一步：
public E set(int index, E element) {
// 检查index是否大于size，如果是则抛出异常
rangeCheck(index);
E oldValue = elementData(index);
// 覆盖ArrayList中index上的元素
elementData[index] = element;
// 返回被覆盖的元素
return oldValue;
}
// 第二步；
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
subList方法** 我们看到代码中是创建了一个ArrayList 类里面的一个内部类SubList对象，传入的值中第一个参数时this参数，其实可以理解为返回当前list的部分视图，真实指向的存放数据内容的地方还是同一个地方，如果修改了sublist返回的内容的话，那么原来的list也会变动。
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
谨慎使用 ArrayList 中的 subList 方法
-
ArrayList 的 subList 结果不可强转成 ArrayList，否则会抛出 ClassCastException 异常，即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList. 说明：subList 返回的是 ArrayList 的内部类 SubList，并不是 ArrayList ，而是 ArrayList 的一个视图，对于 SubList 子列表的所有操作最终会反映到原列表上。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
ArrayList<String> strings = (ArrayList)list.subList(0, 1);
运行结果：Exception in thread "main" java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList at com.nuih.List.ArrayListTest.main(ArrayListTest.java:29)
-
在 subList 场景中，高度注意对原集合元素个数的修改，会导致子列表的遍历、增加、 删除均会产 ConcurrentModificationException 异常。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
List<String> subList = list.subList(0, 1);
// 对原 List 增加一个值
list.add("10");
subList.add("11"); // 这一行会报 java.util.ConcurrentModificationException
**trimToSize方法
public void trimToSize() {
// 修改次数加1
modCount++;
// 如果当前元素小于数组容量，则将elementData中空余的空间（包括null值）去除
// 例如：数组长度为10，其中只有前三个元素有值，其他为空，那么调用该方法后，数组的长度变为3
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
toArray方法** 第一个，Object[] toArray()方法。该方法有可能会抛出java.lang.ClassCastException异常，如果直接用向下转型的方法，将整个ArrayList集合转变为指定类型的Array数组，便会抛出该异常，而如果转化为Array数组时不向下转型，而是将每个元素向下转型，则不会抛出该异常，显然对数组中的元素一个个进行向下转型，效率不高，且不太方便。
第二个， T[] toArray(T[] a)方法。该方法可以直接将ArrayList转换得到的Array进行整体向下转型（转型其实是在该方法的源码中实现的），且从该方法的源码中可以看出，参数a的大小不足时，内部会调用Arrays.copyOf方法，该方法内部创建一个新的数组返回，因此对该方法的常用形式如下：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// 第一种方式（最常用）
Integer[] integer = arrayList.toArray(new Integer[0]);
// 第二种方式（容易理解）
Integer[] integer1 = new Integer[arrayList.size()];
arrayList.toArray(integer1);
// 抛出异常，java不支持向下转型
// Integer[] integer2 = new Integer[arrayList.size()];
// integer2 = arrayList.toArray();
查操作
-
contains（Object o）：如果包含元素o,则返回为true -
get（int index）:返回指定索引的元素 -
indexOf( Object o )：返回此列表中指定元素的第一次出现的索引，如果列表不包含此元素，返回-1 -
lastindexOf( Object o ):返回此列表中指定元素的最后一次出现的索引，如果列表不包含此元素，返回-1 -
isEmpty（）：如果列表为空，返回true -
iterator()：返回列表中元素的迭代器 -
listIterator（）：返回列表的列表迭代器（按适当的顺序） -
listIterator(int index)：从适当的位置返回列表的列表迭代器（按照正确的顺序）
get 方法** 返回指定位置上的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
contains方法** 调用indexOf方法，遍历数组中的每一个元素作对比，如果找到对于的元素，则返回true，没有找到则返回false。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
**iterator方法** interator方法返回的是一个内部类，由于内部类的创建默认含有外部的this指针，所以这个内部类可以调用到外部类的属性。
public Iterator<E> iterator() {
return new Itr();
}
一般的话，调用完iterator之后，我们会使用iterator做遍历，这里使用next做遍历的时候有个需要注意的地方，就是调用next的时候，可能会引发ConcurrentModificationException，当修改次数，与期望的修改次数（调用iterator方法时候的修改次数）不一致的时候，会发生该异常，详细我们看一下代码实现：
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
expectedModCount这个值是在用户调用ArrayList的iterator方法时候确定的，但是在这之后用户add，或者remove了ArrayList的元素，那么modCount就会改变，那么这个值就会不相等，将会引发ConcurrentModificationException异常，这个是在多线程使用情况下，比较常见的一个异常。
遍历
ArrayList 遍历的四种方式
-
第1种，普通for循环随机访问，通过索引值去遍历。
// 随机访问
List<String> list = new ArrayList<>();
int size = list.size();
for (int i = 0; i < size; i++) {
value = list.get(i);
}
-
第2种，通过迭代器遍历。即通过Iterator去遍历。
// 迭代器遍历
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
value = iter.next();
}
-
第3种，for-each。
// 增强for循环
for (String s : list) {
value = s;
}
-
第4种 forEach + lambda 循环遍历
list.forEach(p -> {
p.hashCode();
});
性能对比
既然有 4 种遍历，那我们看看哪种遍历效率下面我们通过一个实验来看下这四种循环的耗时吧：测试代码
package com.nuih.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.UUID;
public class ArrayListTest {
public static void main(String[] args) {
// 数据预热
List<String> testList = createTestList(10);
testForEach(testList);
testFor(testList);
testRandFor(10, testList);
List<Integer> integers = Arrays.asList(10, 50, 100, 500, 1000, 10000, 50000, 100000, 5000000, 10000000, 30000000);
for (Integer i : integers) {
testRand(i);
}
}
private static void testRand(int size) {
System.out.println("-----------次数:" + size + "------------");
List<String> list = createTestList(size);
// 随机访问通过索引值去遍历。
long time1 = System.nanoTime();
testRandFor(size, list);
long time2 = System.nanoTime();
// 增强 for 循环
testFor(list);
long time3 = System.nanoTime();
// 迭代器遍历
testIterator(list);
long time4 = System.nanoTime();
// forEach + lambda
testForEach(list);
long time5 = System.nanoTime();
System.out.println("随机访问\t\t" + (time2 - time1) / 1000 + " ms");
System.out.println("增强 for 遍历\t\t" + (time3 - time2) / 1000 + " ms");
System.out.println("迭代器遍历\t\t" + (time4 - time3) / 1000 + " ms");
System.out.println("forEach 遍历\t\t" + (time5 - time4) / 1000 + " ms");
System.out.println();
}
private static void testRandFor(int size, List<String> list) {
for (int i = 0; i < size; i++) {
list.get(i).hashCode();
}
}
private static void testFor(List<String> list) {
for (String s : list) {
s.hashCode();
}
}
private static void testIterator(List<String> list) {
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
iter.next().hashCode();
}
}
private static void testForEach(List<String> list) {
list.forEach(p -> {
p.hashCode();
});
}
public static List<String> createTestList(int size) {
List<String> list = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
list.add(UUID.randomUUID().toString());
}
return list;
}
}
测试结果：** 结论：如果数据量比较少的话貌似四种循环耗时都差不多，但是随着数据量的增长会发现 foreach 的效率是最好的。但是从上面我们会发现一个奇怪的现象，第一次循环的时候forEach 遍历的时间是最长的尽管数据量非常少也会这样。但是后面的耗时就正常了。如果放开测试里面的预热代码，每次跑出来的耗时也是正常的。
-----------次数:10------------
随机访问 15 ms
增强 for 遍历 8 ms
迭代器遍历 6 ms
forEach 遍历 65728 ms
-----------次数:50------------
随机访问 16 ms
增强 for 遍历 21 ms
迭代器遍历 13 ms
forEach 遍历 10 ms
-----------次数:100------------
随机访问 7 ms
增强 for 遍历 23 ms
迭代器遍历 34 ms
forEach 遍历 19 ms
-----------次数:500------------
随机访问 64 ms
增强 for 遍历 47 ms
迭代器遍历 39 ms
forEach 遍历 105 ms
-----------次数:1000------------
随机访问 129 ms
增强 for 遍历 99 ms
迭代器遍历 81 ms
forEach 遍历 58 ms
-----------次数:10000------------
随机访问 1748 ms
增强 for 遍历 1921 ms
迭代器遍历 1270 ms
forEach 遍历 2212 ms
-----------次数:50000------------
随机访问 4013 ms
增强 for 遍历 2739 ms
迭代器遍历 3628 ms
forEach 遍历 2368 ms
-----------次数:100000------------
随机访问 9874 ms
增强 for 遍历 4500 ms
迭代器遍历 5159 ms
forEach 遍历 6232 ms
-----------次数:5000000------------
随机访问 215933 ms
增强 for 遍历 27000 ms
迭代器遍历 26586 ms
forEach 遍历 22105 ms
-----------次数:10000000------------
随机访问 379588 ms
增强 for 遍历 57104 ms
迭代器遍历 42973 ms
forEach 遍历 40539 ms
-----------次数:30000000------------
随机访问 1090531 ms
增强 for 遍历 195013 ms
迭代器遍历 185519 ms
forEach 遍历 151925 ms
ArrayList 删除数据
虽然有四种遍历方式，但是能够正确删除数据的方式只有两种
-
第 1 种通过迭代器进行删除。这种方式的话，也是《阿里代码规约》所推荐的。
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
iter.next().hashCode();
iter.remove();
}
-
第 2 种 倒序循环删除
for(int i = list.size()-1;i>=0;i--) {
list.remove(i);
}
下面再演示下错误的删除操作
-
普通 for 循环 正序删除，删除过程中元素向左移动，不能删除重复的元素
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
for(int i=0;i<list.size();i++){
list.remove(i);
}
System.out.println(String.join(",",list));
结果输出：1
-
增强 for 循环删除会抛出 java.util.ConcurrentModificationException
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
for (String s : list) {
list.remove(s);
}
System.out.println(String.join(",",list));
ArrayList ConcurrentModificationException
ConcurrentModificationException 出现在使用 ForEach遍历，迭代器遍历的同时，进行删除，增加出现的异常。平常使用的ArrayList, HashMap都有可能抛出这种异常，粗心的话，很容易犯这种错误，导致线上事故！
下面总结下ArrayList的一些使用场景，来讨论是否会抛出ConcurrentModificationException
For..i 遍历
这个遍历的意思，是指 for(int i = 0 ; i <list.size(); i++)这种使用下标进行遍历的方式。 这种情形下，增加都不会有 ConcurrentModificationException。但是也可能导致另外的一些问题，比如下面这段代码，会死循环
List<Integer> list = new Arraylist<>();
list.add(1);
list.add(2);
list.add(3);
for(int i = 0;i<list.size();i++){
list.add(i);
}
遍历删除的情况下，不会有ConcurrentModificationException，但是要注意代码，防止数组越界异常。下面这种形式的代码会抛出数组越界异常。
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
int length = list.size();
for(int i = 0;i<length;i++){
list.remove(i);
}
ForEach 遍历
ForEach 遍历就是 For(Object o : List) 这种遍历方式，众所周知，ForEach循环只是JAVA的一个语法糖，在字节码层面上，等同于迭代器循环遍历。在这种情形下，增加元素一定会抛出ConcurrentModificationException， 而删除元素在大多数情况下，会抛出ConcurrentModificationException（小知识，当且仅当删除小标为 size()-2，也就是倒数第二个元素的时候，不会抛出异常）。 这种情况下，会有异常抛出
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for (Integer i : list) {
if(i == 1){
list.remove(i);
}
}
可以修改上面的判断语句， i == 1 修改为 i == 2 则不会抛出异常。
subList
在 subList 场景中，高度注意对原集合元素个数的修改，会导致子列表的遍历、增加、 删除均会产 ConcurrentModificationException 异常。
List<String> list = new ArrayList<>();
list.add("1");
list.add("1");
list.add("2");
List<String> subList = list.subList(0, 1);
// 对原 List 增加一个值
list.add("10");
subList.add("11"); // 这一行会报 java.util.ConcurrentModificationException
如何避免ConcurrentModificationException
-
需要遍历新增时，最好new一个和老List相同的临时List，遍历老的List，然后在临时List上进行元素的增加 -
需要进行删除时，使用迭代器删除(iterator.remove())，而不是直接调用 list.remove() 3.小心，谨慎
总结
ArrayList底层采用数组实现，是一个用于持有元素的有序、元素可重复的容器。适用于需要查找指定索引处元素的场景。当需要频繁插入、删除元素，或者查找指定元素时，其复杂度为O(n)。
-
初始化 List 的时候尽量指定它的容量大小。( 尽量减少扩容次数) -
当使用无参数构造函数创建ArrayList对象时，ArrayList对象中的数组初始长度为0（是一个空数组）。 -
ArrayList的扩容策略是每次都增加当前数组长度的一半（非固定分配）。 -
ArrayList的扩容方式是直接创建一个新的数组，并将数据拷贝到新数组中。
👇点击阅读原文，查看往期内容！
快留言👇和我互动吧～