Java集合框架（三）：ArrayList

概要：

    ArrayList继承自AbstractList,并且实现了接口List,RandomAccess,Cloneable, java.io.Serializable。其内部通过一个对象数组Object[] elementData保存数据，该对象通过transient关键字修饰，访问权限是default。故此ArrayList内部数据无法序列化，并且其内容同个包内部都可以直接访问。通过私有变量size保存当前元素个数，即ArrayList大小。
    此外还提供几个私有静态常量。如下：

//初始化的ArrayList容量大小
private static final int DEFAULT_CAPACITY = 10;
//创建ArrayList是，默认是一个空ArrayList而不是null，这个变量是为了优化ArrayList空实例时，避免产生过多的不必要的空数组。
private static final Object[] EMPTY_ELEMENTDATA = {};
//确保无参构成函数创建的实例在添加第一个元素时，最小的容量是默认大小10。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//
private static final long serialVersionUID = 8683452581122892189L;

    ArrayList内部是通过Object数组方式保存数据，size保存当前大小。但是存在默认构造函数，当调用该函数的时候，会产生一个默认大小的空ArrayList。这样会存在很多不必要的空数组，影响性能，ArrayList内部定义了几个静态常量空数组，用来应对空数组的共享，避免产生过多的空数组，从而提高性能。

ArrayList内部定义了四个内部类：ArrayListSpliterator、Itr、Listltr、SubList

主要方法说明；

    

构造方法：

    ArrayList提供了3个构造方法，分别是无参数的默认构造方法，接收其他Collection对象的参数方法，以及指定ArrayList大小参数的方法。

public ArrayList():

    默认构造方法，这个方法构造的ArrayList，是一个空的ArrayList，内部共享DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
</br>

public ArrayList(int initialCapacity):

    这个构造器可以指定一个默认的容量参数，如果initialCapacity大于0，则再堆里面申请对应大小的Object数组；如果为0，则和默认构造方法一样，如果是小于零，则抛出异常IllegalArgumentException（非法参数异常)。
</br>

public ArrayList(Collection<? extends E> c):

    这个构造器，可以把E子类类型的Collection对象赋值给ArrayList的方式创建一个新的ArrayList。新ArrayList大小和参数c大小一致，内存拷贝到一个新的内存空间。
</br></br>

添加元素方法：

    ArrayList提供了5个添加元素的方法。

public boolean add(E e):

    往队列尾添加元素，其内部调用另外一个方法

private void add(E e, Object[] elementData, int s)

进行数据添加操作。
</br>

private void add(E e, Object[] elementData, int s):

    这是一个帮助函数，其存在目的是为了减少add(E e)字节码大小，从而可以被C1-编译器作为内联函数展开，从而循环调用add。外部参考。
</br>

public void add(int index, E element):

    在特定的索引位置，插入特定的元素。如果存在对应的元素在该索引位置之后，则需要把这部分元素往后平移位置。
</br>

public boolean addAll(Collection<? extend E> c):

    把c的Collection对象所有元素都添加ArrayList尾部，如果内存空间不足，则会自动扩容，再添加；操作成功，返回true；操作失败返回false，比如c长度为0。
</br>

public boolean addAll(int index, Collection<? extend E> c)：

    在指定索引index，位置插入c的元素，索引右边的元素依次往后平移。次操作要是当前容量不够，则会自动扩容。操作成功返回true。操作失败返回false, 比如c长度为0.

删除元素：

public boolean retainAll(Collection<?> c)
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end)

    retainAll是batchRemove外壳，该函数是把c以外的其他元素都删除。
</br>

public E remove(int index):

</br>

public boolean remove(Object o):

</br>

public boolean removeAll(Collection<?> c):

</br>

public boolean removeIf(Predicate<? super E> filter):

</br>

public boolean removeIf(Predicate<? super E> filter, int i , final int end):

</br>

protected void removeRange(int from Index, int toIndex):

</br>

public void clear():

</br>

元素访问；

元素遍历：

    ArrayList内部是通过数组方式存储数据，其遍历方式可以直接通过数组下标的方式进行遍历也可以通过ArrayList提供的迭代器方式进行遍历。下面分别对两种方式进行描述：

2.4.1.1 下标方式：

