ArrayList

ArrayList概述

ArrayList是可以动态增长和缩减的索引序列，它是基于数组实现的List类。

该类封装了一个动态再分配的Object[]数组，每一个类对象都有一个capacity【容量】属性，表示它们所封装的Object[]数组的长度，当向ArrayList中添加元素时，该属性值会自动增加。如果想 ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以减少增加重分配的次数提高性能。

ArrayList的用法和Vector向类似，但是Vector是一个较老的集合，具有很多缺点，不建议使用。

另外，ArrayList和Vector的区别是：ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性，而Vector则是线程安全的。

ArrayList和Collection的关系：

ArrayList的数据结构

分析一个类的时候，数据结构往往是它的灵魂所在，理解底层的数据结构其实就理解了该类的实现思 路，具体的实现细节再具体分析。

ArrayList的数据结构是：

说明：底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对 ArrayList类的实例的所有的操作底层都是基于数组的。

ArrayList源码分析

1、继承结构和层次关系

IDEA快捷键：Ctrl+H

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

我们看一下ArrayList的继承结构：

ArrayList extends AbstractList AbstractList extends AbstractCollection

所有类都继承Object 所以ArrayList的继承结构就是上图这样。

【分析】

为什么要先继承AbstractList，而让AbstractList先实现List？而不是让ArrayList直接实现List？

这里是有一个思想，接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList是实现接口中一些通用的方法，而具体的类，如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己在实现一些自己特有的方法，这样一来，让代码更简洁，就继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码。所以一般看到 一个类上面还有一个抽象类，应该就是这个作用。

ArrayList实现了哪些接口？

List接口：我们会出现这样一个疑问，在查看了ArrayList的父类 AbstractList也实现了List接口，那为什么子类ArrayList还是去实现一遍呢？

这是想不通的地方，查资料显示，有的人说是为了查看代码方便，使观看者一目了然，说法不 一，但每一个让我感觉合理的，但是在stackOverFlow中找到了答案，这里其实很有趣。

开发这个collection 的作者Josh说：

这其实是一个mistake[失误]，因为他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。

RandomAccess接口：这个是一个标记性接口，通过查看api文档，它的作用就是用来快速随机存取， 有关效率的问题，在实现了该接口的话，那么使用普通的for循环来遍历，性能更高，例如ArrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。所以这个标记性只是为了 让我们知道我们用什么样的方式去获取数据性能更好。

Cloneable接口：实现了该接口，就可以使用Object.Clone()方法了。

Serializable接口：实现该序列化接口，表明该类可以被序列化，什么是序列化？简单的说，就是能够 从类变成字节流传输，然后还能从字节流变成原来的类。

2、类中的属性

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
    // 版本号
    private static final long serialVersionUID = 8683452581122892189L;
    // 缺省容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空对象数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 缺省空对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 元素数组
    transient Object[] elementData;
    // 实际元素大小，默认为0
    private int size;
    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

3、构造方法

无参构造方法

/*
    Constructs an empty list with an initial capacity of ten.
    这里就说明了默认会给10的大小，所以说一开始arrayList的容量是10.
*/
//ArrayList中储存数据的其实就是一个数组，这个数组就是elementData.
public ArrayList() {
    super(); //调用父类中的无参构造方法，父类中的是个空的构造方法
    this.elementData = EMPTY_ELEMENTDATA;
    //EMPTY_ELEMENTDATA：是个空的Object[]， 将elementData初始化，elementData也是个Object[]类型。空的Object[]会给默认大小10，等会会解释什么时候赋值的。
}

有参构造方法1

