ArrayList
实现List接口,包含List的所有操作,并且允许null元素。ArrayList与Vector等价,除了同步操作。另外其内部存在一个capacity,用来指明存储元素的列表大小,该值的大小至少与size值相等,由于capacity会自动增长以满足元素的存储。所以在实际使用的过程中要注意减少capacity的增长次数,减少开销。比如在添加大量元素时,最好指定一个初始化容量大小来减少capacity增长次数,减少内存的重新分配次数等。
需要注意的是ArrayList的操作不是同步的,意味着多线程操作会导致冲突。此时可以使用一个Object对象,通过同步该对象来完成ArrayList同步操作,或者:
Collections.synchronizedListdList(List<T> list)
该方法已经封装好了同步实现,两种方式本质是一致的。
构造ArrayList
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}
其他的构造方法类似,可以自行了解。
可以看到ArrayList的内部存储数据结构为数组,因此其特性与数组特性一致。
- 只能存储同一种数据类型的数据
- 一旦初始化,长度固定
- 数组中的元素与元素之间的内存地址是连续的,元素存在先后顺序
- 元素的索引速度很快
- 插入删除元素效率低
添加值
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
元素在添加之前需要判断是否需要增大容量。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
如果在初始化**ArrayList**时并未指定容量大小,此时将容量大小指定为默认容量大小(1.7版本该值为10)。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
可以看出要增大容量时有条件的。如果构造ArrayList时未传入容量大小,那么此时一定会满足上述代码的if条件从而进入下面的代码;或者指定了容量大小并且size已经大于容量大小也将进入下面的代码。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
上述代码将容量按照一定规则增大为一定的值。可以看到经过上面的操作之后,就可以直接在数组的size位置直接插入元素了。
删除值
包括按照索引删除remove(int index)和按照值删除remove(Object o)。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null;
return oldValue;
}
先对索引范围进行检查,在拿到待删除索引的对应值,如果不是删除的末尾元素,那么还需要对数组内容进行移动,这里有个小技巧,使用索引+1的位置开始的内容覆盖索引位置开始的内容,并将最后一个元素清空达到间接删除的效果。
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;
}
可以看到代码与上述的根据索引删除的代码实现类似,不在累述。
获取值
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
不在累述。至于iterator方法与次类似,请自行查看源码。