pre:List结构类图
1.ArrayList
由族谱图可以看出ArrayList继承与AbstractList类，实现了List接口，AbstractList类中主要针对集合的subList()等方法完成具体实现，其余接口基本都没有重载，因此将集合的新增、删除、修改等方法交由了类ArrayList、Vector等子类去实现
1.1.先总结
由于源码解读实在是太长，为了读者这里先将ArrayList源码中比较重要的几个部分再这里总结下，带着问题去看源码，必将事半功倍
（1）ArrayList的底层数据结构是什么？
（2）ArrayList的插入、删除、查找、修改的时间复杂度分别为多少？
（3）ArrayList是否是线程安全的类？
（4）ArrayList再何时会去扩容？扩容的底层细节是什么?
（5）ArrayList是否支持手动扩容？如何实现的？
（6）ArrayList对于并发场景有哪些处理机制？如何去判断元素是否被其他线程修改
（7）ArrayList的迭代器是如何判断通过外部结构化的改变改变其持有的元素？
（8）ArrayList何时触发modCount++？
1.2.源码解读：
**概念：**ArrayList是由可调整大小的数组实现，其实现了List接口，能够持有所有元素，包括null，除了实现List接口之外，其还包括了一些操作内部存储数据的数组长度的方法，ArrayList与Vector大致相同，只是Vector是线程安全的
**时间复杂度：**size ， isEmpty ， get ， set ， iterator和listIterator的时间复杂度为O(1)，新增和删除的时间复杂度为O(n)，因为数组的插入需要将插入元素的下标之后的所有元素后移，删除同理。与LinkedList实现的常量因子相比，常量因子较低
**容量：**每个实例都有一个容量，容量是用于列表中存储元素的数组的大小，容量大小基本>=存储元素数组的大小（文档注释是这样的：It is always at least as large as the list size，大致就是>=的意思吧，如果有不对欢迎在评论区指正），初始容量=10，在添加元素是，容量会自动增长，代码中可以使用ensureCapacity操作在添加大量元素之前扩充数组的容量，这样可以减少增量重新分配的数量
**线程安全性：**ArrayList是线程不安全的，因此如果需要做同步，需要在外部做同步。（注意在外部有修改结构列表的操作是，很容易出现并发问题，结构操作就是新增、删除元素、显示的修改数组的容量），如果想得到线程安全的ArrayList，应该这样：
List list = Collections.synchronizedList(new ArrayList(...));
**迭代器操作：**如果通过iterator()创建了迭代器后，只能通过迭代器自己的remove或add方法操作元素，如果用别的方式修改列表元素，迭代器会立马抛出异常ConcurrentModificationException
例如在ArrayList中的迭代器实现类Itr中：
public E next() {
checkForComodification();
int i = cursor;
//cursor是在创建迭代器时生成,可以指定游标值,不指定则默认为0
//当一个线程请求到这里，而外部又改变了size的大小时，可能就会导致cursor值超过size值从而抛出异常
//而迭代器内部的remove和add操作元素会同步修改cursor和lastRet值
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
transient:
默认情况下,对象的所有成员变量都将被持久化.在某些情况下,如果你想避免持久化对象的一些成员变量,你可以使用transient关键字来标记他们,transient也是java中的保留字
源码：
源码中着重讲一下ArrayList的扩容在基本增删改方法中的体现，例如基本的empty()、size()、index()、containar()等比较简单的方法不再这部分讲解
package java.util;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认的容量
*/
private static final int DEFAULT_CAPACITY = 10;
//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小的空实例，就是说这个数组是使用默认大小DEFAULT_CAPACITY，与EMPTY_ELEMENTDATA的区别也是在这里
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储元素的数组缓冲区，不序列化
*/
transient Object[] elementData; // 非私有化简化内部类访问
/**
* ArrayList的大小（它包含的元素数），记得与elementData的length区分开
*/
private int size;
/**
* 指定容量的构造方法
*/
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);
}
}
/**
* 构造一个初始容量为10的空数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 构造一个列表，其顺序有迭代器的顺序指定。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray可能（不正确）不返回Object []
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 将容量变成当前数组的实际长度，减少不必要内存的使用
*/
public void trimToSize() {
modCount++;
//其中size记录的是数组的实际长度，而不是容量（容量代表已分配的大小），add元素的时候不是容量++,而是size++
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
//为数据持有的数据重新存储到长度为size的连续空间中
: Arrays.copyOf(elementData, size);
}
}
/**
* 如有必要，增加此ArrayList实例的容量，以确保它至少可以容纳最小容量参数指定的元素数量
*/
public void ensureCapacity(int minCapacity) {
//根据是否是最小值获得当前的最小扩容容量，如果还是初始化的条件，则要求入参minCapacity>10才会扩容
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
//如果数组从未扩容过，则会比较入参和默认容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 明确的扩容底层方法
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 比较入参和当前的容量，如果容量还没当前的大，则无需扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 最大的整型，可能会超出JVM的内存限制，发生OOM
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩充容量，以支持扩容最小容量锁能够支持的容量（实际的扩容方法）
*/
private void grow(int minCapacity) {
// 获得当前数组内存空间长度
int oldCapacity = elementData.length;
// 扩容至原来的1.5倍（只要minCapacity>当前容量就会触发扩容1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容1.5倍仍不够则直接扩容到minCapacity数值的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断是否会溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyof方法将elementData中的数据重新指向大小为newCapacity的连续空间
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;
}
/**
* 返回ArrayList的元素数量
*/
public int size() {
return size;
}
/**
* 见如下indexof方法
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 返回列表中指定位置的元素
*/
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;
}
/**
* 添加元素到队位
*/
public boolean add(E e) {
//该方法内部会去和当前容量比较，如果大于当前容量length就去扩容1.5倍
ensureCapacityInternal(size + 1); // modCount会++
elementData[size++] = e;
return true;
}
/**
* 添加元素到任意位置，位置之后的元素后移, index是从0开始数
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//Arrays.copyof()底层也是调用的如下方法,下列方法的入参分别为：
//src –源数组。
//srcPos –源数组中的起始位置。
//dest –目标数组。
//destPos –目标数据中的起始位置。
//length –要复制的数组元素的数量
//public static native void arraycopy(Object src, int srcPos,
// Object dest, int destPos,
// int length);
//相当于将插入位置的元素后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 删除元素，并将所有元素向左移动
*/
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);
elementData[--size] = null; // clear to let GC do its work 置null让gc回收元素
return oldValue;
}
/**
* 删除第一个匹配的元素
*/
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;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
/**
* addAll方法
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 注意要先后移元素再插入元素
*/
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)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* 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.)
*
* @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) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* 范围检查（往往用于读、修改、删除的方法）
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 范围检查（用于add和addAll方法）
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 移除指定集合的元素
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
/**
* 仅仅保留入参中的元素
*/
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;
}
/**
* 将实例的状态保存到流（也就是对其序列化）
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 记录修改次数,用于记录版本是否被修改，如果修改了则抛出并发异常
int expectedModCount = modCount;
s.defaultWriteObject();
s.writeInt(size);
// 按序写入流中.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//版本比较，用于判断并发
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 从流中重构ArrayList实例
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// 基于size去扩容
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
/**
* 迭代器工厂方法
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* 迭代器工厂方法
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* AbstractList.Itr的优化的版本
*/
private class Itr implements Iterator<E> {
int cursor; // 下个元素的位置
int lastRet = -1; // 当前元素的位置 ，-1代表没有此元素
//修改计数器，代表生成迭代器时候的版本，如果后续的操作判断该值与外部类ArrayList的modCount不一致就代表元素被外部写接 //口修改,直接抛出异常，通过迭代器添加或删除元素，会修改外部类的modCount的值
int expectedModCount = modCount;
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();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
}
public int nextIndex() {
}
public int previousIndex() {
}
@SuppressWarnings("unchecked")
public E previous() {
}
public void set(E e) {
}
public void add(E e) {
}
}
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
/**
* 提供了List的子集合的视图，类似于迭代器，也有版本控制的字段modCount，SubList与ArrayList同样继承与AbstractList类，
* 因此拥有相似的集合方法，并与父类共享modCount，如果通过外部新增元素，而再去读取subList则会检查
* checkForComodification(); 方法，此时SubList的modCount不等于外部类ArrayList的modCount，就会报错，类似于Itr的版本检 * 查
*/
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
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;
}
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
@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();
}
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
* Overriding implementations should document the reporting of additional
* characteristic values.
*
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
//该类不重要
//用于遍历和划分源元素的对象。 分离器覆盖的元素源可以是例如数组， Collection ，IO通道或生成器函数
static final class ArrayListSpliterator<E> implements Spliterator<E> {
}
@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++) {
@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) {
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];
}
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;
}
@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++;
}
@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++;
}
}