概要
- 类继承关系
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList<E>
- 定义
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
实现
- 创建
public ArrayList() {
this.elementData = DEFAULTCAPACITY_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);
}
}
由代码可知，ArrayList采用数组方式存放对象。无参构造器创建一个空Object数组
private static final Object[] EMPTY_ELEMENTDATA = {};
- 插入：add(E)
add方法其实就是给数组中某元素赋值为传入的对象，但add时有个明显的问题是，数组满了怎么办？我们接着往下看。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal函数的作用是保证数组大小是够用的。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
参数传入数组的size + 1， 如果数组为空数组，则将minCapacity设为10或者minCapacity中的大值
private static final int DEFAULT_CAPACITY = 10;
函数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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
首先产生新的数组大小为原来的1.5倍，若新的容量仍小于minCapacity，则minCapacity为新的容量，得出新的容量值后，调用Arrays.copyOf来生成新的数组对象，如想调整容量的生长策略，可继承ArrayList, 并覆写ensureCapacity方法。
在Collection中增加对象时，ArrayList还提供add(int, E)这样的方法，允许将元素直接插入到int位置。它要将当前数组的对象进行一次复制，即将目前index及其后的数据都往后挪一位，该方式要多一次复制数组的代价。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element; size++;
}
- 删除：remove(E)
先上代码：
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;
}
如果要删除的对象为null, 循环遍历整个数组，找到为null值的元素，调用fastRemove删除相应位置的对象。
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
}
又代码可知，fastRemove是一次数组的复制，将index后的对象统一向前移动一位，将最后一位设为null, 释放此对象的引用。
若对象非null, 则通过equals来进行比较，同样通过fastRemove来删除元素。
- 获取单个对象：get(int)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
先做数组范围检查，在返回对象。
- 遍历对象：iterator
public Iterator<E> iterator() { return new Itr();}
每次调用iterator方法时，都会new一个Itr的实例。
当调用此实例的hasNext方法时，比较当前指向的数组的位置是否和数组中已有元素大小相等，如相等返回false，否则返回true。
、、、
public boolean hasNext() {
return cursor != size; // cursor标识下一个返回元素的位置
}
、、、
当调用实例的next方法时，首先比较在创建此Iterator时获取的modCount与当前的modCount，如果不等，则说明在获取next元素时，发生了对集合大小产生影响（新增、删除）的动作。当发生这种情况时，则抛出ConcurrentModificationException。
- 判断对象时候存在：contains(E)
public boolean contains(Object o) { return indexOf(o) >= 0;}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
如果E为null,则直接判断已有元素是否为null, 否则通过判断E.equals和元素是否相等。
- transient
transient Object[] elementData; // non-private to simplify nested class access
声明为transient后，这个字段不会被序列化。
- SuppressWarnings
@SuppressWarnings("unchecked")
告诉编译器，对特定类型的warning保持沉默。
注：
- ArrayList基于数组实现，无容量的限制。
- ArrayList插入元素时可能要扩容，删除时并不会减小数组的容量。
- 若希望缩小数组容量，可以调用ArrayList的trimToSize()
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
- ArrayList非线程安全。
