聊聊 ArrayList

前言

JDK 版本 1.8

ArrayList 是 Java 集合框架中 List 接口的一个实现类，出现于 JDK1.2，是比较常用的 List 实现类之一。

很多文章上面都说：在创建的时候会创建一个容量为 10 的数组。

这是错的，没有指定版本就是耍流氓！！！

什么是 ArrayList ？

翻译过来就是：数组列表

在 Java 看来 ArrayList 是一个类。，这个类是 Java 集合框架的成员，是 List 接口的一个实现类，是一个可变数组的实现，是一个非线程安全的集合。

特点

动态性：ArrayList 可以在运行时动态地分配和释放内存，具有很高的灵活请和可伸缩性
有序性：可以通过数组访问
连续性：ArrayList 的元素在内存中是连续存储的，可以直接通过索引进行访问
线程不安全：ArrayList 是线程不安全的，因为元素的插入和删除操作是保证顺序的
可重复添加数据：内部是基于数组实现的，数组各个元素互不干扰

继承关系

ArrayList 的关系图

Iterable：是”可迭代的“的意思。允许对象成为”每次循环“语句的目标，作用是为当前对象提供 for-each 循环的支持
Collection：集合层次结构的根接口
AbstractCollection：提供了集合接口的骨架实现
List：有序集合（序列）。这个接口的实现对象中对每个元素都有精确的控制，可以通过其整数索引（列表中的位置）访问元素，并搜索列表中的元素
AbstractList：主要是提供了一个 List 接口的默认实现，以及为 List 接口的一些方法提供了默认的实现
Serializable：标识当前类的对象可以被序列化
Cloneable：用于标记当前类可以进行克隆操作，但是让需要调用 Object.clone() 方法进行浅拷贝
RandomAccess：标记当前类支持快速（通常是常量时间）随机访问。也就是遍历方式

// RandomAccess
for(int i=0,n=list.size();i<n; i++)
    list.get(i);

// 上面的比下面的块
for(Iterator i=list.iterator();i.hasNext();)
    i.next();

使用

ArrayList 在 rt 包下面的 java.util 里面，所以第一步先引入：

import java.util.ArrayList;

在使用的时候一半会使用 List 进行接收，也是间接的体现了 Java 的多态，所以还需要引入 List：

import java.util.List;

引入成功后就可以进行创建 ArrayList 对象了：

List list=new ArrayList();

没错这样就创建好了一个简简单单的 ArrayList 对象。
但是在 ArrayList 类里面还可以看到 <E>
这个东西，这个东西就是泛型，也就是说，当使用这个对象的时候需要指定操作的目标对象类型，不然就会使用默认的 Object
，因此修改后的创建方式长这样：

List<String> list=new ArrayList<>();

上面的创建方式就是指定操作对象为 String 对象，当操作其它对象的时候如果不转换类型就会报错，当然也可以指定其它类型：

List<Integer> integerList=new ArrayList<>();
List<Double> doubleList=new ArrayList<>();
List<Short> shortList=new ArrayList<>();
List<Object> objectList=new ArrayList<>(); // 如果没有指定类型，最终效果和此相似

简单操作-增删改查

以泛型为：String 为例：

增加

List<String> list=new ArrayList<>();
list.add("111");
list.add("222");
list.add("111");
System.out.println(list);

// 结果：[111, 222, 111]

删除

list.remove(1); // 删除指定位置元素，返回值：指定位置的元素
list.remove("111"); // 删除第一个出现的指定元素，返回值：包含指定元素并且成功删除为 true 否则 false
list.clear(); // 删除所有元素

修改

list.set(1,"2"); // 用指定元素替换列表中指定位置的元素，返回值：指定位置原始元素

查询

list.get(1); // 返回列表中指定位置的元素

源码学习

构造方法

