JAVA集合-ArrayList

ArrayList是java集合框架中比较常用的数据结构，其实底层就是一个数组的操作实现，但是这个数组呢可以实现容量大小的动态变化，这就是比较特别的地方吧。另外ArrayList不是线程安全的。

框架结构

从图中可以看出ArrayList类继承了AbstractList类，实现了List、RandomAccess、Serialzable、Cloneable接口

实现RandomAccess接口：可以通过下标序号快速访问

实现了Cloneable，能被克隆

实现了Serializable，支持序列化

成员变量

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; // non-private to simplify nested class access
    private int size;
...
}

• DEFAULT_CAPACITY默认容量是10
• EMPTY_ELEMENTDATA 空集合
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA 默认空集合 （与EMPTY_ELEMENTDATA有点区别，在不同的构造函数中用到），第一个元素添加时会扩容成默认容量10
• elementData真正存放数据的地方
• size 数组元素个数

构造函数

/**
 * 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);
    }
}

指定初始化长度，当然这个初始化容量长度不能小于0，如果等于0，则赋一个空集合EMPTY_ELEMENTDATA。

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

这是最常用的默认构造方法，其中使用默认的初始容量大小10，并赋予一个空数组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) {
    elementData = c.toArray();
    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;
    }
}

使用已有集合来创建ArraList，将集合里的值复制到ArrayList中。首先把集合转换成数组，然后判断转换的数组类型是否为Obejct[]类型，如果是则将数组的值拷贝到list中，否则或者容量为0，则赋予一个空数组

常用的操作

添加操作

public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //扩容之后再添加元素
       elementData[size++] = e;
       return true;
      }


     private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }
    
    //计算容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
         return minCapacity;
    }
    
     private void ensureExplicitCapacity(int minCapacity) {
          modCount++;

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

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新容量为原来容量的二分之三倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //新容量小于需要扩容的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            
        //新容量大于数组能申请的最大值  MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8
        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);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

size表示ArrayList的元素个数。在添加元素之前先要确保数组有足够容量。当当前数组需要的空间不够时，就需要扩容了，并且保证新容量不能比当前需要的容量小，然后调Arrays.copyOf()创建一个新的数组并将数据拷贝到新数组中，且把引用赋值给elementData

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

指定数组index位置添加元素。首先会检查index是否超出数组的范围；然后既然要添加元素，就要保证有足够的数组空间；当然要在index位置插入元素，得让index后所有的元素往后移动一位，腾出index位置设置要添加的元素。

添加元素时，都涉及到了对数组的复制移动，用到了两种方法

Arrays.copyOf(elementData, newCapacity);
System.arraycopy(elementData, index, elementData, index + 1,size - index);

第一个方法是生成一个同样大小的新对象，当然底层也是使用了System.arraycopy方法

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

第二个方法是将数组复制到指定数组中，还可以选择复制数组的长度。使用arraycopy方法 自己复制自己，将数组要放置的地方的对象移到后面去

实质上都是底层clone来的结果

删除操作

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

删除指定位置的元素。首先也是检查index的合法性，然后取得该位置的旧元素，计算需要移动的长度，如果需要移动的，则调用System.arraycopy方法将index位置后的元素所有往前移动一位，将数组最后一位置为null，方便GC工作，最后返回被删除的元素。

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

删除指定元素，这里删除的是数组中第一个找到的元素。fastRemove方法移除，这里没有进行index范围检查

获取操作

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
  }


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

获取指定index位置的元素。这个实现很简单，首先index范围检查，然后直接取数组中index位置元素返回。

修改操作

public E set(int index, E element) {
        rangeCheck(index);

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

修改指定位置的元素，并返回旧值

迭代器

使用集合的都知道，在for循环遍历集合时不可以对集合进行删除操作，因为删除会导致集合大小改变，从而导致数组遍历时数组下标越界，严重时会抛ConcurrentModificationException异常

使用迭代器遍历删除，运行正常

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

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    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);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @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();
    }
}

从代码中可以看出iterator方法返回的是一个Itr()对象。

Itr对象有三个成员变量：

cursor：代表下一个要访问的数组下标
lastRet：代表上一个要访问的数组下标
expectedModCount：代表ArrayList修改次数的期望值，初始为modeCount

Itr有三个主要函数：

hasNext：实现简单，判断下一个要访问的数组下标等于数组大小，表示遍历到最后了
next：首先判断 expectedModCount 和 modCount 是否相等。每调用一次 next 方法， cursor 和 lastRet 都会自增 1。
remove ：首先会判断 lastRet  的值是否小于 0，然后在检查 expectedModCount 和 modCount 是否相等。然后直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素。然后将 lastRet 赋值给 cursor ，将 lastRet 重新赋值为 -1，并将 modCount 重新赋值给 expectedModCount。

remove方法弊端：

调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1

总结

ArrayList是一个可以自动扩容的动态数组。

ArrayList的默认容量大小是10

扩容为原来的1.5倍，如果1.5倍还不够的话，直接扩容成我们所需要的容量，1.5倍或所需容量太大的话，直接扩容成Integer.MAX_VALUE或MAX_ARRAY_SIZE

扩容之后通过数组拷贝确保元素的准确性，尽量减少扩容机制

复制和扩容使用了Arrays.copyOf和System.arraycopy方法

ArrayList查找效率高，插入删除操作效率相对低

size 为集合实际存储元素个数

elementData.length 为数组长度，表示数组可以存储多少个元素

如果需要边遍历边 remove ，必须使用 iterator。且 remove 之前必须先 next，next 之后只能用一次 remove。