/*
Constructs an empty list with the specified initial capacity.
构造具有指定初始容量的空列表。

@param initialCapacity the initial capacity of the list
初始容量列表的初始容量

@throws IllegalArgumentException if the specified initial capacity is negative
如果指定的初始容量为负，则为IllegalArgumentException
*/

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //将自定义的容量大小当成初始化 initialCapacity 的大小
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; //等同于无参构造方法
    } else {
        //判断如果自定义大小的容量小于0，则报下面这个非法数据异常
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

有参构造方法 2

/*
    Constructs a list containing the elements of the specified collection,in the order they are returned by the collection's iterator.
    按照集合迭代器返回元素的顺序构造包含指定集合的元素的列表。
    @param c the collection whose elements are to be placed into this list
    @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray(); //转换为数组
    //每个集合的toarray()的实现方法不一样，所以需要判断一下，如果不是Object[].class类型，那么久需要使用ArrayList中的方法去改造一下。
    if ((size = elementData.length) != 0) {
   		 // c.toArray might (incorrectly) not return Object[] (see 6260652)
   		 if (elementData.getClass() != Object[].class)
    		 elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
    	this.elementData = EMPTY_ELEMENTDATA;
    }
}

这个构造方法不常用，举个例子就能明白什么意思

举个例子： Strudent exends Person ， ArrayList、 Person这里就是泛型 ， 我还有一个Collection、 由于这个Student继承了Person，那么根据这个构造方法，我就可以把这个Collection转换为ArrayList ， 这就是这个构造方法的作用 。

【总结】ArrayList的构造方法就做一件事情，就是初始化一下储存数据的容器，其实本质上就是一个数 组，在其中就叫elementData。

4、核心方法-add

alt+7 查看方法列表，ctrl+左键 选中add进去后查看

boolean add(E)

/**
* Appends the specified element to the end of this list.
* 添加一个特定的元素到list的末尾。
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
    //确定内部容量是否够了，size是数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1的这个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e; //在数据中正确的位置上放上元素e，并且size++
    return true;
}

【分析：ensureCapacityInternal(xxx); 确定内部容量的方法】

private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity){
    //看，判断初始化的elementData是不是空的数组，也就是没有长度
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //因为如果是空的话，minCapacity=size+1；其实就是等于1，空的数组没有长度就存放不了，所以就将minCapacity变成10，也就是默认大小，但是在这里，还没有真正的初始化这个elementData的大小。
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //确认实际的容量，上面只是将minCapacity=10，这个方法就是真正的判断elementData是否够用
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //  overflow-conscious code
    //minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不够用，不够用那么就要增加elementData的length。这里有的同学就会模糊minCapacity到底是什么呢，这里给你们分析一下
    /*
    第一种情况：由于elementData初始化时是空的数组，那么第一次add的时候，minCapacity=size+1；也就minCapacity=1，在上一个方法(确定内部容量ensureCapacityInternal)就会判断出是空的数组，就会给将minCapacity=10，到这一步为止，还没有改变elementData的大小。
    
	第二种情况：elementData不是空的数组了，那么在add的时候，minCapacity=size+1；也就是minCapacity代表着elementData中增加之后的实际数据个数，拿着它判断elementData的length是否够用，如果length不够用，那么肯定要扩大容量，不然增加的这个元素就会溢出。
*/
    if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}
//arrayList核心的方法，能扩展数组大小的真正秘密。
private void grow(int minCapacity) {
    // overflow-conscious code
    
    //将扩充前的elementData大小给oldCapacity
    int oldCapacity = elementData.length;
    
    //newCapacity就是1.5倍的oldCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //这句话就是适应于elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，所以这个判断成立，在这里就是真正的初始化elementData的大小了，就是为10.前面的工作都是准备工作。
    if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
    
    //如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是将能给的最大值给newCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //新的容量大小已经确定好了，就copy数组，改变容量大小咯。
    elementData = Arrays.copyOf(elementData, newCapacity);
}
    

//这个就是上面用到的方法，很简单，就是用来赋最大值
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    
//如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用minCapacity来判断了。

//Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE：2147483639 也就是说最大也就能给到第一个数值。还是超过了这个限制，就要溢出了。相当于arraylist给了两层防护。    
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

    

void add(int，E)

public void add(int index, E element) {
    //检查index也就是插入的位置是否合理。
    rangeCheckForAdd(index);
    
    ensureCapacityInternal(size + 1); // Increments modCount!!
    
    //这个方法就是用来在插入元素之后，要将index之后的元素都往后移一位，
    System.arraycopy(elementData, index, elementData, index + 1,
    					size - index);
    
    //在目标位置上存放元素
    elementData[index] = element;
    size++;
}

