ArrayList
- extends: AbstractList<E>
- implements:
- List<E>
- RandomAccess :随机访问功能
- Cloneable：覆盖了clone()，可以clone
- java.io.Serializable:可以序列化传输
- 底层：array
- 初始容量：10
- 容量: private int size：
- 构造函数：
//* 含参数
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//创建新的object数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {]
//用默认的空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//非法的容量
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
// * 不含参数
public ArrayList() {
//构造默认容量的数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- trimToSize()：修剪容量到实际容量大小
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
- 确保容量
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
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);
}
- isEmpty()：判断是否为空
- contains(Object o)：判断是否存在元素
- indexOf(Object o)：寻找元素第一个位置并返回。
- lastIndexOf(Object o)：寻找元素倒数第一个位置并返回。
- Object clone()：克隆出一个新的ArrayList
- Object[] toArray():返回一个包含所有元素的数组
- 查找元素
public E get(int index) {
//判断是否角标越界，越界IndexOutOfBoundsException
rangeCheck(index);
return elementData(index);
}
- 设置元素的数据
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 添加元素
public boolean add(E e) {
//先让数组扩容
ensureCapacityInternal(size + 1);
//最后一个元素是新元素
elementData[size++] = e;
return true;
}
- 指定位置添加元素
public void add(int index, E element) {
//先检查越界
rangeCheckForAdd(index);
//容量增加1
ensureCapacityInternal(size + 1);
//添加元素相对慢的原因所在
//复制数组，新元素索引之后的元素都复制到新数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
- 删除元素
public E remove(int index) {
//先检查越界
rangeCheck(index);
//此列表被结构修改的次数。
//在使用迭代器遍历的时候，用来检查列表中的元素是否发生结构性变化（列表元素//数量发生改变）了，
//主要在多线程环境下需要使用，防止一个线程正在迭代遍历，
//另一个线程修改了这个列表的结构。
//好好认识下这个异常：ConcurrentModificationException。
//ArrayList是非线程安全的。
modCount++;
E oldValue = elementData(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;
}
- 快速删除
private void fastRemove(int index) {
//修改次数+1
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// clear to let GC do its work
elementData[--size] = null;
}
- 清空（删除所有元素）
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
- 检查是否越界,角标越界异常
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 与另外一个Collection取交集
//当集合A的大小改变的时候返回的是True,大小没有改变的时候返回的是False。
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
总结
- ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。
- 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。
- ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
- 对于新增和删除操作add和remove索引之后的所有元素，ArrayList要移动数据,所以效率相对较低
参考文章：
