ArrayList是一个线性表，底层使用Object数组存放元素，允许放入null元素。当放入的元素数量大于等于数组的容量时，数组会自动的扩容，默认扩大为原来的1.5倍，并把原数组的数据拷贝到新的数组。ArrayList支持随机访问，当数组容量很大时，在数组的中间插入和删除的效率很低。
-
ArrayList继承了那些类和实现了那些接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
-
List接口包含了ArrayList常用的方法
List.PNG
-
ArrayList的主要属性
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//存放元素的数组，是一个Object类型的数组
transient Object[] elementData;
//元素的个数
private int size;
//空的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//也是空的数组，和上面的EMPTY_ELEMENTDATA的值一样，但是表达的语意不同
//EMPTY_ELEMENTDATA是capacity为0时使用；
//而DEFAULTCAPACITY_EMPTY_ELEMENTDATA是没有指定capacity时使用，当添加元素时进行数组的初始化
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
-
ArrayList的构造方法
/**
* 没有指定具体的容量，elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
**/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 指定一个具体的容量，当容量大于0，则初始化elementData
* 当容量为0，则将elementData初始化为EMPTY_ELEMENTDATA
**/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 从Collection的子类拷贝
**/
public ArrayList(Collection<? extends E> c) {
//将集合转化为数组，赋值给elementData
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//如果elementData的类型不是Object[]，则使用Arrays.copyOf进行拷贝
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// elementData的长度为0
this.elementData = EMPTY_ELEMENTDATA;
}
}
-
ArrayList中比较重要的方法
- add()
在数组的末尾添加元素的方法，添加之前需要进行空间检查。如果数组还未初始化，则将数组初始化为容量为10；如果元素的数量超过容量则进行扩容，新的容量为原来的1.5倍。
- add()
public boolean add(E e) {
//确保数组大小 大于 数组中的元素的数量加1
//同时会将数组的修改记录modCount加一
ensureCapacityInternal(size + 1); // Increments modCount!!
//数组元素加一
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//调用calculateCapacity确保数组的延迟初始化
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//如果数组还未初始化 则返回ArrayList的默认大小10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//数组还未初始化
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//确保数组的容量大于元素的数量 并增加modCount++
private void ensureExplicitCapacity(int minCapacity) {
//为及时失败提供支持
modCount++;
//如果需要的最小容量大于数组的大小 则进行数组的扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容函数
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//新的容量为原数组的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//最多可以存放Integer.MAX_VALUE个元素
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//会创建一个newCapacity大小的数组 并把原数组的元素拷贝过去
elementData = Arrays.copyOf(elementData, newCapacity);
}
- add(int index,E e)
在list的index下标处添加元素e，会伴随大量元素的移动。
public void add(int index, E element) {
//检查index的下标是否正确
rangeCheckForAdd(index);
//检查数组的容量
ensureCapacityInternal(size + 1); // Increments modCount!!
//相当于把[index,..]的元素拷贝到[index + 1, ...]
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//添加元素
elementData[index] = element;
size++;
}
- addAll(Collection<? extends E> c)
添加多个元素，使用System.arraycopy将c.toArray拷贝到list的数组
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
- addAll(int index, Collection<? extends E> c)
将c的元素拷贝到list的index起始处
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
//检查数组容量
ensureCapacityInternal(size + numNew); // Increments modCount
//要移动的元素的数量
int numMoved = size - index;
if (numMoved > 0)
//将[index, ..]的元素移动到[index + numNew, ...]处
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//拷贝c集合的元素到index起始处
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
- get(int index)
获取index下标处的元素
public E get(int index) {
//检查下标
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
- set(int index, E element)
使用element覆盖index处的元素，并返回旧元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- remove(int index)
移除下标index的元素并返回，伴随有大量元素的移动
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//将[index+1, ...]的元素拷贝到[index, ...]
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//帮助GC
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- remove(Object o)
移除list中和o相同的元素，只移除第一个相同的元素
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;
}
-
modCount++的作用
每当add或者remove元素的时候，modCount都会增加或者减少，那么它的用处是什么？
先来看一段代码，这段代码移除list中的元素1，但是会抛出ConcurrentModificationException异常
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for(Integer i : list){
if(i == 1) {
list.remove(1);
}
}
这段代码也是移除list中的元素1，却不会抛出异常
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> it = list.iterator();
while (it.hasNext()){
if(it.next() == 1){
it.remove();
}
}
这两个循环底层都是用Iterator遍历list，但是一个使用list.remove()，一个使用it.remove()。
ArrayList中的迭代器
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
//注意这里，Itr初始化的时候，expectedModCount被赋值为modCount
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
//取出cursor的当前元素
@SuppressWarnings("unchecked")
public E next() {
//检查modCount
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;
//注意更新了lastRet
return (E) elementData[lastRet = i];
}
//使用迭代器移除lastRet指向的元素
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//移除元素
ArrayList.this.remove(lastRet);
//更新cursor
cursor = lastRet;
lastRet = -1;
//更新expectedModCount
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//检查modCount是否等于expectedModCount，不等则抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
注意next()函数中的checkForComodification()方法，这个方法会判断迭代器中的expectedModCount和ArrayList中的modCount是否相同，不同则抛出ConcurrentModificationException。而调用list.remove()方法会修改modCount的值，会修改modCount的值，所以会抛出异常。而使用迭代器的remove()方法，会同时更新expectedModCount，所以不会抛出异常。
