AbstractList
此类提供List接口的基本实现，以最大程度地减少实现支持“随机访问”数据存储（例如数组）所需的工作。对于顺序访问数据（例如链表），应优先使用AbstractSequentialList类。
要实现不可修改的列表，编程者仅需扩展此类并为get和List的size方法提供实现。
要实现可修改的列表，编程者必须另外重写set方法（否则将抛出UnsupportedOperationException）。如果列表是可变大小的，则程序员必须另外重写add和remove方法。
根据Collection接口规范中的建议，编程者通常应提供一个void（无参数）的构造函数。
与其他抽象集合的实现不同，编程者不必提供迭代器实现。迭代器和列表迭代器由此类在“随机访问”方法之上实现：
get、set、add、remove。
此类中每个非抽象方法的文档都详细描述了其实现。如果正在实现的集合允许更有效的实现，则可以覆盖这些方法中的每一个。
该类是Java集合框架的成员。
唯一构造函数。 （用于子类构造函数的调用，通常是隐式的。）
源码如下：
protected AbstractList() {
}
将指定的元素追加到此列表的末尾（可选操作）。
支持此操作的列表可能会限制哪些元素可以添加到此列表。特别是，某些列表将拒绝添加空元素，而另一些列表将对可能添加的元素类型施加限制。列表类应在其文档中明确指定对可以添加哪些元素的所有限制。
该方法的实现调用了add(int index, E element)方法，add(int index, E element)的默认实现是抛出UnsupportedOperationException，所以如果不重写它，那么调用当前方法也会抛出UnsupportedOperationException。
源码如下：
public boolean add(E e) {
add(size(), e);
return true;
}
获取列表在指定索引位置的元素。
在指定的索引位置设置指定的元素，默认实现是抛出UnsupportedOperationException。
源码如下：
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
在指定的索引位置添加指定的元素，默认实现是抛出UnsupportedOperationException。
源码如下：
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
删除指定索引位置的元素，默认实现是抛出UnsupportedOperationException。
源码如下：
public E remove(int index) {
throw new UnsupportedOperationException();
}
此实现首先获取一个列表迭代器（通过listIterator()）。然后，在列表上进行迭代，直到找到指定的元素或到达列表的末尾。
此方法，在通过listIterator()方法获取到列表迭代器后，逐个遍历元素：
如果参数中给定的元素为null则判断next获得的元素是否为null，若是，则返回previousIndex。
如果参数中给定的元素不为null，则通过equals方法判断next获取的元素是否和参数中给定的元素相同，若相同则返回则返回previousIndex。
如果未能找到，则返回-1。
源码如下：
public int indexOf(Object o) {
// 此处获取的是列表迭代器
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
// 此处已调用过next方法，所以一旦命中，需要返回的是previousIndex()
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
return -1;
}
此实现首先获取一个指向列表末尾的列表迭代器（使用listIterator(size())）。然后，向后迭代列表，直到找到指定的元素，或者到达列表的开头。
寻找元素的方法和indexOf方法一致，区别在于，本方法是从后往前找，也就是找的是指定的元素在列表中最后一次出现的位置，没找到则返回-1。
源码如下：
public int lastIndexOf(Object o) {
// 获取一个从列表末尾开始的迭代器
ListIterator<E> it = listIterator(size());
if (o==null) {
while (it.hasPrevious())
if (it.previous()==null)
return it.nextIndex();
} else {
while (it.hasPrevious())
if (o.equals(it.previous()))
return it.nextIndex();
}
return -1;
}
从此列表中删除所有元素（可选操作）。此调用返回后，该列表将为空。
该实现将调用removeRange(0, size())。
请注意，如果未重写remove(int index)或removeRange(int fromIndex, int toIndex)，本方法将抛出UnsupportedOperationException。
源码如下：
public void clear() {
removeRange(0, size());
}
此实现在参数中指定的集合上获得一个迭代器并对其进行迭代，使用add(int, E)将从迭代器获得的元素插入到此列表的适当位置，一次插入一个。
为了提高效率，许多实现将覆盖此方法。
请注意，除非重写add(int, Object)和add(int, E)，否则此实现将抛出UnsupportedOperationException。
源码如下：
public boolean addAll(int index, Collection<? extends E> c) {
// 判断指定的索引是否符合插入位置的范围限制
rangeCheckForAdd(index);
boolean modified = false;
// 调用遍历指定的集合c，将迭代到的每个元素放入当前集合
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
以正确的顺序返回在此列表元素上的迭代器。
此实现依赖于来源列表的size()，get(int)和remove(int)方法来返回迭代器接口的简单实现。
请注意，除非重写列表的remove(int)方法，否则此方法返回的迭代器将在调用其remove方法时抛出UnsupportedOperationException。
如规范中对modCount字段的描述，该实现在面对并发修改时抛出运行时异常。
源码如下：
public Iterator<E> iterator() {
// 返回一个Itr实例
return new Itr();
}
本方法将调用listIterator(final int index)方法，只不过传入的index为0。
源码如下：
public ListIterator<E> listIterator() {
return listIterator(0);
}
此实现返回ListIterator接口的直接实现，该接口继承了iterator()方法所返回的Iterator接口。ListIterator实现依赖于来源列表的get(int)，set(int, E)，add(int, E)和remove(int)方法。
请注意，此实现返回的列表迭代器在调用其remove，set和add方法时抛出UnsupportedOperationException，除非列表的remove(int)，set(int, E)和add(int, E)方法已被重写。
如规范中对modCount字段的描述，该实现在面对并发修改时抛出运行时异常。
源码如下：
public ListIterator<E> listIterator(final int index) {
// 判断index的大小是否符合范围限制
rangeCheckForAdd(index);
// 返回一个从index位置开始的ListItr实例
return new ListItr(index);
}
迭代器在遍历列表时，游标所在位置。也即后续调用next所返回元素的索引。
最近一次调用next或previous返回的元素的索引。如果通过调用remove删除了此元素，则重置为-1。
迭代器认为来源列表应该具有的modCount值。如果违反了此期望，则说明迭代器已检测到并发修改。
判断是否还有其他元素，如果调用next还能获取到元素，则该方法应返回true。
源码如下：
public boolean hasNext() {
// 判断当前游标cursor是否与列表的元素数量相等
return cursor != size();
}
获取下一个元素。
源码如下：
public E next() {
// 检查是否存在并发修改
checkForComodification();
try {
// 将当前游标位置赋值给变量i
int i = cursor;
// 取出当前游标位置的元素，作为next
E next = get(i);
// 设置最近返回的元素索引为i
lastRet = i;
// 游标后移一位，即在当前值基础上加1
cursor = i + 1;
// 返回之前取出的游标位置的元素
return next;
} catch (IndexOutOfBoundsException e) {
// 遇到数组下标越界异常，先检查是否存在并发修改，如不存在，则抛出无此元素异常
checkForComodification();
throw new NoSuchElementException();
}
}
删除当前元素。
源码如下：
public void remove() {
// 如果lastRet小于0，则抛出IllegalStateException
// 这说明要么迭代器初始化好之后还没有调用过next或previous、要么当前元素已被删除了
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 调用列表的remove方法删除lastRet索引位置的元素
AbstractList.this.remove(lastRet);
// 如果lastRet小于游标，则需将游标位置前移1位
if (lastRet < cursor)
cursor--;
// 将lastRet置为-1
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
// 捕获到IndexOutOfBoundsException则说明存在并发修改，抛出ConcurrentModificationException
throw new ConcurrentModificationException();
}
}
该方法旨在检查是否存在并发修改，判断方法即判断expectedModCount是否等于modCount，不等于则说明存在并发修改，则抛出ConcurrentModificationException。
源码如下：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
构造一个列表迭代器，使用给定的参数index作为当前列表迭代器的游标位置。
源码如下：
ListItr(int index) {
cursor = index;
}
判断当前迭代器前面是否还有元素，判断方法是：当前的游标位置cursor是否为0，为0则说明前面已经没有元素了，此时返回false，否则返回true。
源码如下：
public boolean hasPrevious() {
return cursor != 0;
}
获取上一个元素，获取方法为：
使用当前游标位置减1，算出上一个元素的位置，然后取出该位置的元素，同时设置lastRet和游标位置cursor为该位置，然后返回该元素。
源码如下：
public E previous() {
checkForComodification();
try {
// 将当前游标的前一位赋值给变量i
int i = cursor - 1;
// 获取i位置的元素作为返回值
E previous = get(i);
// 将最近返回的索引位置和游标位置均置为i
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
获取下一个元素的索引，获取方法是：直接返回当前游标位置cursor。
源码如下：
public int nextIndex() {
return cursor;
}
获取上一个元素的索引，获取方法是：返回当前游标位置cursor-1。
源码如下：
public int previousIndex() {
return cursor-1;
}
设置当前位置（lastRet位置）的元素为参数中给定的元素，也即替换最后一次调用next或previous方法得到的元素。
首先，判断lastRet是否小于0，小于0说明其还未调用过next或previous或者调用过remove方法已将当前位置的元素删掉或使用add方法添加了元素，如果小于0，则抛出IllegalStateException。然后检查是否存在并发修改，调用AbstractList的set方法进行赋值。
源码如下：
public void set(E e) {
// lastRet小于0说明其还未调用过next或previous
// 或者调用过remove方法已将当前位置的元素删掉
// 或者使用add方法添加了元素
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 使用列表的set方法进行元素的替换
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
首先检查是否存在并发修改，然后在调用AbstractList的add方法在当前游标位置添加给定的元素。然后，将lastRet置为-1，同时将当前游标位置cursor加1。
源码如下：
public void add(E e) {
checkForComodification();
try {
// 将当前游标的值赋给变量i
int i = cursor;
// 调用列表的add方法将指定的元素e插入到列表的i位置处
AbstractList.this.add(i, e);
// 设定最近返回的索引位置为-1
lastRet = -1;
// 设定当前游标位置加1
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
此实现返回一个AbstractList的子类的列表。子类在私有字段中存储来源列表中子列表的偏移量、子列表的大小（可以在其生存期内更改）以及来源列表的预期modCount值。子类有两种变体，其中一种实现RandomAccess。如果此列表实现RandomAccess，则返回的列表将是实现RandomAccess的子类的实例。
子类的set(int, E)，get(int)，add(int, E)，remove(int)，addAll(int, Collection)和removeRange(int, int)方法都在对索引进行边界检查并调整了偏移量之后，委派给了抽象列表上的相应方法。 addAll(Collection c)方法仅返回addAll(size, c)。
listIterator(int)方法在来源列表的列表迭代器上返回“包装对象”，该列表迭代器是使用来源列表上的相应方法创建的。iterator方法仅返回listIterator()，而size方法仅返回子类的size字段。
所有方法首先检查来源列表的实际modCount是否等于其期望值，如果不是，则抛出ConcurrentModificationException。
源码如下：
public List<E> subList(int fromIndex, int toIndex) {
// 判断当前列表是否是RandomAccess的实例
// 若是，则返回一个RandomAccessSubList实例，否则返回SubList实例
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
比较指定对象与此列表是否相等。当且仅当指定对象也是一个列表，并且两个列表具有相同的大小，并且两个列表中所有对应的元素对都相等时，才返回true。 （如果(e1==null ? e2==null : e1.equals(e2))，则两个元素e1和e2是相等。）换句话说，如果两个列表包含相同顺序的相同元素，则定义为相等。
此实现首先检查指定的对象是否是此列表。如果是，则返回true，如果不是，则检查指定对象是否为列表。如果不是列表，则返回false，如果是列表，则遍历两个列表，比较对应的元素对。如果有任何比较返回false，则此方法返回false。如果一个迭代器在另一个迭代器之前用尽了元素，则返回false（因为列表的长度不相等），否则，当迭代完成时，它将返回true。
源码如下：
public boolean equals(Object o) {
// 指定对象等于当前列表则直接返回true
if (o == this)
return true;
// 指定对象不是List接口的实例则直接返回false
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
// 同时遍历两个列表
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
// 如果发现存在一个元素不匹配，则返回false
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
// 如果上面结束遍历，但仍有一个集合还有未迭代到的元素，则返回false
return !(e1.hasNext() || e2.hasNext());
}
返回该列表的hash值。
此实现完全使用List中hashCode方法的文档中定义列表哈希函数的代码。
源码如下：
public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
从此列表中删除所有索引在fromIndex和toIndex（不含）之间的所有元素。将所有后续元素向左移动（减少其索引）。此调用通过删除toIndex-fromIndex元素来缩短列表。 （如果toIndex == fromIndex，则此操作无效。）
此列表及其子列表上的clear操作调用此方法。重写此方法以利用列表实现的内部功能可以大大地改善此列表及其子列表上的clear操作的性能。
此实现获取位于fromIndex之前位置的列表迭代器，并反复调用ListIterator.next，然后依次调用ListIterator.remove，直到删除了整个范围的元素。 注意：如果ListIterator.remove需要线性时间，则此实现需要平方时间。
源码如下：
protected void removeRange(int fromIndex, int toIndex) {
// 获取从fromIndex位置的列表迭代器
ListIterator<E> it = listIterator(fromIndex);
// 使用toIndex - fromIndex计算出要删除元素的个数，然后遍历，逐个删除元素
for (int i=0, n=toIndex-fromIndex; i<n; i++) {
it.next();
it.remove();
}
}
此列表已被结构上修改的次数。结构上修改是指更改列表大小或以其他方式干扰列表的方式，即正在进行的迭代可能会产生错误的结果。
此字段被iterator和listIterator方法返回的迭代器和列表迭代器的实现所使用。如果此字段的值意外更改，则迭代器（或列表迭代器）将抛出ConcurrentModificationException以响应next，remove，previous，set或add操作。面对迭代期间的并发修改，提供了“快速失败”机制，而不是不确定的行为。
子类对此字段的使用是可选的。如果子类希望提供“快速失败”的迭代器（和列表迭代器），则只需在其add和remove方法（以及它覆盖的所有其他会对列表进行结构修改的方法）。一次调用add或remove应只对此字段加1，否则迭代器（和列表迭代器）将误抛出ConcurrentModificationExceptions。如果实现不希望提供“快速失败”的迭代器，则可以忽略此字段。
添加元素到列表之前对要添加元素的位置进行校验，校验方式为：参数中指定的index是否小于0或者大于size()，若是则抛出IndexOutOfBoundsException。
源码如下：
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
获取一个数组越界的提示信息。
源码如下：
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size();
}
AbstractList可以截取自身的一截，以SubList的形式返回，SubList也支持增删改查，它持有它的父列表，并提供增删查改操作，所以增删改也会影响到其父列表。
它更像是其父列表的代理人，对该子列表的任何增删改，它都是通过其父列表的增删改来实现的。
当前SubList实例的父列表（也即当前实例基于的那个列表）。
基于父列表的索引偏移量，用于定位当前列表的位置。
当前列表的大小。
构造方法，构造一个SubList实例。
源码如下：
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
// 先进行校验
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
// 再执行各个属性的初始化
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
替换指定索引位置的元素。
源码如下：
public E set(int index, E element) {
// 指定索引的合法性检查
rangeCheck(index);
// 检查是否存在并发修改
checkForComodification();
// 调用负列表的set方法进行元素的替换，父列表对应的索引位置为：当前指定的索引 + 偏移量
return l.set(index+offset, element);
}
获取指定索引位置的元素。
源码如下：
public E get(int index) {
// 与set方法相同的套路，索引范围检查、并发检查、通过父列表获取指定位置的元素
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}
获取当前列表的大小。
源码如下：
public int size() {
// 先调用checkForComodification进行并发修改检查，再返回size
checkForComodification();
return size;
}
在指定的索引位置插入指定元素。
源码如下：
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
// 使用父列表的add方法添加元素
l.add(index+offset, element);
// 同步修改次数
this.modCount = l.modCount;
size++;
}
删除指定索引位置的元素。
源码如下：
public E remove(int index) {
rangeCheck(index);
checkForComodification();
// 使用父列表的remove方法删除指定元素
E result = l.remove(index+offset);
this.modCount = l.modCount;
size--;
return result;
}
删除指定索引范围内的元素。
源码如下：
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
// 使用父列表的removeRange方法删除元素
l.removeRange(fromIndex+offset, toIndex+offset);
this.modCount = l.modCount;
size -= (toIndex-fromIndex);
}
将指定集合内的元素添加到当前列表的末尾。
源码如下：
public boolean addAll(Collection<? extends E> c) {
// 当前列表的末尾并非一定是父列表的末尾，所以此处调用自己的addAll方法将元素插入到本列表末尾（即索引位置为size处）
return addAll(size, c);
}
将指定集合内的元素添加到当前列表的指定位置。
源码如下：
public boolean addAll(int index, Collection<? extends E> c) {
// 对指定的索引位置index的合法性做检查
rangeCheckForAdd(index);
// 指定集合的大小为0，则直接返回false
int cSize = c.size();
if (cSize==0)
return false;
// 并发修改检查
checkForComodification();
// 调用父类的addAll方法添加指定集合的元素
l.addAll(offset+index, c);
this.modCount = l.modCount;
size += cSize;
return true;
}
获取一个迭代器，调用父列表的listIterator。
源码如下：
public Iterator<E> iterator() {
// 调用父列表的listIterator()方法
return listIterator();
}
获取一个从指定索引位置开始的列表迭代器。
源码如下：
public ListIterator<E> listIterator(final int index) {
// 进行并发修改检查
checkForComodification();
// 指定索引的合法性检查
rangeCheckForAdd(index);
// 返回一个实现ListIterator的匿名内部类，首先其持有的也是父类的列表迭代器
// 只是进行操作的时候会加上偏移量
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() {
return previousIndex() >= 0;
}
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() {
return i.nextIndex() - offset;
}
public int previousIndex() {
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
SubList.this.modCount = l.modCount;
size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
SubList.this.modCount = l.modCount;
size++;
}
};
}
返回一个当前类的实例，新实例基于当前子列表。
源码如下：
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
范围检查，检查指定的索引是否会造成数组下标越界。
源码如下：
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
新插入元素前对元素插入位置的校验，与rangeCheck类似，不同的是：rangeCheck校验的是index是否小于0或大于等于size，而rangeCheckForAdd校验的是index是否小于0或大于size，因为新增的时候可以在index为size的位置插入元素（也即在列表的末尾插入元素）。
源码如下：
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
整理索引越界时的提示信息，"Index: "+index+", Size: "+size。
源码如下：
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
判断是否存在并发修改，判断依据是，当前列表的更新量modCount和其父列表的更新量modCount是否一致，不一致则抛出ConcurrentModificationException。
源码如下：
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
该类是一个随机访问的子列表。
构造方法，调用父类SubList的构造方法。
源码如下：
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
返回一个基于当前列表的新RandomAccessSubList实例。
源码如下：
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}