ArrayList源码解析

arrayList就是动态数组，可以动态的添加和减少元组，实现了ICollection和Ilist接口以及灵活的设置数组的大小。

5. 遍历集合

通过ArrayList的接口实现树，可以看到ArrayList实现了Iterable接口。

public interface Iterable<T> {

    //返回迭代器
    Iterator<T> iterator();
	// 对每个元素执行操作
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
	//创建拆分器
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

在该接口中需要实现的方法一个就是返回迭代器。迭代器的接口如下：

public interface Iterator<E> {
   
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

5.1 Itr

也就是说，如果需要实现Iterable接口的方法，就必须定义一个Iterator实例，所以在ArrayList类中该方法的实现如下：

public Iterator<E> iterator() {
    return new Itr();
}

该方法返回了itr对象，这个类是ArraysList的内部类，实现了Iterator接口，重写了接口方法的一些默认实现（内部数组，索引）：

private class Itr implements Iterator<E> {
    int cursor;       // 游标，下一个要返回的元素的索引
    int lastRet = -1; // 返回的最后一个元素的索引；如果没有返回-1；
    int expectedModCount = modCount;//用于保证元素迭代的时候不能进行添加和删除操作

    Itr() {}//无参构造器

    public boolean hasNext() {
        return cursor != size;//通过下一个要返回元素的索引是否是集合的大小来确认是否又下一个元素
    }

    @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];//在返回的同时，更新索引。
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);//调用ArrayList的remove方法
            cursor = lastRet;//游标指向删除元素的位置，本来是lastRet+1，这里删除一个，然后游标就不变了
            lastRet = -1;//遍历的最后一个元素不存在了，所以变成了-1；
            expectedModCount = modCount;//因为触发了修改和更新操作，所以要更新该参数。有点像CAS锁的意思
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    //用于进行forEach循环
    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();
    }
    
	//添加和删除元素的时候，可以看到modcount++,也就是说不能在元素迭代的时候进行添加和删除操作，作为内部类巧妙的使用外部类的参数。
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

总体来看，迭代器的相关方法都是基于内部数组和索引来写的，其中使用modCount标记就完成了对元素迭代的时候进行添加和删除操作的限制，所以当在元素迭代的时候进行remove操作的时候，应该使用迭代器的Remove方法，这样不会报错。

迭代器还有一种变种，是foreach循环。这其实是一种语法糖，在编译后还是使用了迭代器来实现。

5.2 ListItr

对于ArrayList还存在一种迭代器，可以实现比itr更多的功能，如下方法可以获得listIterator实例。

public ListIterator<E> listIterator() {
        return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
}

可以看到ListItr继承了Itr并实现了ListIterator接口，ListIterator所提供的模板如下：

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

    @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];//返回上一个元素的值
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);//调用外部集合的方法
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    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();
        }
    }
}

这里基本就能得到ListIterator实例或者Iterator实例的实现，基本就是依靠集合自身的内部数组和方法进行操作，在这个基础之上通过维护索引来实现Iterator的一些特性和游标。

6. 一些其他方法

1. Sublist方法

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

首先先检查对应的索引是否合法。

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}

返回一个内部类Sublist类，该类是集合的视图，也就是说对Sublist类中出来的集合进行修改或者新增操作，那么原始集合也会发生同样的操作。

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

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

2. trimToSize方法

该方法用于回收多余的内存，一旦确定了集合不再添加多余的元素之后，调用该方法会将集合的内部数组调整到集合元素的大小。

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = //三目运算符
          (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);//调用到最后是一个本地方法
    }
}

3. size和isEmpty

size的简单使用

public int size() {
    return size;
}

public boolean isEmpty() {
    return size == 0;
}