ArrayList源码解析

一、ArrayList的定义

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

从ArrayList可以看出它是支持泛型的,它继承自AbstractList,实现List、RandomAccess、Cloneable、java.io.Serializable接口
AbstractList提供了List接口的默认实现(个别方法为抽象方法),List接口定义了列表必须实现的方法
RandomAccess是一个标记接口,接口内没有定义任何内容
实现了Cloneable接口的类,可以调用Object.clone方法返回该对象的浅拷贝
通过实现java.io.Serializable接口以启用其序列化功能,未实现此接口的类将无法使其任何状态序列化或反序列化.序列化接口没有方法和字段,仅用于标识可序列化的语义

二、ArrayList属性

//序列号
private static final long serialVersionUID = 8683452581122892189L;

/**
 * 默认初始化容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 一个空数组:当用户指定该ArrayList容量为0时,返回该空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 一个空数组实例:
 *  当用户没有指定ArrayList的容量时(即调用无参构造函数),返回的是该数组--->刚创建一个ArrayList时,其内数据量为0
 *  当用户第一次添加元素时,该数组(同引用与elementData)将会扩容,变成默认容量为10(DEFAULT_CAPACITY)的一个数组--->通过ensureCapacityInternal() 实现
 *  它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的,而后者是在用户指定容量为0时返回
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * ArrayList基于数组实现:用该数组保存数据,ArrayList的容量就是该数组的长度
 */
transient Object[] elementData;

/**
 * ArrayList实际存储的数据数量
 */
private int size;

1.transient关键字

此处有个关键字需要解释:
Java的serialization提供了一种持久化对象实例的机制.当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它,为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient
transient是Java语言的关键字,用来表示一个域不是该对象串行化的一部分,当一个对象被串行化的时候,transient型变量的值不包括在串行化表示中,然后非transient型的变量是被包括进行的

public class UserInfo implements Serializable {
    private static final long serialVersionUID = -3091184167089157794L;
    private String name;
    private transient String psw;

    public UserInfo(String name, String psw) {
        this.name = name;
        this.psw = psw;
    }

    @Override
    public String toString() {
        return "UserInfo{" +
                "name='" + name + '\'' +
                ", psw='" + psw + '\'' +
                '}';
    }
}
public class TestTransient {
    public static void main(String[] args) {
        UserInfo userInfo = new UserInfo("张三", "123456");
        System.out.println(userInfo);

        try {
            //序列化,被设置为transient属性的没有序列化
            ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("UserInfo.out"));
            oos.writeObject(userInfo);
            oos.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }

        try {
            //重新读取内容
            ObjectInputStream ois = new ObjectInputStream(new FileInputStream("UserInfo.out"));
            UserInfo userInfo1 = (UserInfo) ois.readObject();
            System.out.println(userInfo1.toString()); //发现psw内容为null
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
    }
}

三、ArrayList构造函数

ArrayList提供了三个构造函数

/**
 * 创建一个初始容量/空的ArrayList
 * -可能报错 java.lang.OutOfMemoryError 需要的Array size超过VM限制
 * @param  initialCapacity  初始容量
 * @throws IllegalArgumentException 当初始容量值非法(小于0)时抛出
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 数组缓冲区为EMPTY_ELEMENTDATA,注意与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    }
}

/**
 * 无参构造函数:
 *  初始时创建一个空的ArrayList,此时其内数组缓冲区elementData = {},长度为0
 *  当元素第一次被加入时,扩容至默认容量10
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 创建一个包含collection的ArrayList
 * @param c 要放入ArrayList中的集合,其内元素将会全部添加到新建的ArrayList实例中
 * @throws NullPointerException 当参数c为null时抛出异常
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray(); //集合转Object[]数组
    //将转换后Object[]长度赋值给当前ArrayList的size,并判断是否为0
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // c.toArray可能不会返回Object[],可以查看java官方编号6260652的bug
        if (elementData.getClass() != Object[].class) {
            //若c.toArray可能不会返回Object[],则利用Arrays.copyof()来构造一个大小为size的Object[]数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // replace with empty array.
        //长度为0则换成空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

1.Arrays.copyOf方法

/**
 * 非基本类型copyOf
 * @param original:要复制的数组
 * @param newLength:要返回的副本长度
 * @param newType:要返回的副本的类
 */
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]  
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);  
    System.arraycopy(original, 0, copy, 0,  Math.min(original.length, newLength));  
    return copy;  
}

