ArrayList类继承了AbstractList抽象类，AbstractList抽象类对于一些通用的方法提供了默认实现。ArrayList类实现了接口List、RandomAccess、Cloneable和Serializable。后三者都是语义标志接口，不提供任何实现，标记这个类具有某种功能。RandomAccess标记类具有随机访问的功能，Cloneable标记类具有克隆功能，Serializable标记类具有序列化功能。
<!--more-->
ArrayList类底层是由数组实现的，使用一个Object[]类型的变量来保存这个list的值。这个值不参与序列化，类中重写了writeObject()和readObject()方法来序列化该值。
```java
transient Object[] elementData;
```
变量size记录值的大小。
```java
private int size;
```
ArrayList有两个构造方法——有参构造方法和无参构造方法。
无参构造时，将数组列表的值赋为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
```java
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```
有参构造时，指定容量大于0，就构造一个指定容量大小的数组，如果指定容量为0，就将值赋为EMPTY_ELEMENTDATA。
```java
private static final Object[] EMPTY_ELEMENTDATA = {};
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);
}
}
```
也可以根据一个集合构造一个数组集合，将集合转为数组直接赋值给elementData。当值大小为0时，就将值赋为EMPTY_ELEMENTDATA。
```java
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;
}
}
```
那么，无参构造和有参构造产生的空值有什么区别呢？从表面上看来是一样的，在变量elementData上有这样一句注释，“ 添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。”
DEFAULT_CAPACITY指定为10。
```java
private static final int DEFAULT_CAPACITY = 10;
```
注释的意思是说，无参构造产生的空值在第一次添加元素时，将容量扩展至10。那么我们来看下add方法。
add方法首先将数组容量加1，这就涉及到了ArrayList的扩容机制，我们一步步来看。
```java
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
```
首先，判断目前数组的值是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即该数组是不是无参构造出的空数组。如果是，就取DEFAULT_CAPACITY和minCapacity的最大值，否则就扩展至指定的容量。第一次添加元素时，minCapacity为1，也就是说将数组扩展至10，如果是有参构造的空数组，就扩展至1。
```java
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
```
接下来要判断扩展的容量是否足够存放数组的值，足够存放就开始扩容工作。第一次添加元素时，数组长度为0，可以进入扩容工作。
```java
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
```
grow方法是ArrayList扩容机制的核心，可以看出，扩容的机制是扩展原来容量的0.5倍。如果扩容至1.5倍之后依旧无法达到指定容量大小或者大小超出了int类型的大小，就使用指定容量进行扩容。如果扩容容量大于数组最大容量，就扩容至Integer类型的最大值。最后重新申请一个数组，并进行数组的复制完成扩容工作。当第一次添加元素时，就数组的容量为0，扩容至1或10。
这里有一个疑问，既然ArrayList是数组来保存值的，数组的容量最大是Integer.MAX_VALUE - 8（查资料说是需要空间来保存一些头部信息），那么为什么ArrayList的容量还可以扩大至Integer.MAX_VALUE呢？
```java
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
```
由此可以看出，EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是为了区分有参构造和无参构造的空数组，从而使用不同的扩容规则。
我们可以注意到，上面方法中有一个modCount变量加1的操作。这个变量是从父类AbstractList中继承来的，它标记一个list被修改的次数。它主要是为了在迭代器中判断list是否被其他操作改变，进入迭代器会保存一个modCount值的副本，如果modCount的值变了，就抛出异常。
```java
protected transient int modCount = 0;
```
方法trimToSize将数组中多余容量释放。当使用容量小于数组容量时，如果使用容量为0，将数组设为空值，否则重新生成一个长度为size的数组。
```java
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
```
size方法可以获取list的大小。
```java
public int size() {
return size;
}
```
isEmpty方法判断list是否为空，即size是否为0.
```java
public boolean isEmpty() {
return size == 0;
}
```
contains方法判断数组是否包含参数。如果参数o在数组的位置不小于0，就说明数组中存在参数。
```java
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
```
indexOf方法判断参数在数组中的位置。如果参数o为null，那么在数组中找到一个null值的位置就好，不为空就是用equals方法找到数组中o的位置，找不到就返回-1。
```java
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;
}
```
lastIndexOf方法从后往前遍历，判断参数在数组中的位置。
```java
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;
}
```
clone方法克隆一个list。注意，该克隆是浅克隆，数组元素并没有复制。
```java
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
```
toArray方法将list转为数组。如果参数a的长度不够容纳list元素，就重新生成一个数组，否则就直接复制元素。a中有空余位置的话将size位置置为null。
```java
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
```
get方法返回指定位置的元素。首先检查index是否越界，然后返回数组index位置的元素。
```java
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```
set方法设置指定位置的元素。首先检查index是否越界，然后拿到index位置的旧值，将index位置的值设为新值，最后返回旧值。
```java
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
```
add方法向list中添加元素。不指定元素添加位置时默认添加到数组末尾，首先确保数组的容量，然后在数组后面添加一个元素，最后返回true。指定元素添加位置时，首先检查指定位置是否越界，然后确保数组的容量，然后将index以及之后的元素向后移动一位，将index位置设为指定元素，最后返回true。
```java
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```
remove方法移除指定位置的元素或移除指定元素。当指定的是元素位置时，先检查指定位置是否越界，然后获取指定位置的旧值，将指定位置之后的元素向前移动一个位置，然后将最后一位设为null，最后返回旧值。当指定的是元素时，就先判断元素的位置，移除那个位置元素，最后返回布尔值。
```java
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;
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 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方法清除list中的元素。将数组中的每个元素设为null，并将大小设为0。
```java
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
```
addAll方法向list中添加集合。不指定位置时，默认向末尾添加集合元素。
```java
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
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);
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;
}
```
removeAll方法移除指定集合中的所有元素，retainAll方法保留指定集合中的所有元素。这两个方法类似，只是逻辑是反的，Java设计者很巧妙的运用了一个boolean类型的参数来区分两种逻辑，以便使同一个方法。在try中的for循环就已经将需要留下的元素放到了数组的前一部分，即w位置之前。注释说contains方法可能会有异常，当异常发生，就将没有遍历到的元素全部留下，这个逻辑我也不太明白。最后将w位置之后的元素设为null，返回布尔值。
```java
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 {
if (r != size) {
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;
}
```
forEach方法可以使用lambda表达对每一个元素进行相同的操作。在操作之前，会先拿到数组修改的次数，然后重新申请一个与list数组元素相同的数组进行操作。注意，此复制是浅复制，两个数组共用一套元素。最后判断list是否被其他操作改变了，如果被改变了就抛出异常。
```java
@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方法移除掉满足参数条件的元素。首先将满足参数条件的元素的位置放到一个set集合中，然后再遍历将其重新整合。
```java
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(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)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
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;
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
```
replaceAll方法对数组的每个元素执行传入方法。
```java
@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++;
}
```
sort方法使用传入的比较方法对数组进行排序。
```java
@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++;
}
```
ArrayList拥有自己的两种迭代器，Itr和ListItr。
Itr实现了接口Iterator，定义了三个变量，cursor，代表下一个元素的位置，lastRet，代表上一个元素的位置，expectedModCount，数组之前的修改次数。
```java
int cursor;
int lastRet = -1;
int expectedModCount = modCount;
```
Itr迭代器有4个方法，hasNext()，next()，remove()，forEachRemaining()。
hasNext方法判断可以向后迭代。
```java
public boolean hasNext() {
return cursor != size;
}
```
next方法返回下一个元素，并将cursor和lastRet向前移动一个位置。
```java
@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];
}
```
remove方法移除掉上一个遍历过的元素，并将cursor指向上一个元素的位置，将lastRet设为-1。
```java
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();
}
}
```
forEachRemaining方法遍历所有剩下的元素。在使用Iterator迭代器使用next方法循环list，如果没有循环完整个list，可以使用该方法循环完整个list。
```java
@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();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
```
ListItr继承了Itr类，实现了接口ListIterator。除了提供了一个构造方法之外，还添加了向前遍历的方法。
ListItr的构造方法可以为迭代器指定开始迭代的位置。
```java
ListItr(int index) {
super();
cursor = index;
}
```
hasPrevious方法判断是否可以向前迭代。
```java
public boolean hasPrevious() {
return cursor != 0;
}
```
nextIndex方法返回下一个迭代元素的位置。
```java
public int nextIndex() {
return cursor;
}
```
previousIndex方法返回前一个迭代元素的位置。
```java
public int previousIndex() {
return cursor - 1;
}
```
previous方法返回前一个迭代的元素。
```java
@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];
}
```
set方法设置上一个遍历过的元素值为e。
```java
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方法向cursor位置添加一个元素，并将cursor指向下一个位置，将lastRet设为-1。
```java
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。
SubList继承AbstractList抽象类，实现RandomAccess接口，有四个属性，在构造方法中可以看出这四个属性的意义。
```java
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
```
parent就是母列表，parentOffset是母列表的偏移，offset是子列表相对于母列表的偏移，size是子列表的大小，同时记录了母列表被修改的次数。
```java
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;
}
```
SubList提供了列表简单的操作 ，set，get，size，add，remove，removeRange，addAll，iterator，listIterator等方法。注意，这些方法虽然在子列表调用的，但是都是直接操作母列表对应位置的元素的。比如set方法，会去修改母列表元素offset+index位置的元素的值。
```java
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;
}
```
ArrayList使用subList方法返回列表的子列表。注意，如果修改子列表的元素，母列表的元素也会被修改。
```java
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
```
最后，ArrayList还有一个内部类ArrayListSpliterator，这个以后再研究吧，目前有些看不懂。