import java.util.ArrayList;
public class TestSCanArrayList1 {
    public static void main(String[] args){
        List<String> al = new ArrayList<String>();
        //添加三个元素
        al.add("one");
        al.add("two");
        al.add("three");
        //遍历
        for(int i = 0; i < al.size(); ++i) {
            System.out.println(al.get(i));
        }
    }
}

    以上demo代码，首先调用add方法添加3个元素，然后通过size()方法获取数组大小，在for循环内部，通过get()方法，依次访问对应索引的元素个数，逐一遍历。

迭代器方式：

import java.util.ArrayList;
public class TestSCanArrayList2 {
    public static void main(String[] args){
        List<String> al = new ArrayList<String>();
        //添加三个元素
        al.add("one");
        al.add("two");
        al.add("three");
        //遍历
        //定义一个迭代器
        Iterator iter = al.iterator();
        while(iter.hasNext()) {
            System.out.println(iter.next());
        }

        //迭代器方式二：
        for(String item: al){
          System.out.println(item);
        }
    }
}

    以上demo代码，使用迭代器的方式进行遍历。代码中第一次遍历是通过显示定义和调用迭代器方法；第二次是隐式调用，for-each循环，编译器自动调用迭代器进行元素遍历。

ArrayList内部迭代器类：

    2.4.1.2节中迭代器方式进行遍历，是通过ArrayList内部定义的迭代器类，进行实现。下面直接通过代码分析的方式进行迭代器的功能分析：

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

/**
 * An optimized version of AbstractList.Itr
 * AbstractList.Iter的优化版本。
 */
private class Itr implements Iterator<E> {
    int cursor;       // 指向下一个元素的位置，每次next返回的元素如果是i,则cursor是i+1
    int lastRet = -1; // next返回的元素索引位置，-1表示空，
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    //显示定义无参数的构造方法，防止编译器自动生成构造方法
    Itr() {}

    //判断是否还有下一个元素，cursor 从1开始，如果cursor不等于size表示还有元素
    public boolean hasNext() {
        return cursor != size;
    }

    //返回当前位置的下一个元素
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();//检查ArrayList是否产生变化，以防未定义的情况出现
        int i = cursor; //把cursor赋值给i,cursor就是本次需要返回的元素，
        if (i >= size)//i已经是大于等于ArrayList大小，则表示没有元素了
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;//把ArrayList对象数组赋值给临时数组变量elementData，其目的是想使用数组的length属性
        if (i >= elementData.length)//i大于等于elementData.length，表示数组已经变化了。
            throw new ConcurrentModificationException();
        cursor = i + 1;//更新cursor，+1是指向下一个元素
        return (E) elementData[lastRet = i];//先把i赋值给lastRet，在把elementData[lastRet]位置上的值返回，这里还进行了强制类型转换为E。
    }

    //删除一个元素，具体删除的那个元素，依赖于迭代器的当前状态。
    //ArrayList非线程安全，所以只能单线程环境下使用。
    //迭代器是通过iterator()方法获取，该方法内部每次都是new 一个对象.
    public void remove() {
        //lastRet小于0，这个代码其实就是说明remove函数调用有前提条件，
        //它必须是调用next()以后才能调用。
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);//删除上次next()返回的元素
            cursor = lastRet;//cursor原来是指向lastRet+1, cursor往前移1个位置，因为删除一个元素以后，该位置右边的所有元素都往前平移了。其索引都相应减1.
            lastRet = -1; //lastRet赋值-1， 其目的是防止多次调用remove引起不确定行为
            expectedModCount = modCount;//手工更新ArrayList变更次数。
            /*
             * 只是修改lastRet为-1，这样防止了重复remove调用，
             * cursor往前移1个位置，是让迭代器在删除了元素后，依然能正确使用。
             */
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i < size) {
            final Object[] es = elementData;
            if (i >= es.length)
                throw new ConcurrentModificationException();
            for (; i < size && modCount == expectedModCount; i++)
                action.accept(elementAt(es, i));
            // update once at end to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

    通过以上代码分析可以得知，迭代器内部其实就是通过索引的方式进行迭代数据，和先获取size然后通过get方法本质上不会差别太大，而且性能上还不如get方式。另外remove方法只能是next()方法返回的元素，而且只能连续调用1次。remove一个元素以后，会引起其他元素的位置平移。