1. 类图
2. 基本属性
/**
* 默认容量 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
*
* 默认容量（10）的空数组,添加第一个元素时，这个数组的容量会扩展为10。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList 的元素存储在其中的数组缓冲区。
* ArrayList 的容量就是这个数组缓冲区的长度。
* 添加第一个元素时，任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空 ArrayList
* 都将扩展为 DEFAULT_CAPACITY。
*/
transient Object[] elementData; // 非私有以简化嵌套类访问
/**
* ArrayList 的大小（它包含的元素数）。
*/
private int size;
/**
* 要分配的数组的最大大小。
* 一些 JVM 在数组中保留一些头字。
* 尝试分配更大的数组可能会导致OutOfMemoryError: 请求的数组大小超出 JVM 限制
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
3. 构造方法
1. 没有指定容量，默认是创建一个容量为10的空列表DEFAULTCAPACITY_EMPTY_ELEMENTDATA
/**
* 构造一个初始容量为 10 的空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2. 指定容量，参数为0时是一个空数组EMPTY_ELEMENTDATA，参数大于0时，分配一块指定大小的连续空间。
/**
* 构造一个具有指定初始容量的空列表。
*
* @param initialCapacity 构造一个具有指定初始容量的空列表。
* @throws IllegalArgumentException 如果指定初始容量为负数
*/
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);
}
}
3. 入参指定集合时，将该集合参数转换为Object数组，
数组长度为0时，返回一个空数组EMPTY_ELEMENTDATA，
数组长度大于0时，调用Arrays.copyOf方法（基本类型深拷贝，引用类型浅拷贝）返回一个新的数组。
/**
* 构造一个包含指定集合的元素的列表，按照集合的迭代器返回的顺序。
*
* @param c 元素将被放入此列表的集合
* @throws NullPointerException 如果指定的集合为空
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
4. ArrayList容量相关方法
1. trimToSize()——手动缩小数组容量，减少占用内存
/**
* 手动缩容，释放内存。将此 ArrayList 实例的容量修剪为列表的当前大小。
* 应用程序可以使用此操作来最小化 ArrayList 实例的存储。
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
2. ensureCapacity(int minCapacity)——指定容量对数组手动扩容
/**
* 指定容量手动扩容，增加此ArrayList实例的容量，避免indexOut
* 以确保它至少可以容纳由最小容量参数指定的元素数量。
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
3. ensureCapacityInternal(int minCapacity)——如为 默认大小的空数组,将其首次扩容至 指定容量与默认容量10 里的最小值。最后调用ensureExplicitCapacity判断是否需要扩容
/**
* 每次对数组元素操作后调用的校验方法
* 如果为默认大小的空数组,将其首次扩容至 指定大小与默认10 里的最小值。
* 然后调用ensureExplicitCapacity判断是否需要扩容
* @param minCapacity 所需的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
4. ensureExplicitCapacity(int minCapacity)——数组操作次数自增 1，如数组容量不足，调用grow进行扩容
/**
* 修改次数自增 1
* 如数组容量不足，调用grow进行扩容
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
5. grow(int minCapacity)——扩容核心方法
扩容至原数组容量的1.5倍。如果扩容计算后，新容量比所需容量小（还是不够），则设置为所需最小容量。
如果容量大于允许的最大值 Integer.MAX_VALUE - 8，调用hugeCapacity方法校验最大容量。如允许则设置为Integer.MAX_VALUE，否则抛出OutOfMemoryError异常。
/**
* 增加容量以确保它至少可以容纳由最小容量参数指定的数量的元素。
*
* @param minCapacity 所需的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//记录原容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5倍扩容
if (newCapacity - minCapacity < 0) //如果扩容计算后，新容量比所需容量小（还是不够）
newCapacity = minCapacity; //设置为所需最小容量
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果容量大于允许的最大值 Integer.MAX_VALUE - 8
newCapacity = hugeCapacity(minCapacity); //校验
// minCapacity is usually close to size, so this is a win:)
elementData = Arrays.copyOf(elementData, newCapacity);//最终调用System.arraycopy返回新数组
}
6. int hugeCapacity(int minCapacity)——大容量数组校验
/**
* 数组最大容量校验
* minCapacity小于 0 说明超出机器数值显示范围报错 OOM
* 如果数组所需最小容量大于 Integer.MAX_VALUE - 8 设置为 Integer.MAX_VALUE
* 否则设置为 Integer.MAX_VALUE - 8
* @param minCapacity 所需数组最小容量
* @return 确定的数组容量
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
5. ArrayList私有方法
1. elementData(int index)——返回指定索引的元素
/**
* 实际执行返回指定元素的函数
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
2. rangeCheck(int index)——越界检查
/**
* 检查给定的索引是否在范围内。如果不是，则抛出适当的
* 运行时异常。此方法不检查索引是否为负：
* 它总是在数组访问之前立即使用，
* 如果索引为负，则抛出 ArrayIndexOutOfBoundsException。
*/
private void rangeCheck(int index) {
if (index >= size) //索引index从0，元素个数size从1开始
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
3.rangeCheckForAdd(int index)——add方法专用越界检查
/**
* add 和 addAll 使用的 rangeCheck 版本。
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
4.fastRemove(int index)——快速删除指定元素，无越界检查及返回值
/*
* 跳过边界检查并且不返回已删除值的私有删除方法。
*
*/
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;
}
5.batchRemove(Collection<?> c, boolean complement)——批量删除
private boolean batchRemove(Collection<?> c, boolean complement) { //指定数组c里元素，true为保留,false为删除
final Object[] elementData = this.elementData; //拷贝列表引用
int r = 0, w = 0;
boolean modified = false; //操作结果默认false
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) //快慢双指针，符合条件写入局部变量elementData
elementData[w++] = elementData[r];
} finally {
if (r != size) { //如果遍历后，列表索引不等于列表元素（c.contains()方法抛出异常，中断）
System.arraycopy(elementData, r,
elementData, w,
size - r); //将未来的及处理的元素，从中断索引向后，写入到列表
w += size - r; //修正列表元素个数
}
if (w != size) {
//如果新列表的个数跟原列表元素个数不同，对冗余元素进行处理
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w; //自增修改次数
size = w; //修正元素个数
modified = true; //标识处理成功
}
}
return modified; //返回处理结果
当complement参数为true时，对冗余元素进行处理前的示例图
如参数为false，则结果应为 2 4 3 4 5 最后处理就是根据 3 4 5 所在索引处理为elementData[i] = null;
6.subListRangeCheck(int fromIndex, int toIndex, int size)——子列表越界检测
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0) //小于0
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size) //大于列表元素个数
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex) //起始索引大于终止索引（如从索引9截取到1）
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
6. 实现List接口的方法
1. size() ——获取ArrayList数组元素个数
/**
* 返回此列表中的元素个数。
* @return 此列表中的元素数
*/
public int size() {
return size;
}
2. isEmpty() ——判断是否为空（元素个数 == 0）
/**
* 如果此列表不包含任何元素，则返回 true
* @return true 如果此列表不包含任何元素
*/
public boolean isEmpty() {
return size == 0;
}
3. contains(Object o) ——校验是否存在指定元素
/**
* 如果此列表包含指定的元素，则返回 true。
* 更严谨的说，当且仅当此列表包含至少一个元素时才返回 true
*
* @param o 要校验在此列表中是否存在的元素
* @return true 如果此列表包含指定的元素
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
4. indexOf(Object o) ——获取指定元素第一次出现的索引
/**
* 返回指定元素在此列表中第一次出现的索引(入参可以为 null)，
* 如果此列表不包含该元素，则返回 -1。
*/
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;
}
5. lastIndexOf(Object o) ——获取指定元素最后一次出现的索引
/**
* 返回指定元素在此列表中最后一次出现的索引，如果此列表不包含该元素，则返回 -1。
*/
public int lastIndexOf(Object o) {
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;
}
6. toArray()——返回一个固定长度的新数组Object[] objects
/**
* 以正序（从第一个元素到最后一个元素）返回一个包含此列表中所有元素的数组。
* 调用者可以*地修改返回的数组，此方法分配的是一个新数组。
* 此方法充当基于数组和基于集合的 API 之间的桥梁。
* @return 一个包含此列表中所有元素的数组，按正序排列
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
7. toArray(T[] a) ——返回一个固定长度、指定数组类型的数组（返回数组与入参类型一致）
/**
* 以正序返回包含此列表中所有元素的数组（从第一个元素到最后一个元素）;
* 返回数组的运行时类型是指定数组的类型。
*
* 如果列表arrayList存储元素个数大于指定数组（入参a）长度，返回数组是arrayList拆分的数组。
* 否则，将使用指定数组a的运行时类型和此 ArrayList 的大小分配一个新数组。
*
* 如果该数组的元素比列表多，则紧跟列表末尾的 数组中的元素被设置为 null。
* （如果调用者知道列表不包含任何空元素。这对于确定列表的长度很有用）
*
* @param a 如果容量它足够大，为存储列表元素的数组；
* 否则，将为此分配一个相同运行时类型的新数组。
* @return 包含列表元素的数组
* @throws ArrayStoreException 如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类型
* @throws NullPointerException 如果指定的数组为空
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) //指定数组长度小于ArrayList存储的元素数量
// 返回指定数组类型、ArrayList存储元素数量的数组
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
为了有助于理解下面这段，请看Test类
* 如果列表arrayList存储元素个数大于指定数组（入参a）长度，返回数组是arrayList拆分的数组。
* 否则，将使用指定数组a的运行时类型和此 ArrayList 的大小分配一个新数组。
*
* 如果该数组的元素比列表多，则紧跟列表末尾的 数组中的元素被设置为 null。
* （如果调用者知道列表不包含任何空元素。这对于确定列表的长度很有用）
public class ArrayListTest {
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
arrayList.add("7");
arrayList.add("8");
arrayList.add("9");
String[] list = {"0","1","2","3","4","5","6"};
Object[] objects = arrayList.toArray(list);
for (int i = 0; i < objects.length; i++) {
System.out.println(objects[i]);
}
}
}
输出结果如下
7 //arrayList里索引0的值
8 //arrayList里索引1的值
9 //arrayList里索引2的值
null // if (a.length > size) a[size] = null; 这段代码插入的null 覆盖了 list里的 a[3]
4 //list里索引4的值
5 //list里索引5的值
6 //list里索引6的值
8. get(int index)——返回指定索引元素
/**
* 返回此列表中指定位置的元素。先越界检查一下
*
* @param index 要返回的元素的索引
* @return 此列表中指定位置的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* 实际执行返回指定元素的函数
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
9.set(int index, E element)—— 设置元素到指定索引
/**
* 用指定的元素替换此列表中指定位置的元素。
* 先越界检查一下
*
* @param index 要替换的元素的索引
* @param element 要存储在指定位置的元素
* @return 之前在指定位置的元素
* @throws IndexOutOfBoundsException 越界异常
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
10.add(E e)—— 添加元素
/**
* 将指定的元素附加到此列表的末尾。
*
* @param e 要添加到此列表末尾的元素
* @return true 如添加成功
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); //存储的元素数量加1，操作次数加1
elementData[size++] = e;
return true;
}
11.add(int index, E element)——在指定位置插入元素
/**
* 在此列表中的指定位置插入指定元素。
* 将当前在该位置的元素（如果有）和任何后续元素向右移动（向它们的索引添加一个）
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException 数组越界异常
*/
public void add(int index, E element) {
//add方法专用的越界检查
rangeCheckForAdd(index);
// 存储的元素数量加1，操作次数加1
ensureCapacityInternal(size + 1);
//操作同一数组，元素右移一位，这个时候索引index与index+1的元素相同
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element; //指定元素覆盖原index索引的元素
size++;
}
12.remove(int index)——删除指定索引的元素，返回该元素
/**
* 移除此列表中指定位置的元素。
* 将任何后续元素向左移动（从它们的索引中减去一）
*
* @param index 要删除的元素的索引
* @return 从列表中删除的元素
* @throws IndexOutOfBoundsException 越界异常
*/
public E remove(int index) {
rangeCheck(index); //越界检查
modCount++; //修改次数加1
E oldValue = elementData(index); //获取该索引原元素
int numMoved = size - index - 1; //删除元素后的需要向左移动的元素个数
if (numMoved > 0) //如果需要移动元素个数>0
System.arraycopy(elementData, index+1, elementData, index,
numMoved); //向左覆盖一位
elementData[--size] = null; // 令最后索引为null，以便GC，减小数组元素个数1
return oldValue;//返回位于index索引的旧元素
}
13.remove(Object o)——删除指定元素，返回是否删除成功
/**
* 如果指定元素存在，从此列表中删除第一次出现的指定元素。
* 如果指定元素不存在，则不作变动。
* 如果此列表包含指定的元素（或此列表由于调用而更改），则返回true。
*
* @param o 要从此列表中删除的元素（如果存在）
* @return true如果此列表包含指定的元素
*/
public boolean remove(Object o) {
if (o == null) { //如果指定元素为null
for (int index = 0; index < size; index++) //遍历
if (elementData[index] == null) {
fastRemove(index); //调用ArrayList的私有方法fastRemove
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);//调用ArrayList的私有方法fastRemove
return true;
}
}
return false;
14. clear()——清空数组
/**
* 从此列表中删除所有元素。
* 此调用返回后，列表将为空。
*/
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
15. addAll(Collection<? extends E> c)——批量添加元素
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); //入参转换为Object数组
int numNew = a.length; //获取object数组长度
ensureCapacityInternal(size + numNew); // 判断添加所有元素后是否扩容,增加变动次数
//从a的索引0到numNew，拷贝到elementData索引size后面，
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew; //修正ArrayList的元素个数
return numNew != 0; //如果添加的元素数量不为0，返回true
}
16. addAll(Collection<? extends E> c)——从指定索引开始批量添加元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); //新增时数组越界检查
Object[] a = c.toArray(); //入参转换为Object数组
int numNew = a.length; //获取object数组长度
ensureCapacityInternal(size + numNew); // 判断添加所有元素后是否扩容,增加变动次数
int numMoved = size - index; //需要移动的元素个数
if (numMoved > 0) //如需移动的元素个数 > 0
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved); //elementData的index开始numMoved个元素，添加到elementData的index + numNew索引后面。
System.arraycopy(a, 0, elementData, index, numNew); //将a从0开始numNew个元素，添加到elementData的index索引后面。
size += numNew;
return numNew != 0;
}
17. removeAll(Collection<?> c) ——从列表中删除包含在指定集合中的所有元素。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c); //检查指定对象的引用非null
return batchRemove(c, false); //调用ArrayList私有方法
}
18. retainAll(Collection<?> c) ——从列表中保留包含在指定集合中的所有元素。
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c); //检查指定对象的引用非null
return batchRemove(c, true); //同上调用ArrayList私有方法，区别为参数
}
19. listIterator(int index) ——返回从指定索引开始的一个ListItr迭代器
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
20. listIterator() ——返回从索引0开始的一个ListItr迭代器
public ListIterator<E> listIterator() {
return new ListItr(0);//ListItr类的构造方法只有一个有参构造
}
21. iterator() ——返回从索引0开始的一个Itr迭代器
public Iterator<E> iterator() {
return new Itr();
}
22. subList(int fromIndex, int toIndex) ——截取一个子列表
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size); //调用ArrayList子列表越界检查
return new SubList(this, 0, fromIndex, toIndex); //调用构造方法创建子列表
}
7. 内部类
上文涉及到的迭代器Itr、ListItr在此简略介绍下
1. 迭代器Itr
1）基本属性
/**
* AbstractList.Itr 的优化版本
*/
private class Itr implements Iterator<E> {
int cursor; // 要返回的下一个元素的索引
int lastRet = -1; // 返回的最后一个元素的索引；如果没有返回 -1
int expectedModCount = modCount; //标记修改次数，预期
}
2）hasNext()——是否存在下一个元素
public boolean hasNext() {
return cursor != size; //如果不是最后一个元素，返回true
}
3）next()——获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); //多线程修改检测CAS算法，如果修改次数不符合预期，抛出异常
int i = cursor; // 要返回的下一个元素的索引
if (i >= size) //如果下一索引超出元素个数
throw new NoSuchElementException(); //抛出异常NoSuchElementException
Object[] elementData = ArrayList.this.elementData; //获取列表引用
if (i >= elementData.length) //如果下一索引超出元素个数，说明列表长度被修改了，与刚刚i >= size不一致
throw new ConcurrentModificationException(); //抛出ConcurrentModificationException
cursor = i + 1; //修正下一次调用时，应该获取的索引
return (E) elementData[lastRet = i]; //记录最后一次返回的元素的索引为i，并返回该索引位置的元素
}
4）remove()——删除最后一次返回的元素
public void remove() { //删除
if (lastRet < 0) //未返回过元素。
throw new IllegalStateException(); //抛异常
checkForComodification(); //CAS检测是否被其余线程修改
try {
ArrayList.this.remove(lastRet); //调用ArrayList的remove删除最后一次返回的元素
cursor = lastRet; //修正要返回的下一个元素的索引
lastRet = -1; //初始化lastRet为-1
expectedModCount = modCount; //自增修改次数
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException(); //如果越界了则判断其余线程修改过同一列表抛出异常
}
}
5）forEachRemaining(Consumer<? super E> consumer)——迭代所有剩余元素
@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++]); //赋值
}
// 在迭代结束时更新一次以减少堆写入流量
cursor = i;
lastRet = i - 1;
checkForComodification();
}
6）checkForComodification()——线程安全检测CAS算法实现
final void checkForComodification() { //线程安全检测
if (modCount != expectedModCount) //CAS算法，如果修改次数不符合预期，抛出异常
throw new ConcurrentModificationException();
}
2. 迭代器ListItr
1）构造参数
/**
* AbstractList.ListItr 的优化版本
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) { //有参构造
super();
cursor = index; //要返回的下一个元素的索引
}
}
2）相关判断
public boolean hasPrevious() { //前一个索引是否存在元素
return cursor != 0;
}
public int nextIndex() {
return cursor;
} //获取下一索引
public int previousIndex() {
return cursor - 1;
} //获取前一索引
3） previous()——获取前一个元素
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification(); //CAS检测
int i = cursor - 1; //修正索引i指向前一元素
if (i < 0) //如果前一个元素索引小于0（即现在元素索引为0）
throw new NoSuchElementException(); //异常
Object[] elementData = ArrayList.this.elementData; //获取列表引用
if (i >= elementData.length) //检测索引越界
throw new ConcurrentModificationException(); //越界说明列表被修改过
cursor = i; //修正要返回的下一个元素的索引
return (E) elementData[lastRet = i]; //记录最后一次返回的元素的索引为i，并返回该索引位置的元素
}
4）set(E e)——给前一次返回的元素索引位置，赋值指定元素
public void set(E e) { //元素赋值
if (lastRet < 0) //如未曾返回过元素
throw new IllegalStateException(); //不能确认要赋值到哪，抛出异常
checkForComodification(); //线程安全检测
try {
ArrayList.this.set(lastRet, e); //尝试将元素e赋值到最后返回的索引
} catch (IndexOutOfBoundsException ex) { //如ArrayList.this.set抛出越界异常
throw new ConcurrentModificationException(); //说明列表被修改了，线程不安全
}
}
5）add(E e)——在列表最后追加新元素
public void add(E e) {
checkForComodification(); //线程安全检测
try {
int i = cursor; //获取下次返回索引
ArrayList.this.add(i, e); //在该索引赋值为元素e
cursor = i + 1; //修正下次返回索引
lastRet = -1; //初始化最后返回索引
expectedModCount = modCount; //修改预期版本号
} catch (IndexOutOfBoundsException ex) { //add越界
throw new ConcurrentModificationException(); //被其余线程改了抛异常
}
}
}
3. 子列表 subList实现了RandomAccess接口
subList特性跟ArrayList完全一致，只在某些越界异常上有所区别
在此就不作具体介绍
1）构造方法
private class SubList extends AbstractList<E> implements RandomAccess{
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
}
2）基本属性
private final AbstractList<E> parent; //父列表
private final int parentOffset; //父偏移量
private final int offset; //偏移量
int size; //SubList实例的元素个数
4. ArrayListSpliterator
1）构造方法
/** 创建覆盖给定范围的新拆分器 */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // 确定为空，除非遍历
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
2）基本属性
private final ArrayList<E> list; //arrayList对象
private int index; // 当前索引，advance/split操作时会修改
private int fence; // 未使用为-1 ；使用后赋值为最后一次索引
private int expectedModCount; // 初始版本号
3）getFence()——获取可分割迭代器对应集合元素的长度
private int getFence() { // 获取可分割迭代器长度对应集合元素的长度
int hi; // (forEach方法专用变量)
ArrayList<E> lst;
if ((hi = fence) < 0) { //如果迭代器未被调用过
if ((lst = list) == null) //集合为空
hi = fence = 0; //初始化hi、fence=0
else { //集合不为null
expectedModCount = lst.modCount; //记录lst版本号
hi = fence = lst.size; //初始化hi、fence为列表元素个数
}
}
return hi;
}
4）trySplit()——继续拆分，返回一半长度、新的分割迭代器
public ArrayListSpliterator<E> trySplit() { //返回新的分割迭代器
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; //当前迭代器长度、起始索引、分割后索引
return (lo >= mid) ? null : // 除非太小，否则将分成前一半长度的迭代器返回
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
5）tryAdvance(Consumer<? super E> action)——对元素进行处理
public boolean tryAdvance(Consumer<? super E> action) { //处理元素
if (action == null) //处理动作为null
throw new NullPointerException();
int hi = getFence(), i = index; //获取迭代器大小，起始索引
if (i < hi) { //如果起始索引为到达最后一位
index = i + 1; //指针右移1
@SuppressWarnings("unchecked") E e = (E)list.elementData[i]; //获取元素
action.accept(e); //执行处理
if (list.modCount != expectedModCount)//检测线程安全
throw new ConcurrentModificationException();
return true; //操作成功
}
return false; //操作失败
}
public void forEachRemaining(Consumer<? super E> action) { //处理所有剩余元素
int i, hi, mc; // 提升在循环里的访问效率
ArrayList<E> lst; Object[] a;
if (action == null) //处理action为null
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {//集合引用，元素不为null
if ((hi = fence) < 0) { //非最后一位
mc = lst.modCount; //记录版本号
hi = lst.size; //指定起始位置为集合元素个数
}
else
mc = expectedModCount; //记录原始版本号
if ((i = index) >= 0 && (index = hi) <= a.length) { //未越界
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e); //执行处理
}
if (lst.modCount == mc) //如果版本号符合预期，结束
return;
}
}
throw new ConcurrentModificationException();//版本号变动，被其余线程修改过
}
public long estimateSize() {
return (long) (getFence() - index); //剩余未处理的元素个数
}
public int characteristics() { //返回size
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; //
}
8. 重写Object的方法
1. clone() ——克隆数组，浅克隆
/**
* 返回此 arrayList 实例的浅拷贝。
* （元素本身不会被复制）
*
* @return 此 ArrayList实例的克隆
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn‘t happen, since we are Cloneable
throw new InternalError(e);
}
}
9. 重写Iterable接口default方法
1. forEach(Consumer<? super E> action)——for循环迭代处理
//传入一个Consumer类，重写accept处理方法
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action); //判断action是否为null
final int expectedModCount = modCount; //获取原始版本号
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData; //获取列表引用
final int size = this.size; //获取元素个数
//如线程安全，for循环迭代
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]); //执行入参action里重写的accept处理
}
if (modCount != expectedModCount) { //CAS版本号不一致
throw new ConcurrentModificationException(); //抛出异常
}
}
10. 重写Collection接口default方法
1.spliterator()——返回一个可分割迭代器
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
2.removeIf(Predicate<? super E> filter)——如果符合指定条件删除元素
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter); //过滤器引用检测
// 确定要删除哪些元素
// 在此阶段如果filter抛出任何异常
// 将保持集合不变
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++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) { //获取过滤器filter判断结果，如果为true
removeSet.set(i); //从Set里删除该元素
removeCount++; //删除成功操作数+1
}
}
if (modCount != expectedModCount) { //线程安全检测
throw new ConcurrentModificationException();
}
// 将幸存的元素移动到已删除元素留下的空间上
final boolean anyToRemove = removeCount > 0; //是否删除过元素
if (anyToRemove) { //删除过
final int newSize = size - removeCount; //修正size
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { //循环赋值
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) { //清空重复元素
elementData[k] = null; // Let gc do its work
}
this.size = newSize; //修正集合元素大小
if (modCount != expectedModCount) { //线程检测
throw new ConcurrentModificationException();
}
modCount++; //修改版本号
}
return anyToRemove; //返回是否修改成功
}
11. 重写List接口default方法
1.replaceAll(UnaryOperator operator)——对符合operator条件的进行覆盖操作
@Override
@SuppressWarnings("unchecked")
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++; //版本号更新
}
示例如下
public class ArrayListTest {
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
arrayList.add("7");
arrayList.add("8");
arrayList.add("9");
arrayList.replaceAll(new UnaryOperator() {
@Override
public Object apply(Object o) {
if (o.equals("7")){
return "10";
}
return null;
}
});
arrayList.forEach(x-> System.out.println(x));
}
}
输出结果
10
null
null
2.sort(Comparator<? super E> c)——根据指定自定义c进行排序
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount; //预期版本号
Arrays.sort((E[]) elementData, 0, size, c); //Arrays.sort排序
if (modCount != expectedModCount) { //版本变动线程不安全
throw new ConcurrentModificationException(); //抛异常
}
modCount++; //版本号更新
}