一、主要的成员变量
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
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.
*/
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.
*/
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;
protected transient int modCount = 0;
- DEFAULT_CAPACITY 表示初始的list容量大小
- EMPTY_ELEMENTDATA 表示空的list集合
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示带有默认容量的空的数值集合，与EMPTY_ELEMENTDATA区分是为了第一次添加元素时如何去扩容
- elementData表示list对象
- size表示list大小
- modCount 表示集合修改次数，防止并发造成数据不一致问题
二、创建ArrayList
1、空构造函数
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 这里是将elementData赋予DEFAULTCAPACITY_EMPTY_ELEMENTDATA
2、带集合参数的构造函数
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 将collection转为集合elementData
- 如果elementData 的长度为0，那么将elementData 赋予EMPTY_ELEMENTDATA，这里要与空构造函数赋值进行区别
- 如果elementData的长读不为0，赋值size；如果elementData对象不是Object[].class类型，转换为Object[].class类型
3、带初始容量大小的构造函数
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);
}
}
- 如果初始容量大于0，创建对应容量的数值对象，并赋给elementData
- 如果初始容量等于0，将EMPTY_ELEMENTDATA赋给elementData
三、添加元素
1、在list末尾添加单个元素
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
- modCount++表示修改次数加1
- add执行元素添加
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
- 如果添加元素的数量与数组的长度相等，开始扩容
- 如果添加元素的数量与数组的长度不相等，向数组的末尾添加元素，元素的总数量加1
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
- newCapacity(minCapacity)，传入最小的扩容大小，最后返回实际的扩容大小
- Arrays.copyOf会根据原数组，返回指定大小的数值
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
- 将容量扩大0.5倍，如果扩大后的容量newCapacity 小于最小扩容量minCapacity，若elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则返回DEFAULT_CAPACITY与minCapacity之间的最大值，否则返回minCapacity
- 如果扩大后的容量大于最小扩容量，若扩大后的容量小于最大允许容量MAX_ARRAY_SIZE ，则返回扩大后的容量newCapacity，否则根据hugeCapacity(minCapacity)进一步判断需要扩大的容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
- 若最小的扩容量minCapacity大于最大允许扩容量MAX_ARRAY_SIZE，则返回Integer的最大值，否则返回MAX_ARRAY_SIZE
2、指定位置添加单个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
- 检查索引值index
- 修改次数加1
- 判断是否需要扩容
- System.arraycopy复制元素，System.arraycopy是本地方法，用的是浅拷贝
- 在指定位置添加元素
- 元素数量加1
3、在末尾添加集合
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
- 将集合转为Object数组
- 修改次数加1
- 获取要添加集合的长度
- 判断是否需要扩容
- 利用System.arraycopy将集合添加至末尾
- 元素数量加numNew
4、在指定位置添加集合
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
- 前面主要是对index的验证，获取要添加集合的长度以及判断是否需要扩容
- 第一次System.arraycopy主要是将原index之后的数据移动到index+numNew
- 第二次System.arraycopy是将集合数据添加到原list列表中
- list元素的数量加numNew
四、查找元素
1、获取元素的索引值
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
分两种情况，如果元素为null，遍历elementData，返回第一个未null元素的索引值
如果元素不为null，遍历elementData，根据元素实现的equals方法去判断是否相等，返回第一个相等元素索引值
如果没有查到，返回-1
2、根据索引值获取元素
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
- 直接根据索引值从数值中获取元素
五、删除元素
1、根据索引值删除元素
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
- 获取该索引值
- 修改次数加1，元素数量减1，利用System.arraycopy对数据移动，将末尾值改为null
- 返回被删除的值
2、删除指定元素
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
- 主要是遍历获取元素的索引值，最后根据索引值，调用fastRemove进行删除操作
3、批量删除
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
- batchRemove有个参数complement，若为false，则删除与参数c匹配的元素，本次删除是false；若为true，则保留与c匹配的元素，retainAll函数传入的值就是true
- 首先遍历elementData，如果c包含该元素，则跳出，此时已经获取第一个需要重写的位置
- 再次遍历elementData，如果c包含该元素，则继续遍历；如果不包含，则将该元素写入到es
- 更改修改次数
- 调用shiftTailOverGap修改元素个数，已经剩下位置的元素置为null
4、条件批量删除
public boolean removeIf(Predicate<? super E> filter) {
return removeIf(filter, 0, size);
}
boolean removeIf(Predicate<? super E> filter, int i, final int end) {
Objects.requireNonNull(filter);
int expectedModCount = modCount;
final Object[] es = elementData;
// Optimize for initial run of survivors
for (; i < end && !filter.test(elementAt(es, i)); i++)
;
// Tolerate predicates that reentrantly access the collection for
// read (but writers still get CME), so traverse once to find
// elements to delete, a second pass to physically expunge.
if (i < end) {
final int beg = i;
final long[] deathRow = nBits(end - beg);
deathRow[0] = 1L; // set bit 0
for (i = beg + 1; i < end; i++)
if (filter.test(elementAt(es, i)))
setBit(deathRow, i - beg);
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
int w = beg;
for (i = beg; i < end; i++)
if (isClear(deathRow, i - beg))
es[w++] = es[i];
shiftTailOverGap(es, w, end);
return true;
} else {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return false;
}
}
- filter.test函数判断是否匹配，匹配返回真，不匹配返回false
- 获取第一个匹配的索引值
- 定义deathRow，若符合条件则相应的元素位置置为1
- isClear判断是否需要清除，若为0，返回为真，不需要清除，那么赋值给es
- shiftTailOverGap将剩下的位置元素置为null
5、删除索引区间的元素
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
shiftTailOverGap(elementData, fromIndex, toIndex);
}
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
- System.arraycopy将数值元素迁移
- 将剩下的位置元素置为null
六、改变元素
@Override
public void replaceAll(UnaryOperator<E> operator) {
replaceAllRange(operator, 0, size);
modCount++;
}
private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final Object[] es = elementData;
for (; modCount == expectedModCount && i < end; i++)
es[i] = operator.apply(elementAt(es, i));
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
- 遍历elementData，对每个元素执行operator.apply，最相应的更改
