0. ArrayList是什么
动态数组
1. 实现的本质
动态数组的本质当然是数组
2.常用接口
2.1 构造函数
- 无参时构建空数组，第一次存的时候创建一个大小为10的数组
- 指定初始容量，创建指定大小的数组
- 参数为
Collection对象，创建对象大小的数组，把对象拷过来
2.2 add方法
有4种add方法
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
流程都是类似的
- 计算新的容量，如果容量不够，则扩容1.5倍，将原数据拷过来
private void ensureCapacityInternal(int minCapacity) {
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);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
- 如果是插入，则将目标位置后的数据后移，然后添加新的数据，否则，直接拼接新的数据。
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
2.3 get方法
直接取值
2.4 remove方法
3个remove方法
public E remove(int index)
public boolean remove(Object o)
public boolean removeAll(Collection<?> c)
前两个很简单，删除元素后把后面的元素批量前移，需要注意的是remove(Ojbect o)时使用的是equals()方法，如果没有重写默认比较的是引用，主要看第三个。
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
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];
} 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++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
遍历数组，把不在需要移除集合中的元素重新排列在数组开始部分。
简单说就是把不需要移除的元素重新排列。（竟然联想到了标记-整理？？）
finally部分有一个操作是有可能没有遍历完，contains方法抛出异常，后面的就不管了，直接拼接到数组后面。
2.5 遍历Iterator
在每次对ArrayList修改操作后都有modCount记录修改次数，在Iterator操作中会检查这个值，有可能抛出ConcurrentModificationException
ListItr继承Itr并实现了ListIterator接口。
ListIterator比Iterator多了向前遍历、添加、修改的功能。