//基本数据类型  
public static int[] copyOf(int[] original, int newLength) {  
    int[] copy = new int[newLength];  
    System.arraycopy(original, 0, copy, 0,  Math.min(original.length, newLength));  
    return copy;  
}

观察源代码发现copyOf(),在其内部创建了一个新的数组,然后调用arrayCopy()产生新的数组对象返回;总结如下：

copyOf()实现用的是arrayCopy()
arrayCopy()需要目标数组,对两个数组的内容进行可能不完全的合并操作
copyOf()在内部新建一个数组,是用arrayCopy()将oldArray内容复制到newArray中去,并且长度为newLength,返回newArray

2. System.arraycopy()

/**
 * @param src - 源数组
 * @param srcPos - 源数组中的起始位置
 * @param dest - 目标数组
 * @param destPos - 目标数据中的起始位置
 * @param length - 要复制数组的元素数量
 */
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

该方法用了native关键字,调用的是C++编写的底层函数,即JDK中的底层函数
在实际使用中,如果我们能对所需的ArrayList的大小进行判断,有两个好处:

节省内存空间(我们只需放置两个元素到数组—new ArrayList(2))
避免数组扩容引起效率下降(我们只需要放置大约37个元素到数组,new ArrayList(40))

四、ArrayList容量处理

/**
 * 将数组缓冲区大小调整为实际ArrayList存储元素的大小
 * 即elementData = Arrays.copy(elementData, size)
 * 该方法ArrayList没有使用,由用户手动调用,以减少空间资源浪费
 */
public void trimToSize() {
    //modCount 是 AbstractList 的属性值: protected transient int modCount = 0;
    modCount++;

    //当实际大小 < 数组缓冲区大小时(如调用默认构造函数后,刚添加一个元素时,此时elementData.length = 10,而size = 1)
    //通过这一步,可以使得空间得到有效利用,而不会出现资源浪费的情况
    if (size < elementData.length) {
        //注意此处的运算符优先级:先判断后把数组赋给elementData
        //调整数组缓冲区elementData变为实际存储大小
        elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
    }
}

/**
 * 指定ArrayList的容量
 * 此方法提供给用户使用,在ArrayList中并没有使用
 * @param   minCapacity   指定的最小容量
 */