/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */
private static final Object[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={
    };

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */
transient Object[]elementData; // non-private to simplify nested class access

/** * Constructs an empty list with an initial capacity of ten. */
public ArrayList(){
    
    this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/** * The size of the ArrayList (the number of elements it contains). * * @serial */
private int size;

从源码无参构造的注释上可以看到：构造一个空列表，初始容量为 10。

size 则是 ArrayList 的大小，即拥有元素的个数。

ArrayList 的无参构造方法中只有一行简简单单的复制语句，只是将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
的空数组复制给了 elementData 并没有任何的创建容量为 10 的操作。那么在哪里创建的呐

创建容量为 10 的数组

在创建对象的时候

上面在创建 ArrayList 的时候使用了无参构造创建的，那么有没有其它的构造方法那？

答案肯定是有的：

/** * 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 */
public ArrayList(int initialCapacity) {
    
    if (initialCapacity > 0) {
    
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
    
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
    
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/** * Constructs an empty list with an initial capacity of ten. */
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. * * @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) {
    
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
    
        if (c.getClass() == ArrayList.class) {
    
            elementData = a;
        } else {
    
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
    
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

先看第一个：public ArrayList(int initialCapacity)

当入参 initialCapacity 的值大于 0 的时候会创建大小为 initialCapacity 的数组，当入参为 0
的时候才会使用默认的值创建大小为零的数组（这里的数组大小同样为零），当入参小于零的时候则会抛出异常。

在添加操作的时候

先看源码：

/** * Appends the specified element to the end of this 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) {
    
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

将指定元素添加到列表的末尾。

这里面一共就是两行有效代价，第二行就是从 elementData 中取出元素了，那么重点就在第一行，只是一个渐渐单单方法调用，那么就看一下吧：

/** * Default initial capacity. */
private static final int DEFAULT_CAPACITY = 10;

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
    return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
        
private void ensureCapacityInternal(int minCapacity) {
    
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
private void grow(int minCapacity) {
    
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
    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);
}
        
/** * Appends the specified element to the end of this 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) {
    
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

不要慌，一步一步的分析：

先走 ensureCapacityInternal(size + 1); 调用私有方法传入参数 size + 1
在上面“构造方法”中已经有相关代码，int 类型默认是 0

进入 ensureCapacityInternal 方法里面得到入参：minCapacity 的值为：1

紧接着进入 calculateCapacity 方法里面获得两个入参：elementData 为空的数组，minCapacity
为参数 minCapacity 的值：1

判断入参 elementData 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
的地址是否相等（在创建对象的时候就是使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 进行赋值的）

相等就返回 DEFAULT_CAPACITY 和 minCapacity 的最大值，目前而言就是 DEFAULT_CAPACITY
也就是10（就是这里确定的初始化大小），不相等则返回 minCapacity 一般是自定义的

返回结果 DEFAULT_CAPACITY 默认 10 后紧接着进入 ensureExplicitCapacity 方法

得到入参 10，先对数组大小进行标记

判断当前数组是否有剩余位置用于存储元素

进入 grow 方法得到入参：minCapacity 10

获取当前数组存储元素个数于字段：oldCapacity 中

获取当前数组元素个数的 1.5 倍数值于字段：newCapacity 中

判断翻倍后的数组存储个数和入参的大小，如果入参大，则将入参赋值给 newCapacity 字段

在判断 newCapacity 和 MAX_ARRAY_SIZE 的大小，获取较小的值（MAX_ARRAY_SIZE 为数组的最大存储大小）

进行新数组的拷贝重新赋值给：elementData

对新的元素进行赋值，并且 size 的值进行自增

返回 true

add 方法至此结束。

增加

看看上面的吧，貌似刚写过。

删除

`list.remove(int index);`

删除指定位置元素，返回值：指定位置的元素

先看看源码吧：

@SuppressWarnings("unchecked")
E elementData(int index) {
    
    return (E) elementData[index];
}
            
/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */
public E remove(int index){
    
    rangeCheck(index);

    modCount++;
    E oldValue=elementData(index);

    int numMoved=size-index-1;
    if(numMoved>0)
    System.arraycopy(elementData,index+1,elementData,index,
    numMoved);
    elementData[--size]=null; // clear to let GC do its work

    return oldValue;
}

/** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. */
private void rangeCheck(int index) {
    
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

解释：

进入 ArrayList 的 public E remove(int index) 方法，入参为指定的位置序号

进入 rangeCheck 方法，得到入参：index 索引

判断指定索引是否在当前元素索引范围内，如果没有则抛出运行时异常，否则结束

参数：modCount 自增 1 （修改计数器）

进入 elementData 方法，得到入参：index 索引

从 elementData 中取出索引对应的元素并类型转换为指定类型赋值给：oldValue

计算需要将数组往前移动的元素个数

判断待移动个数是否大于零

大于零进行数组的拷贝：从 index+1 开始拷贝 numMoved 个

将指定位置的元素指向 null 等待 GC 取回收

返回 oldValue 的值，也就是删除的值

`list.remove(Object o);`

/** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */
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;
}

/* * Private remove method that skips bounds checking and does not * return the value removed. */
private void fastRemove(int index) {
    
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
    numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

解释：

进入 ArrayList 的 public E remove(Object o) 方法，入参为待删除的元素

进行判断，如果入参为：null 循环变量整个数组找出元素为 null 的元素

调用 fastRemove 方法得到入参为元素下标

修改计数器自增 1

计算需要将数组往前移动的元素个数

判断待移动个数是否大于零

大于零进行数组的拷贝：从 index+1 开始拷贝 numMoved 个

将指定位置的元素指向 null 等待 GC 取回收

返回 true

否则

入参不为空，循环变量整个数组找出元素为入参的元素

调用 fastRemove 方法得到入参为元素下标

和上述一样的流程

返回 true

返回 false

`list.clear();`

/** * Removes all of the elements from this list. The list will * be empty after this call returns. */
public void clear() {
    
    modCount++;

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

    size = 0;
}

这个简单啊，不就是将整个数组循环遍历，每个狗指向 null 等待 GC 回收。

修改

`list.set(int index, E element);`

// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
    
    return (E) elementData[index];
}
            
/** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */
public E set(int index, E element) {
    
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

/** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. */
private void rangeCheck(int index) {
    
    if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

进入 ArrayList 的 set 方法，得到入参：index 替换元素的索引，element 替换的元素

进入 rangeCheck 方法，得到入参：index 索引

判断指定索引是否在当前元素索引范围内，如果没有则抛出运行时异常，否则结束

进入 elementData 方法

得到入参：index 索引

从 elementData 中取出索引对应的元素并类型转换为指定类型赋值给：oldValue

将指定数组元素指向入参元素

返回指定位置元素的旧值：oldValue

查询

`list.get(int index);`

@SuppressWarnings("unchecked")
E elementData(int index) {
    
    return (E) elementData[index];
}
            
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */
public E get(int index) {
    
    rangeCheck(index);

    return elementData(index);
}

/** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. */
private void rangeCheck(int index) {
    
    if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

进入 ArrayList 的 get 方法，得到入参：index 获取元素的索引

进入 rangeCheck 方法，得到入参：index 索引

判断指定索引是否在当前元素索引范围内，如果没有则抛出运行时异常，否则结束

进入 elementData 方法

得到入参：index 索引

从 elementData 中取出索引对应的元素并类型转换为指定类型作为返回值

常用方法

`list.size()`

获取列表中元素的个数。

就是 ArrayList 里面私有参数 size 的 get 方法

`list.isEmpty()`

判断当前数组当中有没有元素。

ArrayList 里面私有参数 size 是否等于零

`list.contains(Object o)`

判断当前列表是否包含指定元素

/** * Returns <tt>true</tt> if this list contains the specified element. * More formally, returns <tt>true</tt> if and only if this list contains * at least one element <tt>e</tt> such that * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>. * * @param o element whose presence in this list is to be tested * @return <tt>true</tt> if this list contains the specified element */
public boolean contains(Object o) {
    
    return indexOf(o) >= 0;
}

/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index <tt>i</tt> such that * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>, * or -1 if there is no such index. */
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;
}

循环遍历当前列表，找出和指定元素相等的下标，返回这个数组元素的下标是否大于等于零

`list.toArray()`

使用 Arrays.copyOf 拷贝当前数组

特殊方法

`System.arraycopy`

public static native void arraycopy(Object src,   // 源数组
                                    int  srcPos,  // 复制源数组的起始位置
                                    Object dest,  // 目的数组
                                    int destPos,  // 放置目的数组的起始位置
                                    int length);  // 需要复制的长度