基于动态数组实现了List接口。除了List接口的所有方法之外,还提供了调整内部数组大小的方法。该类与Vector类大致相同,区别在于 ArrayList是不支持同步 的。
size,isEmpty,get,set,iterator和listIterator方法都只需时间复杂度为O(1)。其他的操作时间复杂度为O(n)。且常数因子与LinkedList类相比更低。
每个ArrayList实例都有一个 capacity ,描述了该列表中实际用于存储元素的数组的大小。当向列表中添加元素时,capacity会自动增大。使用ensureCapacity方法,可以在向列表中添加大量元素之前先使数组扩容,避免列表自身多次自动扩容。
ArrayList内部使用一个数组来保存元素,ArrayList的容量就表示该数组的大小,
transient Object[] elementData; // non-private to simplify nested class access
任何空的ArrayList中的 elementData
数组用一个默认的空数组表示,
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
当向空ArrayList中添加第一个元素时,会扩容到 DEFAULT_CAPACITY
大小,
private static final int DEFAULT_CAPACITY = 10;
此外,ArrayList中还使用一个 size
记录当前保存元素的个数,
private int size;
add(E e)
方法可以向ArrayList的末尾添加一个元素,
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
其中会先调用 ensureCapacityInternal(int minCapacity)
方法对 elementData
数组的大小进行检查与扩容,
private void ensureCapacityInternal(int minCapacity) { // ensureCapacity方法返回数组所需要的大小 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
然后调用 ensureExplicitCapacity(int minCapacity)
方法,
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
使用 grow(int minCapacity)
方法对数组进行扩容并复制旧数组的元素到新数组中,
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 先设置新容量为旧容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新容量小于传入的要求容量,则新容量以要求容量为准 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量大于MAX_ARRAY_SIZE(2^31-1-8) if (newCapacity - MAX_ARRAY_SIZE > 0) // 判断要求容量的大小是否大于MAX_ARRAY_SIZE(2^31-1-8) // 若要求容量大于MAX_ARRAY_SIZE(2^31-1-8),则新容量为Integer.MAX_VALUE(2^31-1) // 否则新容量为MAX_ARRAY_SIZE(2^31-1-8) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // 将旧数组元素复制到新数组中 elementData = Arrays.copyOf(elementData, newCapacity); }
get(int index)
方法返回列表中指定位置的元素,
public E get(int index) { // 检查下标是否合法 rangeCheck(index); // 返回元素 return elementData(index); }
remove(int index)
方法删除列表中指定位置的元素并将其返回,
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); // 将数组最后一位设为null elementData[--size] = null; // clear to let GC do its work return oldValue; }
fail-fast 机制是java集合(Collection)中的一种错误机制。作用是在集合的迭代器的迭代期间,如果发现集合被其他线程修改,则抛出异常,避免执行一些不确定的操作。
例如:当某一个线程A通过迭代器去遍历某集合的过程中,若该集合的内容被其他线程所改变了,那么线程A访问集合时,就会抛出 ConcurrentModificationException
异常,产生fail-fast事件。
AbstractList中有一个 modCount
字段用于记录容器 结构发生变化
的次数,
protected transient int modCount = 0;
结构变化指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,若仅仅设置元素的值不算作结构发生变化,例如,
public boolean add(E e) { ensureCapacityInternal(size + 1); // 增加modCount elementData[size++] = e; return true; } public E remove(int index) { rangeCheck(index); modCount++; // 增加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; }
在使用ArrayList的迭代器时,迭代器中会记录当前列表的 modCount
,
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; // 记录创建迭代器时,容器的modCount ... }
在使用迭代器的 next()
, remove()
, previous()
, set()
或 add()
方法时,会通过检测该字段,判断容器是否被意外地修改了,
// 迭代器类中定义的检查modCount的方法,在迭代时容器被意外修改时抛出异常 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
如果容器的 modCount
与迭代器中记录的 expectedModCount
不一致,即容器在迭代器遍历期间被修改,就会返回 ConcurrentModificationException
异常。
Vector的实现与ArrayList相似,不过使用了 synchronized
进行同步,
// 添加元素 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } // 获取元素 public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); } // 删除元素 public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return oldValue; }
capacityIncrement
LinkedList使用双向链表保存元素,因此在插入删除操作的时候相比底层为数组的ArrayList更快,
// 节点的结构 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } // 头节点 transient Node<E> first; // 尾节点 transient Node<E> last;