文章目录
- 类图
- 声明
- RandomAccess 接口
- Cloneable 接口
- Serializable 接口
- List 接口
- AbstractList 抽象类
- 属性
- DEFAULT_CAPACITY
- EMPTY_ELEMENTDATA
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- elementData
- size
- 构造方法
- 方法
- trimToSize()
- 容量计算、扩容
- size()、isEmpty() 、 contains(Object o) 、indexOf(Object o)、lastIndexOf(Object o)、clone()
- toArray()
- get(int index)、set(int index, E element)
- add(E e)、add(int index, E element)、remove(int index)、remove(Object o)、clear()
- addAll()
- removeAll(Collection c)、retainAll(Collection c)
- removeAll() 分析 - batchRemove(c, false)
- retainAll() 分析 - batchRemove(c, true)
- 序列化、反序列化 writeObject()、readObject()
- 迭代器
- Iterator
- ListIterator
- forEach()
- removeIf()
- replaceAll()
- sort()
- subList() //TODO
- 划重点
- 参考
类图
声明
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
RandomAccess 接口
RandomAccess
接口是一个标记接口,用于 List
,实现该接口意味着可以提供快速的随机访问
。比如 ArrayList
实现了 RandomAccess
,因为ArrayList
底层是数组实现的,可以支持常数级 O(1)
的随机访问;而 LinkedList
则没有实现 RandomAccess
,因为 LinkedList
底层是双向链表,查找的时间复杂度为 O(n)
,并不是常数级。List
拥有快速随机访问功能时,遍历时采用 fori循环
最快速;而没有这个功能的 List
,遍历时采用 Iterator迭代器
最快速。
Cloneable 接口
Cloneable
接口也是一个标记接口,只有实现 Cloneable
接口,并且重写了 Object
类中的 clone()
方法,才能调用 clone()
进行克隆,否则会抛出异常 CloneNotSupportedException
。
Serializable 接口
可序列化的标记接口
List 接口
List
接口继承自 Collection
接口,添加了一些 List
的专有方法
AbstractList 抽象类
提供了 List
接口中一些方法的默认实现,也包括 Iterator
、ListIterator
,其中有些实现是直接抛出异常 UnsupportedOperationException
,比如 add(int, E)
、remove(int)
、get(int)
、set(int, E)
。
AbstractList 中的重要字段 modCount
/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;
记录 List
的结构化修改的次数。结构化修改指的是使 size
发生变化的操作(包括增删,不包括更新),或扰乱正在运行的迭代器,使其产生错误结果的操作。
这个字段被用于 Iterator
、ListIterator
迭代器,如果在执行 next()
、remove()
、previous()
、set()
、add()
方法时,这个字段发生出乎意料的变化,迭代器将抛出异常 ConcurrentModificationException
。在并发修改时,提供一种快速失败机制(fail-fast),而不是发生不确定的行为。
对子类而言,这个字段是可选的。如果子类想要提供快速失败机制(fail-fast),则需要在结构化修改时维护此字段;若不想提供,则可忽略本字段。
属性
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
*
* 默认的初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*
* 所有空的 ArrayList 实例所共享的空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*
* 所有默认初始容量的空 ArrayList 实例所共享的空数组实例。换句话说,就是所有由无参构造方法构造的空 ArrayList 实例的 elementData 字段共享的同一个值。
* 之所以 与 EMPTY_ELEMENTDATA 区别,是为了判断在添加第一个元素时,应该如何扩容。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*
* 存储 ArrayList 元素的数组。ArrayList 的容量等于 elementData.length。
* 任何 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将在第一次添加元素时被扩容为 DEFAULT_CAPACITY。
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* 包含的元素数量
*
* @serial
*/
private int size;
DEFAULT_CAPACITY
默认的初始容量。与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
配合使用,当 elementData
为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
时,第一次将扩容为 DEFAULT_CAPACITY
EMPTY_ELEMENTDATA
所有空的 ArrayList 实例所共享的空数组实例。或者说是所有空 ArrayList 的 elementData 字段共享的同一个值。可造成共享 EMPTY_ELEMENTDATA
的有三种情况:
- 使用有参构造方法
ArrayList(int initialCapacity)
传入 0 - 使用有参构造方法
ArrayList(Collection<? extends E> c)
传入空集合 ArrayList
中本来有元素,然后又都被删除了,导致size
又等于 0 了,此时调用trimToSize()
也会共享。
使用无参构造方法 ArrayList() 并不共享 EMPTY_ELEMENTDATA,而是共享下面的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
所有默认 size
的空 ArrayList
实例所共享的空数组实例。换句话说,就是所有由无参构造方法构造的空 ArrayList 实例的 elementData 字段共享的同一个值。
之所以 与 EMPTY_ELEMENTDATA 区别,是为了判断在添加第一个元素时,应该如何扩容。
- 当
elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
时, 扩容为 10 - 当
elementData == EMPTY_ELEMENTDATA
时,扩容为 1
elementData
存储 ArrayList 元素的数组。ArrayList 的容量等于 elementData.length
。任何 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
的空 ArrayList
都将在第一次添加元素时被扩容为 DEFAULT_CAPACITY。
size
包含的元素数量
构造方法
/**
* Constructs an empty list with the specified initial capacity.
*
* 构造一个指定容量的空 List
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 容量 > 0,创建数组,赋值给 elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 容量为 0,则将 EMPTY_ELEMENTDATA 赋值给 elementData,所以所有通过 new ArrayList(0) 创建的空 List 将共享 EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 容量非法,抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*
* 构造一个初始容量为 10 的空 List。这个 10 便是 DEFAULT_CAPACITY。
* 其实在构造完成后容量并不是 10,而是到添加第一个元素时才扩容为 10。
*/
public ArrayList() {
// 所有使用被构造方法构造的空 List 的 elementData字段,将共享空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* 构造一个包含指定集合中元素的 List,并且 List 中元素的顺序必须与集合的迭代器返回元素的顺序相同。
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
// 将集合中的元素转化为数组,并将新数组赋值给 elementData,toArray() 方法已经保证了返回的新数组中元素的顺序与集合迭代器返回的顺序相同。
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// List 的元素数 = 数组的长度,当元素数大于 0 时。
// 由于 toArray() 返回的不一定是 Object[],可能是其他数组,而 elementData 只能是 Object[],所以用 Arrays.copyOf 转化一下
// see 6260652 这好像是 jdk 的一个 bug,手动笑哭
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 当元素数 为 0 时,则将 EMPTY_ELEMENTDATA 赋值给 elementData,所以所有通过 new ArrayList(空集合) 创建的空 List 将共享 EMPTY_ELEMENTDATA
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
方法
trimToSize()
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*
* 调整 ArrayList 的容量为当前的元素数。这样能最小化 ArrayList 占用的存储空间
*/
public void trimToSize() {
// 结构化修改次数 + 1
modCount++;
// 当元素数量小于容量时才进行 trim
if (size < elementData.length) {
elementData = (size == 0)
// 元素数为 0,则 elementData = EMPTY_ELEMENTDATA,共享 EMPTY_ELEMENTDATA
? EMPTY_ELEMENTDATA
// 元素数 > 0,将元素复制到长度为 size 的新数组,类似 elementData = new Object[size]{所有元素}。
: Arrays.copyOf(elementData, size);
}
}
容量计算、扩容
其中最难以理解的是 grow()
方法的溢出代码感知 (overflow-conscious code) 部分,处理了 Integer 的溢出情况。溢出感知代码我是参考以下两篇文章的。
- 讲讲ArrayList的扩容和什么是溢出感知代码
- 溢出感知代码 - 你知道 if(a<b) 和 if (a - b < 0) 的区别吗?
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* 本方法可见性为 public,可被外部调用。
* 如果需要的话,会增加 List 的容量,以确保能容纳指定数量的元素
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
// elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 返回 10,否则返回 0
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
// 判断是否需要扩容,且过滤 minCapacity 为负数的情况
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
/**
* 计算临时的新容量
* 本方法实际只是处理 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的情况
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,可就是无参构造方法创建的。
// 至少会扩容为 DEFAULT_CAPACITY,也就是 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
// 使用calculateCapacity() 返回的临时新容量,调用 ensureExplicitCapacity()
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
// ...
modCount++;
// 溢出感知代码,若 minCapacity 已经溢出,minCapacity > elementData.length 会返回 false,不符合预期,所以用 minCapacity - elementData.length > 0 进行判断
// overflow-conscious code
// 当指定容量大于当前容量时才执行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*
* 数组的最大长度。
* 一些虚拟机会在数组中存储一些关键信息。请求更大的空间时会抛出异常 OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* 增加 List 的容量,以确保能容纳指定数量的元素
* 大体逻辑如下
* 1. 将旧容量乘以 1.5 倍得到新容量
* 2. 取新容量与最小容量的最大值作为新容量
* 3. 当新容量超过 MAX_ARRAY_SIZE 时,以 minCapacity 重新计算新容量。
* 判断最小容量是否溢出,溢出则抛异常;
* 否则,最小容量 > MAX_ARRAY_SIZE时,新容量为 Integer.MAX_VALUE,最小容量 ≤ MAX_ARRAY_SIZE时,新容量为 MAX_ARRAY_SIZE
* 4. 将原数组的元素复制到新数组,并赋值给 elementData
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
// 保存旧的容量
int oldCapacity = elementData.length;
// 新容量为旧容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// newCapacity、minCapacity 都可能溢出
// 如果 newCapacity 溢出的话,因为 minCapacity > oldCapacity,newCapacity == oldCapacity * 1.5,所以 newCapacity 的溢出值必然小于 minCapacity,newCapacity - minCapacity > 0
// 如果新容量 newCapacity 小于最小容量 minCapacity,以最小容量为准
// newCapacity、minCapacity 都没溢出 newCapacity < minCapacity、newCapacity - minCapacity < 0 都可判断
// newCapacity、minCapacity 都溢出了。由于无法判断两个溢出值的大小,所以无法判断大小
// newCapacity 溢出了,minCapacity 没有溢出。newCapacity == oldCapacity * 1.5。oldCapacity 本身没有溢出,所以 newCapacity 的溢出的最大值接近 oldCapacity * 0.5,而 minCapacity > oldCapacity == 两倍的newCapacity 的溢出的最大值 > newCapacity 的溢出的最大值 > newCapacity 的溢出值,即 minCapacity > newCapacity 的溢出值。newCapacity - minCapacity 可正确判断两数大小。
// newCapacity 没有溢出,minCapacity 溢出了。无法判断 newCapacity 与 minCapacity 溢出值的大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// newCapacity 超过允许的最大值 MAX_ARRAY_SIZE 时,以 minCapacity 重新计算新容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将原数组的元素复制到新数组,并赋值给 elementData
// 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();
// 最小容量没溢出,最小容量 > MAX_ARRAY_SIZE时,新容量为 Integer.MAX_VALUE,最小容量 ≤ MAX_ARRAY_SIZE时,新容量为 MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
size()、isEmpty() 、 contains(Object o) 、indexOf(Object o)、lastIndexOf(Object o)、clone()
/**
* Returns the number of elements in this list.
*
* 返回元素个数 O(1)
* @return the number of elements in this list
*/
public int size() {
return size;
}
/**
* Returns <tt>true</tt> if this list contains no elements.
*
* List 是否为空 O(1)
* @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* 元素是否存在
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
// 直接调用 indexOf() ,判断下标大于等于 0
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* 返回列表中第一个与指定元素匹配的索引,或者说最小的索引;如果列表中不包含该元素,则返回-1
*/
public int indexOf(Object o) {
// for 循环从 0 开始
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;
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* 返回列表中最后一个与指定元素匹配的索引,或者说最大的索引;如果列表中不包含该元素,则返回-1
*/
public int lastIndexOf(Object o) {
// for 循环从 size-1 开始
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
* 返回 List 的一个浅拷贝实例。List 中的元素不会被拷贝
* @return a clone of this <tt>ArrayList</tt> instance
*/
public Object clone() {
try {
// 调用 Object 的 clone() 返回拷贝的 List
ArrayList<?> v = (ArrayList<?>) super.clone();
// 将 elementData 复制一份,赋值给新 List,避 新老 List 操作同一个 elementData 数组
v.elementData = Arrays.copyOf(elementData, size);
// 重置 modCount
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
toArray()
/**
* Returns an array containing all of the elements in this list
* in proper sequence (from first to last element).
*
* <p>The returned array will be "safe" in that no references to it are
* maintained by this list. (In other words, this method must allocate
* a new array). The caller is thus free to modify the returned array.
*
* <p>This method acts as bridge between array-based and collection-based
* APIs.
*
* 返回一个包含 List 中所有元素的数组,元素的顺序与在 List 中的顺序一样。
* 由于返回的是一个新创建的数组,所有对其操作是安全的。
*
* @return an array containing all of the elements in this list in
* proper sequence
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* Returns an array containing all of the elements in this list in proper
* sequence (from first to last element); the runtime type of the returned
* array is that of the specified array. If the list fits in the
* specified array, it is returned therein. Otherwise, a new array is
* allocated with the runtime type of the specified array and the size of
* this list.
*
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* <tt>null</tt>. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
*
* 返回一个包含 List 中所有元素的数组,元素的顺序与在 List 中的顺序一样。
* 返回的数组的运行时类型与指定数组相同。如果指定的数组能够容纳 List 的元素,则使用它,否则创建一个新的运行时类型与指定数组相同,长度为 List.size() 的数组。
* 当指定数组的长度大于 List.size() 时,多余的位置会补 null
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this list
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// a 并不能容纳 List 的所有元素,则创建新数组
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 否则,将 List 元素放入 a
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
get(int index)、set(int index, E element)
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified position in this list.
* 返回指定索引的元素
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
// 检查索引的合法性
rangeCheck(index);
// 返回元素
return elementData(index);
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
* 替换指定位置的元素,并返回旧值
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
add(E e)、add(int index, E element)、remove(int index)、remove(Object o)、clear()
删除元素,不管是remove(int index)、remove(Object o)、还是 removeRange(int fromIndex, int toIndex)、removeAll(Collection c),思路就是将被删除元素的后续元素进行整体的左移。ArrayList 的做法是将后续元素向左复制 n 个单位,然后清空 size - 1 - n 到 size - 1 的元素。
/**
* Appends the specified element to the end of this list.
* 添加元素到 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;
}
/**
* 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++;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
* 删除指定位置的元素。后续元素左移。
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
// 检查索引的合法性
rangeCheck(index);
// 结构化修改次数 + 1
modCount++;
// 保存被删除的值
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 将元素向左复制
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 原本的最后一个元素置位 null,等待 GC 回收
// size - 1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* 如果指定元素存在,则删除第一个找到的,也就是索引最小的。如果不存在,则不发送改变。
* 存在指定元素,则返回 true,否则返回 false
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
// 区分 null 和 非null
// for 从 0 开始,若找到则调用 fastRemove() 删除,并返回 true
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 remove method that skips bounds checking and does not
* return the value removed.
* 私有的删除方法,省略索引的检测,且不返回被删除的元素。
* 代码和public 的 remove 雷同,只是省略索引的检测,且不返回被删除的元素。
*/
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
}
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
* 清空List,删除所有的元素
*/
public void clear() {
// 结构化修改次数 + 1
modCount++;
// 将数值的元素清空,等待GC回收
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
// 元素数重置为 0
size = 0;
}
addAll()
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* 按照指定集合的迭代器返回的顺序,将指定集合所有元素追加到 List 的末尾。如果在操作时修改了指定的集合,则此操作的行为是未定义的。
* 这意味着如果指定的集合是这个列表,并且这个列表是非空的,那么这个调用的行为是未定义的。
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
// 获取集合元素的数组,数组元素的顺序与迭代器返回的顺序相同
Object[] a = c.toArray();
int numNew = a.length;
// 如果需要的话,进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 追加元素到 List 末尾
System.arraycopy(a, 0, elementData, size, numNew);
// 元素数增加
size += numNew;
// 集合不为空则返回 true
return numNew != 0;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
* 1
* 从指定位置开始,将指定集合的元素插入到 List 中。指定位置以及后续元素向右移动。新元素将以指定集合迭代器的返回顺序出现在 List 中。
* 1
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检测索引的合法性
rangeCheckForAdd(index);
// 获取集合元素的数组,数组元素的顺序与迭代器返回的顺序相同
Object[] a = c.toArray();
int numNew = a.length;
// 如果需要的话,进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
// 指定位置以及后续元素向右复制 numMoved 个单位
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 将集合的元素插入 List
System.arraycopy(a, 0, elementData, index, numNew);
// 元素数增加
size += numNew;
// 集合不为空则返回 true
return numNew != 0;
}
removeAll(Collection c)、retainAll(Collection c)
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* 删除指定索引间的所有元素,从 fromIndex 到 toIndex,左闭右开的。
* 将后续元素向左移动。这个操作将减少 toIndex - fromIndex 个元素。若 toIndex==fromIndex 则不进行操作
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
// 结构化修改次数 + 1
modCount++;
int numMoved = size - toIndex;
// 将 toIndex 到末尾的元素整体向前复制到 fromIndex 的位置
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// 将原来的末尾的元素清空,等待GC回收
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
// 关闭元素数
size = newSize;
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
* 检测索引的合法性,但不检查索引为负数的情况,因为索引为负数时,数组会字段抛出异常 ArrayIndexOutOfBoundsException
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* A version of rangeCheck used by add and addAll.
* 检测索引的合法性
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
* 构建异常信息
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* 从 List 中删除指定集合中的所有元素
* 换句话说,就是删除 List 与集合的公共元素。
*
* @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);
}
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* 仅保留此 List 中包含在指定集合中的元素。
* 换句话说,从该列表中删除指定集合中不包含的所有元素。
* 只在 List 中保留 List 与集合的公共元素(交集)。
*
* @param c collection containing elements to be retained in 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 retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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;
}
removeAll() 分析 - batchRemove(c, false)
从 List 中删除指定集合中的所有元素。换句话说,就是删除 List 与集合的公共元素。
删除元素,思路就是将被删除元素的后续元素进行整体的左移。
// removeAll() 调用 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
for (; r < size; r++)
// batchRemove(c, false); 传入的是 false,也就是说,当集合中不包含 elementData[r] 时,才执行 if 语句的逻辑。
// 当集合中不包含 elementData[r] ,即 elementData[r] 不是 List 与集合的公共元素,也就是说不删除 elementData[r]。
// 当 elementData[r] 为不用删除的元素时,执行 if 语句的逻辑
if (c.contains(elementData[r]) == complement)
// 当 elementData[r] 为不用删除的元素时,将其左移到 elementData[w] 的位置,然后 w + 1。
// 也就是说 w 记录的是不用删除的元素的个数。
// 当 for 循环结束后,elementData 的前 w 个元素就是不用删除的元素,索引从 0 到 w - 1
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 因为 r == size,所以不执行
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 什么情况下 w == size?w 记录的是不用删除的元素的个数。 w == size 意味着所有元素都不用删除,所以直接返回 modified(false)
if (w != size) {
// 索引从 0 到 w - 1 是不用删除的元素,那么只需要清空 w 到 size - 1 的元素即可
// 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;
}
retainAll() 分析 - batchRemove(c, true)
retainAll()
与 removeAll()
相比,只是 batchRemove(c, true)
第二个参数为 true,当集合包含 elementData[r]
时执行 if 逻辑,同样是将不用删除的元素整体左移。
序列化、反序列化 writeObject()、readObject()
ArrayList
有三个实例变量:size
、elementData
、modCount
,elementData
、modCount
都是 transient
的,无需写入。
/**
* Save the state of the <tt>ArrayList</tt> instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
// 写入 size 与其他隐藏的对象
s.defaultWriteObject();
// 将 size 作为容量写入,以兼容 clone() ,没明白...
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// 按顺序写入数组元素
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 检查在此期间是否有修改,有则抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// elementData 默认值,size == 0 时
elementData = EMPTY_ELEMENTDATA;
// 读取 size 与其他隐藏的对象
// Read in size, and any hidden stuff
s.defaultReadObject();
// 读取容量,忽略返回值
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
// 分配数组容量
ensureCapacityInternal(size);
Object[] a = elementData;
// 按顺序读取元素
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
迭代器
Iterator
/**
* Returns an iterator over the elements in this list in proper sequence.
* 返回一个迭代器
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
* 此迭代器提供快速失败机制
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return 下一个返回元素的索引,默认为 0
int lastRet = -1; // index of last element returned; -1 if no such 最后返回的元素的索引,没有的话就是 -1
int expectedModCount = modCount; // 结构化修改的次数。默认为实例化迭代器时 List 的 modCount
Itr() {}
// cursor 指的是下一个返回元素的索引,为 size 时,说明已经到末尾了
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
// 并发修改检查
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
// 并发修改检查
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 记录最后返回元素的索引 lastRet = cursor
// cursor + 1 游标后移
// 返回 elementData[lastRet]
cursor = i + 1;
return (E) elementData[lastRet = i];
}
/**
* 删除迭代器返回的最后一个元素。
* 每调用一次 next() 方法后,只能调用一次 remove()
*/
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// 并发修改检查
checkForComodification();
try {
// 直接调用 ArrayList 的 remove
ArrayList.this.remove(lastRet);
// 游标左移一位
cursor = lastRet;
// 重置 lastRet,因为 lastRet 被删除了,所以没有 lastRet,置为默认值
lastRet = -1;
// ArrayList 的 remove 会修改 modCount,所以要同步一下 expectedModCount,保证后续操作不会报错
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 对剩余的元素执行指定的操作。剩余的元素指的是 cursor 及其后续元素
*/
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
ListIterator
/**
* Returns a list iterator over the elements in this list (in proper
* sequence), starting at the specified position in the list.
* The specified index indicates the first element that would be
* returned by an initial call to {@link ListIterator#next next}.
* An initial call to {@link ListIterator#previous previous} would
* return the element with the specified index minus one.
* 返回一个开始于指定位置的迭代器。首次调用 next() 将返回指定元素,首次调用 previous() 将返回 指定索引 - 1 的元素。
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
* 这个迭代器提供快速失败机制
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* Returns a list iterator over the elements in this list (in proper
* sequence).
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* An optimized version of AbstractList.ListItr
* 这个迭代器继承了上面的 Itr,提供了额外的方法
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
/**
* 返回下次调用 previous() 将返回的元素的索引,如果位于头部,则返回 -1
*/
public int previousIndex() {
return cursor - 1;
}
/**
* 返回列表中的前一个元素并反向移动光标位置。
* 交替调用 next() 和 previous() 将重复返回相同的元素。
*/
@SuppressWarnings("unchecked")
public E previous() {
// 并发修改检查
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 记录最后返回元素 lastRet = i = cursor - 1
// cursor = i = cursor - 1 游标左移
// 返回 elementData[lastRet]
cursor = i;
return (E) elementData[lastRet = i];
}
/**
* 用指定的元素替换 next() 或 previous() 返回的最后一个元素。
* 只有在调用过 nex() t或 previous() 之后, 既没有调用过 remove() 也没有调用过 add() 时,才能调用此方法。
* 可以连续调用本方法() ,因为本方法不会重置 lastRet
*/
public void set(E e) {
// 只有在调用过 nex() t或 previous() 之后, 既没有调用过 remove() 也没有调用过 add() 时,才能调用此方法。
// 也就是说 lastRet != -1
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 将指定的元素插入列表(可选操作)。该元素被插入到 next() 将返回的元素之前、previous() 将返回的元素之后。
* 如果列表中不包含元素,则新元素将成为列表中的唯一元素。
* 将新元素插入隐式游标之前:对 next() 的后续调用将不受影响,对 previous() 的后续调用将返回新元素。
* 此调用将方法 nextIndex() 或 previousIndex() 返回的值加 1。
*/
public void add(E e) {
checkForComodification();
try {
int i = cursor;
// 调用 ArrayList 的 add() 添加元素
ArrayList.this.add(i, e);
// 因为插入新元素后, 调用 next() 后返回新元素,所以要加一,以保证新元素被插入到 next() 将返回的元素之前。
// 又由于 previous() 会返回 next() 的前一个元素,而 next() 的前一个元素就是新元素,所以对 previous() 的后续调用将返回新元素。
// 因为 cursor 加一了,所以 nextIndex() 或 previousIndex() 返回的值都将加 1。
cursor = i + 1;
// 重置 lastRet
lastRet = -1;
// 由于ArrayList 的 add() 方法会修改 modCount,所以需要同步一下 expectedModCount,以保证后续操作不会报错。
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
forEach()
forEach()
和 Itr.forEachRemaining()
的实现很像
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
removeIf()
/**
* 1. 将要删除的元素找到,将其索引存入 BitSet
* 2. 将所有不用删除的元素向左移动,更准确的说是复制
* 3. 清空尾部的无效元素
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
// 要删除的元素个数
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
// 如果元素 i 需要被删除,将其记录到 removeSet 中,且 removeCount + 1
// removeSet 的第 n 位为 true,说明第 n 个元素需要删除
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
// 新 size = 原 size - 要删除元素的个数
final int newSize = size - removeCount;
// 将所有不用删除的元素重新排列
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
// 下一个不用删除的元素的索引
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
// 清空新 size 到 size - 1 之间的无效元素
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
// 新 size
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
replaceAll()
首先要解释一下 UnaryOperator
接口,它继承了 Function
接口,且它的泛型为 T, T
,所有它的方法为 T apply(T t);
,参数与返回值的类型相同。
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
// 将所有元素执行指定操作后,再放回原位置
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
sort()
/**
* 以指定的比较器排序 List。
* 若比较器为 null,则 List 的元素必须实现了 Comparable 接口
*/
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
subList() //TODO
划重点
- 如何扩容以及扩容的倍数
- 溢出感知代码
- removeAll() 时对 batchRemove() 方法的调用解析,感受 jdk 源码之美
- 两种迭代器的实现,尤其是 add() 方法的实现
参考
- java集合-ArrayList中EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别
- 讲讲ArrayList的扩容和什么是溢出感知代码
- 溢出感知代码 - 你知道 if(a<b) 和 if (a - b < 0) 的区别吗?
- BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?
- ArrayList 里的 removeAll() 及 batchRemove() 方法【可能让你感受到jdk之美的文章】