public void ensureCapacity(int minCapacity) {
    //最小扩充容量,默认是10
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
    //若用户指定的最小容量 > 最小扩充容量,则以用户指定的为准,否则还是10
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

/**
 * 私有方法,明确ArrayList的容量,提供给本类使用的方法
 * 用于内部优化,保证空间资源不被浪费,尤其在add()方法添加时起效
 * @param minCapacity 指定的最小容量
 */
private void ensureCapacityInternal(int minCapacity) {
    //若elementData=={}时,则取minCapacity为 默认容量10 和 参数minCapacity 的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

/**
 * 私有方法:明确ArrayList的容量
 * @param minCapacity 指定的最小容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    //将修改统计数+1,该变量主要是用来实现fail-fast机制的
    modCount++;

    // 防止溢出代码:确保指定的最小容量 > 数组缓冲区当前长度
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

/**
 * 数组缓冲区的最大存储容量:
 *  减去8的原因 ---> 一些VM会在一个数组中存储某些数组
 *  尝试分配这个最大存储容量,可能会导致OutOfMemoryError(当值>VM限制时)
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 私有方法:扩容 以确保ArrayList至少能存储minCapacity个元素
 * 扩容计算: newCapacity = oldCapacity + (oldCapacity >> 1)
 * @param minCapacity 指定的最小容量
 */
private void grow(int minCapacity) {
    // 防止溢出代码
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //若newCapacity 依旧小于 minCapacity
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    //若newCapacity 大于 最大存储容量,则进行大容量分配
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 私有方法:大容量分配,最大分配Integer.MAX_VALUE
 * @param minCapacity
 * @return
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

1.modCount解析

首先modCount是从类java.util.AbstractList继承的字段,这个字段主要是为了防止在多线程操作的情况下,List发生结构性的变化
就是防止一个线程正在迭代,另外一个线程进行对List进行remove操作,这样当我们迭代到最后一个元素时,很明显List最后一个元素为空,那么这时modCount就会告诉迭代器,让其抛出异常ConcurrentModificationException
如果没有这一个变量,那么系统会报异常ArrayIndexOutOfBoundsException,这样的异常显然不是应该出现的(这些运行时错误都是使用者的逻辑错误导致的,我们的JDK那么高端,不会出现使用错误,我们只抛出使用者造成的错误,而这个错误是设计者应该考虑的),为了避免出现这样的异常,定义了检查
详见:https://www.zhihu.com/question/24086463/answer/64717159

五、核心函数分析

1.indexOf

/**
 * 顺序查找,返回元素的最低索引值(首先出现的索引位置)
 * @return 存在 ? 最低索引值 : -1
 */
@Override
public int indexOf(Object o) {
    //注意:元素为null不是非法操作,空值也可以作为元素放入ArrayList
    if (o == null) {
        //顺序查找数组缓冲区,注意:Arrays工具类提供了二分搜索,但没有提供顺序查找
        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;
}

2.lastIndexOf

/**
 * 反向查找(从数组末尾向开始查找),返回元素的最高索引值
 * @return 存在 ? 最高索引值 : -1
 */
@Override
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;
}

3.clone

/**
 * 深度复制:对拷贝出来的ArrayList对象操作
 * @return 一个克隆的ArrayList实例
 */
@Override
public Object clone() {
    try {
        //Object克隆方法:会复制对象及其内所有基本类型成员和String类型,但不会复制对象成员、引用对象
        ArrayList<?> v = (ArrayList<?>) super.clone();
        //对需要复制的引用变量,进行独立的拷贝,将存储的元素移入新的ArrayList
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

4.toArray

/**
 * 返回ArrayList的Object数组
 * - 包含ArrayList的所有存储元素
 * - 对返回的该数组进行操作,不会影响该ArrayList(相当于分配了一个新的数组) ==> 该操作是安全的
 * - 元素存储顺序与ArrayList中的一致
 * @return
 */
@Override
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

/**
 * 返回ArrayList元素组成的数组
 * @param a 需要存储list中元素的数组
 * @return 若a.length >= list.size
 *          则将list中的元素按顺序存入a中,然后a[list.size]=null,a[list.size+1]及其之后的元素依旧是a的元素
 *          注意:若a中本类存储有元素,则a会被list的元素覆盖,且a[list.size]=null
 *         否则将返回包含list所有元素且数组长度等于list中元素个数的数组
 * @throws ArrayStoreException 当a.getClass()!=list时,存储元素的类型时
 * @throws NullPointerException 当a为null时
 */
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    // 若数组a的大小 < ArrayList的元素个数,则新建一个数组,
    // 数组大小是ArrayList的元素个数,并将ArrayList全部拷贝到新数组中
    if (a.length < size) {
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    // 若a数组大小 >= ArrayList的元素个数,则将ArrayList全部元素都拷贝到数组a中
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size) {
        a[size] = null;
    }
    return a;
}

5.add方法(重点)

/**
 * 添加新值到list末尾
 * @param e 添加的值
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
@Override
public boolean add(E e) {
    // 确定ArrayList的容量大小(严谨)
    // 注意；size+1 保证资源空间不被浪费,按当前情况,保证存多少元素就只分配多少空间资源
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 添加e到ArrayList中,然后size自增1
    elementData[size++] = e;
    return true;
}

/**
 * 插入方法:命名为insert()比较合理
 * - 在指定位置插入新元素,原先在index位置的值往后移动一位
 * @param index 要插入的位置
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    elementData[index] = element;
    size++;
}

说明:正常情况下会扩容1.5倍,特殊情况下

指定为空数组时为0
新扩展数组大小已经达到了最大值则只取最大值
当我们调用add方法时,实际上的函数调用如下:

说明:程序调用add实际上进行一系列调用,可能会调用grow,grow可能会调用hugeCapacity

5.1无参构造时add运行

1 2	List<Integer> lists = new ArrayList<Integer>(); lists.add(8);

说明:初始化list大小为0,调用ArrayList()型构造函数,那么在调用list.add()方法时是怎样的?

在add方法之前开始elementData = {};调用add方法时会继续调用,直至grow,最后elementData的大小变为10，之后再返回到add函数，把8放在elementData[0]中

5.2有参构造add运行

1 2	List<Integer> lists = new ArrayList<Integer>(6); lists.add(8);

在调用add方法之前,elementData的大小已经为6,之后再进行传递,不会进行扩容处理

6.trimToSize()

/**
 * 将数组缓冲区大小调整为实际ArrayList存储元素的大小
 * 即elementData = Arrays.copy(elementData, size)
 * 该方法由用户手动调用,以减少空间资源浪费
 */
public void trimToSize() {
    //modCount 是 AbstractList 的属性值: protected transient int modCount = 0;
    modCount++;

    //当实际大小 < 数组缓冲区大小时(如调用默认构造函数后,刚添加一个元素时,此时elementData.length = 10,而size = 1)
    //通过这一步,可以使得空间得到有效利用,而不会出现资源浪费的情况
    if (size < elementData.length) {
        //注意此处的运算符优先级:先判断后把数组赋给elementData
        //调整数组缓冲区elementData变为实际存储大小
        elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
    }
}

将ArrayList容量设置为当前size大小,首先需要明确一个概念,ArrayList的size就是ArrayList的元素个数,length是ArrayList申请的内容空间长度.ArrayList每次都会预申请多一点空间,以便添加元素的时候不需要每次都进行扩容操作,例如我们的元素个数是10个,它申请的内存空间必定会大于10,即length>size,而这个方法就是把ArrayList的内存空间设置为size,去除没有用到的null值空间.这也就是我们为什么每次在获取数据长度是都是调用list.size()而不是list.length()

7.removeAll和retainAll(重点)

/**
 * 移除list和c中共有的元素
 * - 若实例化Collection的类不是ArrayList,则删除肯定失败
 * @param c
 * @return {@code true} 若list和c有公有元素,删除成功(list元素个数有改变):没有公有元素,删除失败
 * @throws ClassCastException 当c中元素和list的元素类型不兼容时
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException 当c为null时
 * @see Collection#contains(Object)
 */
@Override
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 只保留list和集合c中公有的元素:和 removeAll()功能相反
 * @param c
 * @return {@code true} list元素个数有改变
 * @throws ClassCastException
 * @throws NullPointerException
 * @see Collection#contains(Object)
 */
@Override
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

在实际开发中removeAll这个动作很耗时,因为在bacthRemove需要循环原来的list,此时还会调用contains方法,而在contains方法中的indexOf方法又会循环一次,即removeAll两层for循环,复杂度O(m*n),所以在操作比较大的ArrayList时这种方法绝对不可取,可以采用下面的方式

private List<Integer> removeAll(List<Integer> src, List<Integer> target) {
	LinkedList<Integer> result = new LinkedList<>(src); //大集合用linkedlist 
 	HashSet<Integer> targetHash = new HashSet<>(target); //小集合用hashset 

 	Iterator<Integer> iter = result.iterator(); //采用Iterator迭代器进行数据的操作  
 	while(iter.hasNext()){  
 		if(targetHash.contains(iter.next())){  
 			iter.remove(); 
 		} 
 	} 
	return result;
}

7.1比较两种removeAll

外层循环
一个是普通的for循环,一个迭代遍历元素,两者相差不大
内层数据比较
前者通过index方法把整个数组遍历了一遍
后者调用HashSet的Contains方法,实际上是调用HashMap的containKey方法,查找时是通过hash表查找,复杂度为O(1)

7.2Hash表简单介绍

Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录关键字进行比较来查找,这个源于Hash表设计的特殊性,它采用函数映射思想将记录的存储位置与记录的关键字关联起来,从而能够快速进行查找,可以简单理解为，以空间换时间，牺牲空间复杂度来换取时间复杂度
hash表采用一个映射函数f:key—>address将关键字映射到该记录在标识的存储位置,从而在想要查找该记录时可以直接根据关键字和映射关系计算出该记录在表中的存储位置,通常情况下这个映射关系称作为hash函数,而通过hash函数合关键字计算出来的存储位置称作为hash地址(这里的存储位置只是表中的存储位置并不是实际的物理地址)

上图是hash表一种实现方式,是由数组+链表组成的,元素放入hash表的位置通过hash(key)%len获得即元素key的哈希值对数组长度取模得到的
另外hash表大小的确定也很关键,如果hash表的空间远远大于最后实际存储的记录个数,则造成了很大的空间浪费,如果选取小了的话则容易造成冲突.在实际情况中一般需要根据最终记录存储个数和关键字的分布特点来确定hash大小,还有一种情况可能事先不知道最终需要存储的记录个数,则需要动态维护hash表的容量,此时可能重新计算hash地址

8.遍历ArrayList的对象iterator

/**
 * 从列表指定位置开始返回列表迭代器(按顺序)
 * @param index 元素的索引位置
 * @throws IndexOutOfBoundsException
 * @return
 */
@Override
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: " + index);
    }
    return new ListItr(index);
}

/**
 * 返回一个ListIterator迭代器,该迭代器是fail-fast机制的
 * @return
 */
@Override
public ListIterator<E> listIterator() {
    return new ListItr(0);
}

/**
 * 返回一个Iterator迭代器,该迭代器是fail-fast机制的
 * @return
 */
@Override
public Iterator<E> iterator() {
    return new Itr();
}

iterator方法是Abstract中实现的,该方法返回AbstractList一个内部类Itr对象

9.subList

/**
 * 获取从fromIndex到toIndex之间的子集合(左闭右开)
 * - 若fromIndex==toIndex,则返回的空集合
 * - 对该子集合操作,会影响原有集合
 * - 当调用了subList()后,若对原有集合进行删除(删除subList中的首个元素)操作,会抛出ConcurrentModificationException
 * - 该子集合支持索引的集合操作
 * 原因看SubList内部类的构造函数即可
 * @param fromIndex
 * @param toIndex
 * @return
 * @throws IndexOutOfBoundsException
 * @throws IllegalArgumentException
 */
@Override
public List<E> subList(int fromIndex, int toIndex) {
    // 合法性检查
    subListRangeCheck(fromIndex, toIndex, size);
    return new ArrayList.SubList(this, 0, fromIndex, toIndex);
}

六、ArrayList的内部类

private class Itr implements Iterator<E>
private class ListItr extends Itr implements ListIterator<E>
private class SubList extends AbstractList<E> implements RandomAccess
static final class ArrayListSpliterator<E> implements Spliterator<E>

1.Itr

Itr实现了Iterator接口,同时重写了里面的hasNext()、next()、remove()、forEachRemaining等方法

/**
 * AbstractList.Itr优化版本
 */
private class Itr implements Iterator<E> {
    int cursor;       // 下一个返回元素的索引,默认值为0
    int lastRet = -1; // 上一个返回元素的索引,若没有上一个元素则为-1.每次调用remove(),lastRet都会重置为-1
    int expectedModCount = modCount;

    @Override
    public boolean hasNext() {
        // 是否有下一个元素的判断
        return cursor != size;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        // 临时变量i,指向游标当前位置
        // 此处并没有让lastRet直接等于cursor进行操作
        int i = cursor;
        // 第一次检查i
        if (i >= size) {
            throw new NoSuchElementException();
        }
        Object[] elementData = ArrayList.this.elementData;
        // 第二次检查i
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        cursor = i + 1;
        // 注意这里的取值
        return (E) elementData[lastRet = i];
    }

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

        try {
            // 移除元素
            ArrayList.this.remove(lastRet);
            // 指针回移
            cursor = lastRet;
            // 注意此处: 上一元素指针重置为-1,因此lastRet不一定等于cursor-1
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * jdk1.8进行函数式编程
     * @param consumer 动作(让集合每一个元素都执行该动作)
     */
    @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++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

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

2.ListItr

继承Itr,实现了ListIterator接口;
重写了hasPrevious()、nextIndex()、previousIndex()、previous()、set(E e)、add(E e)等方法
这也看出了Iterator和ListIterator的区别:

ListIterator有add()方法,可以向List中添加对象,而Iterator不能
ListIterator和Iterator都有hasNext()和next()方法,可以实现顺序向后遍历.但是ListIterator有hasPrevious()和previous()方法,可以实现逆向(顺序向前)遍历.Iterator就不可以
ListIterator可以定位当前的索引位置,nextIndex()和previousIndex()可以实现.Iterator没有此功能
都可实现删除对象,但是ListIterator可以实现对象的修改,set()方法可以实现.Iterator仅能遍历,不能修改.因为ListIterator的这些功能,可以实现对LinkedList等List数据结构的操作

3.SubList

继承AbstractList,实现了RandomAccess接口,类内部实现了对子序列的增删改查等方法,同时也充分利用了内部类的优点,就是共享ArrayList的全局变量,例如检查器变量modCount，数组elementData等，所以SubList进行的增删改查操作都是对ArrayList的数组进行的，并没有创建新的数组

4.ArrayListSpliterator

七、ArrayList源码全解析

八、ArrayList总结

ArrayList基于数组实现,其内存储元素的数组为elementData,elementData声明为transient Object[] elementData;
ArrayList中EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的使用—这两个常量数组的使用场景不同,前者是用户通过ArrayList(int initialCapacity)该构造方法直接指定初试容量为0时,后者是用户直接使用无参构造创建ArrayList时
ArrayList默认容量为10,调用无参构造新建一个ArrayList时,其elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA,当第一次使用add()添加元素时,ArrayList的容量会为10
ArrayList的toArray()方法和subList()方法,在源数据和子数据之间的区别

toArray():对该方法返回的数组,进行操作(增删改查)都不会影响源数据(ArrayList中的elementData).二者是不会相互影响的
subList():对返回的子集合进行操作(增删改查)都会影响父集合.而且若是对父集合中进行删除操作(仅仅在删除子集合的首个元素)时,会抛出异常 ConcurrentModificationException

九、c.toArray的官方bug

public Object[] toArray()返回的类型不一定就是Object[], 其类型取决于其返回的实际类型
原因是我们父类实例的具体类型,实际上是取决于new时的子类类型

1.代码分析

1.1创建类

1
2
3

public class Father {}

public class Son extends Father{}

1.2测试1

@Test
public void test1() {
    Son[] sons = {new Son(), new Son()};
    System.out.println(sons.getClass());// class [Lcom.johnnie.test.Test$Son

    Father[] fathers = sons;
    System.out.println(fathers.getClass());// class [Lcom.johnnie.test.Test$Son

    fathers[0] = new Father();// java.lang.ArrayStoreException
}

对于fathers[0] = new Father(); 这句话,为什么会报错?
报错原因是因为fathers实际类型是Son[],由于数组中元素类型是son类型,因而会出现向下转型异常.也就是说假如我们有1个Object[]数组,并不代表着我们可以将Object对象存进去,这取决于数组中元素实际的类型

1.3测试2

新建一个MyList,该类继承ArrayList

public class MyList<E> extends ArrayList<E> {
    @Override
    public String[] toArray() {
        return new String[]{"1", "2", "3"};
    }
}

测试代码如下:

@Test
public void test2() {
    List<String> ss = new LinkedList<>();
    ss.add("123");
    Object[] objs = ss.toArray();// LinkedList toArray()返回的本身就是Object
    objs[0] = new Object();

    ss = new MyList<>();
    objs = ss.toArray(); 
    System.out.println(objs.getClass()); // class [Ljava.lang.String
    objs[0] = new Object(); // java.lang.ArrayStoreException
}

当我们调用List的toArray()时,我们实际调用的是其具体实现类MyList中重写的String[] toArray()方法.因此数组并不是Object[]而是String[],而向下转型是不安全的,因此会抛出异常
通过分析这个官方bug,我们就记住了:

抽象类(接口)其具体类型,取决于实例化时所采用的导出类的类型
子类实现和父类同名方法,当返回值不一致时,默认调用的是子类的实现方法;如MyList中的String[] toArray