简介
java.util.ArrayList是Java集合框架中list接口的可变数组的实现，对list接口的全部实现以及允许null值，并提供相关可以操作底层存储数组的方法。
ArrayList底层的数据存储结构就是采用数组(数组是在内存中的一片连续的空间)，也就是对ArrayList的操作就是对数组的操作，从而操作的时间复杂度和数组一样：
- 访问特定元素：O(1)
- 添加元素：O(1)
- 插入/删除：O(n)
- 搜索
- 排序： O(logn)
- 未排序：O(n)
使用
- 创建一个ArrayList，3种方法:
// 使用无参构造函数
List<String> list = new ArrayList<>();
// 指定初始化大小
List<String> list = new ArrayList<>(16);
// 使用另外一个集合初始化
Collection<String> collection ...//某个集合
List<String> list = new ArrayList<>(collection);
其中，使用无参构造函数的创建方法默认初始化大小为10，源码如下：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 添加/插入
// new ArrayList
List<String> list = new ArrayList<>();
// 添加一个
list.add("A");
// 插入一个
// 注意指定位置大于数组大小，那么抛出`IndexOutOfBoundsException`异常
list.add(1,"B");
// 添加多个
list.addAll(Arrays.asList("C","D"));
// 插入多个
// 同样小心`IndexOutOfBoundsException`异常
list.addAll(1,Arrays.asList("E","F"));
- 删除
List<String> list = ...// ArrayList
//移除特定元素
list.remove("A");
// 移除某个元素
list.remove(1);
- 迭代/循环
//List<String> list = ...// ArrayList
// 使用`for-each`
for (String item : list) {
//...
}
// 使用Iterator正向迭代
for(Iterator<String> i = list.iterator();i.hasNext();){
String item = i.next();
//...
}
// 使用ListIterator使用逆向迭代
for(ListIterator<String> i = list.listIterator(); i.hasPrevious();){
String item = i.next();
//...
}
- 搜索
//List<String> list = ...// ArrayList
// 定位某个元素，一次出现，找不到返回-1
list.indexOf("A");
// 定位某个元素，最后一次出现，找不到返回-1
list.lastIndexOf("A");
// 查找多个，Java8 StreamAPI
List<String> result = list.stream().filter("D"::equals).collect(Collectors.toList());
// 如果对于排序的数据，可以通过二分搜索算法
List<String> copy = new ArrayList<>(stringsToSearch);
Collections.sort(copy);
int index = Collections.binarySearch(copy, "f");
源码分析&注意事项
添加时自动扩容
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(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;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
可以看出，添加时先判断最小容量是否允许添加，如果容量不够则通过grow扩容，扩大50%，通过oldCapacity>>1右移一位实现。其中，ArrayList最大为MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，modCount用于保存扩容次数，用于迭代器的快速失败迭代。
Iterator 和 ListIterator
ListIterator是Iterator子类，相对于Iterator，新增了逆序迭代、添加、替换等功能。
image.png
使用注意
- 在添加大量元素前，应用程序可以使用ensureCapacity 操作来增加ArrayList实例的容量或者在初始化的时候执行需要使用的大小，这可以减少递增式再分配的数量。
- 非线程安全，同步使用的时候需要外部同步锁，简单的可以通过包装实现：
List list = Collections.synchronizedList(new ArrayList(...));
