集合（5）——List接口与AbstractList抽象类源码解析

List接口

List是一个有序、可以重复，可以有null元素的集合

类图

官方文档

List成员方法

其中“有序”，指的是存储的时候按照元素的添加顺序进行存储和获取。

• 有序的集合（也成为序列）。该接口的开发人员可以精确的控制列表中每个元素的插入位置。开发人员可以通过索引访问元素，并搜索列表中的元素
• 与Set不同的是，列表通常允许重复的元素。更正式的说，列表通常允许对元素e1和e2存储在列别中，其中e1.equals(e2)。如果实现该接口的类允许存在null元素，那么就允许存在多个null。

AbstractList抽象类

类图

官方文档

public abstract class AbstractList<E>
extends AbstractCollection<E>
implements List<E>

• AbstractList抽象类实现了很多List接口中的方法，减轻了想要实现List接口的开发人员的负担，如果开发人员想要实现List接口，那么他可以直接继承AbstractList类然后重写对应的方法就可以了。如果开发人员想要顺序访问数据（如LinkedList类），那么继承AbstractSequentialList 类比继承AbstractList要更高效
• 如果开发人员想要实现一个不可修改的List，那么只需要继承该类，然后重写两个方法：get(int)和size()方法
• 如果开发人员想要实现一个可修改的List，那么需要重写set()方法，如果不重写会抛出UnsupportedOperationException异常，如果size()的大小是可变的，那么开发人员还需要重写add(int, E)和 remove(int)方法
• 该类的子类需要有2个构造方法，一个是空参，一个是参数类型为Collection的构造方法
• 该类的子类可以不实现iterator方法，因为这个抽象类已经实现了iterator()方法

AbstractList的成员变量

该类只有一个成员变量：该List在结构上已经被修改的次数
protected transient int modCount = 0;

Iterator迭代器和ListIterator迭代器会使用到该变量，如果迭代器的expectModCount与该变量的值不同，那就会抛出ConcurrentModificationException异常，在官方文档中称其为* fail-fast *

AbstractList的成员方法

(1) public boolean add(E e)方法

    public boolean add(E e) {
        add(size(), e);
return true;
    }

源码解析：

• 开发人员如果想要调用这个方法，就一定要重写该方法，否则会抛出UnsupportedOperationException异常
• 该方法体中调用了该类的add(int index, E element)方法
• 支持该操作的List可能会限制能够添加到该列表的元素类型。如一些列表不允许添加null元素，还有一些列表对元素的其他类型有限制。实现该类的子类应该在其文档中清楚地指定要添加什么元素的任何限制。
• 调用该方法可能会产生4种异常
  
  • UnsupportedOperationException ：如果开发人员没有重写该方法，就会抛出该异常
  • ClassCastException ：if the class of the specified element prevents it from being added to this list
  • NullPointerException ：如果该实现类不允许添加Null，而开发人员添加了null
  • IllegalArgumentException ：if some property of this element prevents it from being added to this list

(2) abstract public E get(int index); 抽象类

• 功能：返回具体索引位置的元素
• 调用该方法可能会产生的异常：
  
  • IndexOutOfBoundsException ：index的值 < 0或者超出了size()的大小

(3) public E set(int index, E element)方法

    public E set(int index, E element) {
throw new UnsupportedOperationException();
    }

源码解析：
- 功能：重置index位置的元素的信息
- 开发人员需要重写该方法
- 调用该方法可能会产生5种异常
- UnsupportedOperationException ：如果开发人员没有重写该方法，就会抛出该异常
- ClassCastException ：if the class of the specified element prevents it from being added to this list
- NullPointerException ：如果该实现类不允许添加Null，而开发人员添加了null
- IllegalArgumentException ：if some property of this element prevents it from being added to this list
- IndexOutOfBoundsException ：index的值 < 0或者超出了size()的大小

(4)public void add(int index, E element)方法

    public void add(int index, E element) {
throw new UnsupportedOperationException();
    }

源码解析：

• 功能：在index处插入element元素。将当前元素向后移动一位，如原来list中的元素为{1,2,3,4,5}，现在调用add(0,10)后，list中的元素为{10，1，2，3，4，5}。这点要注意！！！
• 开发人员需要自己实现该方法，否则会抛出UnsupportedOperationException异常
• 调用该方法可能会产生5种异常
  
  • UnsupportedOperationException ：如果开发人员没有重写该方法，就会抛出该异常
  • ClassCastException ：if the class of the specified element prevents it from being added to this list
  • NullPointerException ：如果该实现类不允许添加Null，而开发人员添加了null
  • IllegalArgumentException ：if some property of this element prevents it from being added to this list
  • IndexOutOfBoundsException ：index的值 < 0或者超出了size()的大小