【分析：rangeCheckForAdd(index)】

private void rangeCheckForAdd(int index) {
    //插入的位置肯定不能大于size 和小于0
    if (index > size || index < 0)
        //如果是，就报这个越界异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

【System.arraycopy(...)：就是将elementData在插入位置后的所有元素，往后面移一位】

public static void arraycopy(Object src,
            int srcPos,
            Object dest,
            int destPos,
            int length)

    //src：源对象
    //srcPos：源对象对象的起始位置
    //dest：目标对象
    //destPost：目标对象的起始位置
    //length：从起始位置往后复制的长度。
  

注释解读：

这段的大概意思就是解释这个方法的用法，复制src到dest，复制的位置是从src的srcPost开始，到srcPost+length-1的位置结束，复制到destPost上，从destPost开始到destPost+length-1的位置上

告诉你复制的一种情况，如果A和B是一样的，那么先将A复制到临时数组C，然后通过C复制到B，用了一个第三方参数

这一大段，就是来说明会出现的一些问题，NullPointerException和IndexOutOfBoundsException 还有ArrayStoreException 这三个异常出现的原因。

这里描述了一种特殊的情况，就是当A的长度大于B的长度的时候，会复制一部分，而不是完全失败。

这些是参数列表的解释和异常

😱读别人源码是件很头疼的事，新手会用就行，原理等以后回来复习的时候再看~

【总结】

正常情况下会扩容1.5倍，特殊情况下（新扩展数组大小已经达到了最大值）则只取最大值。

当我们调用add方法时，实际上的函数调用如下：

说明：程序调用add，实际上还会进行一系列调用，可能会调用到grow，grow可能会调用hugeCapacity。

【举例】

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

说明：初始化lists大小为0，调用的ArrayList()型构造函数，那么在调用lists.add(8)方法时，会经过怎样 的步骤呢？下图给出了该程序执行过程和最初与最后的elementData的大小。

说明：我们可以看到，在add方法之前开始elementData = {}；调用add方法时会继续调用，直至 grow，最后elementData的大小变为10，之后再返回到add函数，把8放在elementData[0]中。

【举例说明二】

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

说明：调用的ArrayList(int)型构造函数，那么elementData被初始化为大小为6的Object数组，在调用add(8)方法时，具体的步骤如下：

说明：我们可以知道，在调用add方法之前，elementData的大小已经为6，之后再进行传递，不会进行 扩容处理。

推荐文章系列： 【集合框架】JDK1.8源码分析之HashMap（一） (opens new window)

5、核心方法-remove

其实这几个删除方法都是类似的。我们选择几个讲，其中fastRemove(int)方法是private的，是提供给 remove(Object)这个方法用的。

remove(int)：通过删除指定位置上的元素

public E remove(int index) {
    rangeCheck(index);//检查index的合理性
    
    modCount++;//这个作用很多，比如用来检测快速失败的一种标志。
    E oldValue = elementData(index);//通过索引直接找到该元素
    
    int numMoved = size - index - 1;//计算要移动的位数。
    if (numMoved > 0)
    	//这个方法也已经解释过了，就是用来移动元素的。
    	System.arraycopy(elementData, index+1, elementData, index,numMoved);
    //将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
    elementData[--size] = null; // clear to let GC do its work
    //返回删除的元素。
    return oldValue;
}

remove(Object)：这个方法可以看出来，arrayList是可以存放null值

//通过元素来删除该元素，就依次遍历，如果有这个元素，就将该元素的索引传给fastRemobe(index)，使用这个方法来删除该元素，
//fastRemove(index)方法的内部跟remove(index)的实现几乎一样，这里最主要是知道arrayList可以存储null值
public boolean remove(Object o) {
    if (o == null) {
    	for (int index = 0; index < size; index++)
        	if (elementData[index] == null) {
                fastRemove(index);
                return true;
    		}
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

clear()：将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉，所以叫clear

public void clear() {
    modCount++;
    
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
    	elementData[i] = null;
    size = 0;
}

removeAll(collection c)

public boolean removeAll(Collection<?> c) {
	return batchRemove(c, false);//批量删除
}

batchRemove(xx,xx)：用于两个方法，一个removeAll()：它只清楚指定集合中的元素，retainAll() 用来测试两个集合是否有交集。

//这个方法，用于两处地方，如果complement为false，则用于removeAll如果为true，则给retainAll()用，retainAll（）是用来检测两个集合是否有交集的。

private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData; //将原集合，记名为A
        int r = 0, w = 0;  //r用来控制循环，w是记录有多少个交集
        boolean modified = false;
        try {
            for (; r < size; r++)
                //参数中的集合C一次检测集合A中的元素是否有，
                if (c.contains(elementData[r]) == complement)
                    //有的话，就给集合A
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            //如果contains方法使用过程报异常
            if (r != size) {
                //将剩下的元素都赋值给集合A，
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                //这里有两个用途，在removeAll()时，w一直为0，就直接跟clear一样，全是为null。
                //retainAll()：没有一个交集返回true，有交集但不全交也返回true，而两个集合相等的时候，返回false，所以不能根据返回值来确认两个集合是否有交集，而是通过原集合的大小是否发生改变来判断，如果原集合中还有元素，则代表有交集，而元集合没有元素了，说明两个集合没有交集。

                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

总结：remove函数，用户移除指定下标的元素，此时会把指定下标到数组末尾的元素向前移动一个单 位，并且会把数组最后一个元素设置为null，这样是为了方便之后将整个数组不被使用时，会被GC，可 以作为小的技巧使用。

6、其他方法

set()方法

说明：设定指定下标索引的元素值

public E set(int index, E element) {
    // 检验索引是否合法
    rangeCheck(index);
    // 旧值
    E oldValue = elementData(index);
    // 赋新值
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

indexOf()方法

说明：从头开始查找与指定元素相等的元素，注意，是可以查找null元素的，意味着ArrayList中可以存放null元素的。与此函数对应的lastIndexOf，表示从尾部开始查找。

// 从首开始查找数组里面是否存在指定元素
public int indexOf(Object o) {
    if (o == null) { // 查找的元素为空
        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;
}

get()方法

public E get(int index) {
    // 检验索引是否合法
    rangeCheck(index);
    return elementData(index);
}

说明：get函数会检查索引值是否合法（只检查是否大于size，而没有检查是否小于0），值得注意的 是，在get函数中存在element函数，element函数用于返回具体的元素，具体函数如下：

E elementData(int index) {
	return (E) elementData[index];
}

说明：返回的值都经过了向下转型（Object -> E），这些是对我们应用程序屏蔽的小细节。

ArrayList实践

问题：我们现在有4只小狗，我们如何存储它的信息，获取总数，并能够逐条打印狗狗信息！

分析：通过List 接口的实现类ArrayList 实现该需求。

• 元素个数不确定
• 要求获得元素的实际个数
• 按照存储顺序获取并打印元素信息

class Dog {
    private String name;
    //构造。。。set、get、。。。toString（）
}

public class TestArrayList {
    public static void main(String[] args) {
        //创建ArrayList对象 , 并存储狗狗
        List dogs = new ArrayList();
        
        dogs.add(new Dog("小狗一号"));
        dogs.add(new Dog("小狗二号"));
        dogs.add(new Dog("小狗三号"));
        dogs.add(2,new Dog("小狗四号"));// 添加到指定位置
        
        // .size() ： ArrayList大小
        System.out.println("共计有" + dogs.size() + "条狗狗。");
        System.out.println("分别是：");
        
        // .get(i) ： 逐个获取个元素
        for (int i = 0; i < dogs.size(); i++) {
            Dog dog = (Dog) dogs.get(i);
            System.out.println(dog.getName());
        }
    }
}

问题联想：

• 删除第一个狗狗 ：remove（index）
• 删除指定位置的狗狗 ：remove（object）
• 判断集合中是否包含指定狗狗 ： contains（object）

分析：使用List接口提供的remove()、contains()方法

【常用方法】

总结

1）arrayList可以存放null。 2）arrayList本质上就是一个elementData数组。 3）arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。 4）arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。 5）arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很 多，有移动很多数据才能达到应有的效果 6）arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环。