主要分析增加和删除方法
//增加一个元素在末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//增加一个元素在指定位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
/**
*将从原来从下标为index开始起的数据整体向后移动一格，将新数据放在index处
**/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//从指定位置增加一个元素集合
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)//如果新插入的位置不在原来列表的尾部，需要将原来的列表从插入位置开始到原来结尾的所有数据整体向后移动需要插入的元素个数个位置
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
//判断是否需要扩充容量
private void ensureCapacityInternal(int minCapacity) {
/**
*如果原来没有数据，设置默认容量与所传入的容量的最大值为新的容量,DEFAULT_CAPACITY为10
**/
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);//新的空间为原来空间的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)//1.5倍以后如果大于默认的最大值，就以 Integer.MAX_VALUE为最大值
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
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;
}
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)//如果不是删除最后一个元素，需要将从删除位置之后的数据整体向前移动一个位置，否则不需要移动
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //删除位置标记为空，让垃圾回收器自动清理
return oldValue;
}
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;
}
/**
* 如果不是删除最后一个元素，需要将从删除位置之后的数据整体向前移动一个位置，否则不需要移动
**/
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
}
/**
*批量删除的逻辑，如果complement为true,表示删除原来列表中未在传入集合参数c中出现的元素
*如果complement为false,表示删除原来列表中在传入集合参数c中出现的元素
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];//符合要求的值覆盖原来位于[0,W]位置上的值
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)//删除从[w，size-1]所有元素
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
//重新整理空间，让元素的个数与分配数组空间的大小一致
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
在插入元素的时候会判断是否需要扩容，如果需要开辟新的空间，那么新的空间大小为原来的空间大小的1.5倍，但是不能超过Integer.MAX_VALUE。
删除元素的时候时候不会缩小原来分配的数组空间。只是将删除位置的元素设置为空，虽然元素个数size会变化，但是原来分配的数组空间不变，也就是说这个时候数组列表中不为空的元素的个数是小于或者等于所分配的空间，如果想重洗整理空间，调用trimToSize方法。
因为数组要求元素连续存放，查询某一个元素的时间代价为常数级（通过索引来获取），但是插入和删除的操作花费非常昂贵，对于插入操作，需要将原来的数据从插入位置开始整体向后挪动一位以腾出空间给需要插入的元素存放，对于删除元素，需要将表中的删除点之后的所有数据向前移动一个位置。
对于插入和删除操作的最坏的情况是从位置0开始，此时复杂度为O(n)。平均看来两种运算都需要移动表的一半的元素，因此仍然需要线性时间。
因此对于插入删除操作不是太频繁的情况而查询比较频繁时，用ArrayList较好。
网友评论