(5) public E remove(int index)方法

    public E remove(int index) {
throw new UnsupportedOperationException();
    }

源码解析：

• 功能：移除index位置的元素，它后面的元素向左移动
• 注意，如果使用Iterator遍历的时候，只能调用iterator的remove方法，否则有fail-fast问题
• 开发人员需要自己实现该方法，否则默认抛出UnsupportedOperationException异常

（6）public int indexOf(Object o)方法

    public int indexOf(Object o) {
        ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
 return it.previousIndex();
        } else {
while (it.hasNext())
if (o.equals(it.next()))
 return it.previousIndex();
        }
 return -1;
    }

源码解析：

• 功能：返回List中第一次出现o元素的位置，如果不存在该元素则返回-1
• 源码思路：
  
  • 这里面将Null和非null通过if语句进行判断。很多源码都是通过这种方法进行判断的，但是我觉得官方文档中提供的方法更简洁，(o==null ? get(i)==null : o.equals(get(i)))。
  • 该方法是通过Iterator进行遍历的，如果找到了就返回，找不到就一直遍历直到list末尾。
  • 注意这里面返回的是previousIndex()。因为，没调用一次it.next()方法，迭代器的游标都会向后移动一位。

(7) public int lastIndexOf(Object o)方法

    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;
    }

源码解析：

• 功能：返回指定元素最后一次出现的位置。如果不存在，返回-1
• 源码思路：
  
  • 使用迭代器进行遍历，但是这里面需要注意，迭代器初始化时使用的是带参数的构造方法，则最开始迭代器处于List的最后。
  • 还是分o是null 和非null进行判断，但是现在判断条件不是hasNext()而变成hasPrevious()

(8)public void clear()方法

    public void clear() {
        removeRange(0, size());
    }

源码解析

• 功能：清除list中的所有元素
• 源码思路：可以看到，该方法是调用removeRange(int fromIndex, int toIndex)方法来实现清除功能
• 注意：开发人员需要重写该方法和removeRange(int fromIndex, int toIndex)方法，否则会抛出UnsupportedOperationException 异常

public boolean addAll(int index, Collection<? extends E> c)方法

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
boolean modified = false;
for (E e : c) {
            add(index++, e);
            modified = true;
        }
return modified;
    }

源码解析:

• 功能：在指定位置添加c元素
• 源码思路：
  
  • 首先要判断指定的位置是否符合list的范围
  • 使用foreach来完成增加元素的操作，在循环体中调用了add(int index, E element)方法，所以想要使用该方法，需要重写add方法，否则会抛出异常。

(9)public List<E> subList(int fromIndex, int toIndex)方法

    public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
    }

源码解析：

• 功能：截取子List
• 源码思路：从源码可以看出，实现该功能，是通过创建RandomAccessSubList类对象，或SubList类对象实现的

(10)public boolean equals(Object o)方法

    public boolean equals(Object o) {
if (o == this)
return true;
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();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
        }
return !(e1.hasNext() || e2.hasNext());
    }

(11) public int hashCode()方法

    public int hashCode() {
int hashCode = 1;
for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
    }

源码解析：

• 功能：返回对象的hashCode码，可以看出List的hashCode码与集合中的所有元素都有关系，是每个元素的hashCode码*31

(12) protected void removeRange(int fromIndex, int toIndex)方法

    protected void removeRange(int fromIndex, int toIndex) {
        ListIterator<E> it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

源码解析：

• 功能：将下标fromIndex到下标toIndex的元素移除
• 源码思路：移除元素是通过迭代器实现的，首先将迭代器的游标置于fromIndex位置，然后通过for循环来实现元素的移除，没次循环，迭代器都向前移动一个位置，然后调用remove()方法删除元素。

(13) private void rangeCheckForAdd(int index)方法

    private void rangeCheckForAdd(int index) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

源码解析：

• 功能：检查插入的元素位置是否超过界限。
• 源码思路：通过if语句判断插入位置，如果插入位置小于0或者大于集合size()，则抛出异常，其中异常的信息调用的是该类的outOfBoundsMsg（）方法。

(14) private String outOfBoundsMsg(int index)方法

    private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size();
    }

源码解析：

• 功能：元素位置超过界限的异常返回信息。