- elementData:就是实际存储元素的数组,被transient,表明不参与序列化,意味着elementData里的数据仅存在调用者的内存中
- EMPTY_ELEMENT空数组
-
DEFAULTCAPACITY_EMPTY_ELEMENT: 不同于EMPTY_ELEMENT,这个空的Object[]有啥用?
(为什么要两个空数组?3号空数组用法如下,那么二号呢?其实二号要解决的是当我想创建一个空集合时,即调用new ArrayList(0),在随后调用add方法时,不会被自动扩容成大小为10,这就是二者区别-defaultCapacity。)
无参构造函数当调用无参构造函数时,将它赋给elementData,这样做感觉好像没多大用?其实它就像一个标记,什么时候会用到它呢?当第一个元素被添加的时候
size: 是实际元素个数
扩容三姐妹之二三---DEFAULT_CAPACITY = 10;也就是说当你new ArrayList()调用add(E e)或是其它add方法后,会根据需要创建一个Object[minCapacity]初始数组-------(感觉写了半天细枝末节的东西)
---modeCount是用作Fail-Fast机制
---grow()执行数组扩容操作,利用Arrays.copyOf(),继续追踪发现是调用了System.arrayCopy(),创建了一个扩容后大小的新数组copy[],返回copy
ArrayList还有一类构造函数:ArrayList(Collection<? extends E> c),它什么原理呢? Collection接口有个toArray(),举例如具体实现类ArrayList的toArray()里调用Arrays.copyOf(),如上所述它返还一个copy[],而该构造函数里就利用了这个来将c转化为数组赋给elementData。其实很多地方都用到了Arrays.copy(),比如trimToSize()..
ADD():
ArrayList其实是一个动态变化的数组,我们来看它在添加删除元素时的变化:
从add入手:add(E e); add(int index; E elementi); add(Collention<? extends E> c); add(int index, Collection<? extends E> c)四种方法。
- add(E e):首先会调用ensureCapacityInternal(size+1),该方法又会调用ensureEcplicitCapacity(),在该方法里如果size+1>elementData.length,则调用growth()方法进行扩容,逻辑如下
一般情况下扩容为原来的1.5倍,这里又用到 了Arrays.copyOf()
- add(int index, E e)
显而易见,先判断index是否越界,在进行扩容判断,之后调用System.arraycopy()将原数组index及之后的元素后挪一位,最后添加
- add(Collention<? extends E> c)与add(int index, Collection<? extends E> c)核心类是toArray()与System.arraycopy(),与之前提的一样(代码不贴了--累人!)
indexOf(Object o)与lastIndexOf(Object o)都会对o进行null判断,因为ArrayList可以添加null;clone()为浅拷贝,elementData数据不包括在内
get,set,remove方法都没什么好说的
removeAll(Collection<?> c), retainAll(Collection<?> c)
这两个方法中若c==null则抛出NullPointException异常,接着调用batchRemove(Collection<?> c, boolean complement)
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;
}
//w == size则说明没有改变,返回false,removeAll与retainAll结果为false
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;
}
该方法在complement为true时,取elementData与c的交集,即相同部分保留;为false时,取elementData独有部分保留。所以removeAll调用batchRemove(c, false),retainAll调用batchRemove(c, true);
迭代器
- Iterator
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回的元素的下标
int lastRet = -1; // 被返回的元素的下标,即调用next()返回elementData[lastRet]
int expectedModCount = modCount; //fail-fast,迭代中若数组被更改(add,remove
添加删除操作)会造成二者不相等,抛ConcurrentModificationException
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); //fail-fast
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); //调用的是ArrayList的remove方法
cursor = lastRet; //lastRet表示被删除的位置,后被cusor前挪一位填补上,cusor变为lastRet
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//如果相对elementData中每个元素都执行相同操作,你可以写一类实现Consumer接口,
复写accept(),在调用该方法
@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();
}
}
Consumer是个函数式接口,函数描述符为:T → void, 多用于lambda
- ListIterator
//继承itr,实现ListIterator implements Iterator<E>,ListIterator拓展了Iterator
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;
}
//前一个元素位置
public int previousIndex() {
return cursor - 1;
}
//返回前一个元素,即cusor-1处;cusor退一位,反复调用实现倒叙;如果之后你接着调用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();
cursor = i;
return (E) elementData[lastRet = i];
}
//下面的add()方法会重置lastRet = -1;所以add后避免调用set
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//add会插入到原本调用next函数返回的元素之前,cusor自增1仍指向原本next函数返回的元素,
此时可通过previous来得到新增的元素;这样设计保证了next函数不受影响
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
SubList extends AbstractList<E> implements RandomAccess
内部类private class SubList,作用就是生成一个[fromeIndex,toIndex)大小的小型List,麻雀虽小五脏俱全,只能通过subList(int fromIndex, int toIndex)函数调用,功能实现依赖外部类ArrayList,实现了自己的迭代器ListIterator。
还有一方法Arraylist.sort在这篇文章里介绍MergeSort与TimSort,ComparableTimSort
网友评论