java源码-ArrayList-白红宇

开篇

ArrayList主要由如下特性：

ArrayList实际上是通过一个数组去保存数据的，当我们构造ArrayList时，如果使用默认构造函数，ArrayList的默认容量大小是10。

当ArrayList容量不足以容纳全部元素时，ArrayList会自动扩张容量，新的容量 = 1.5*原始容量。

ArrayList的克隆函数，将全部元素克隆到一个数组中，采用Arrays.copyOf方法实现。

ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写出“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

在做ArrayList的遍历的时候有3中遍历的方法，分别是随机访问遍历，用迭代器遍历和强制for循环遍历，按照效率来说最快的是随机访问遍历，最差的是迭代器遍历。

ArrayList的遍历是不安全的，在遍历的时候如果改变了集合的结构会抛出ConcurrentModificationException异常。

ArrayList类图

ArrayList类定义

ArrayList的类定义比较简单，基本上可以看出来默认值数组大小为10，数据存储通过elementData变量。

public class ArrayList
     
       extends AbstractList
      
               implements List
       
        , 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 = {};    //默认是package-private access，保存数据    transient Object[] elementData;     //实际保存的数据量大小    private int size;}

ArrayList构造函数

ArrayList的构造数非常简单，根据传入的参数initialCapacity初始化数组大小。如果不传参数就默认构建空数组。

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);        }    }    public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }    public ArrayList(Collection
      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;        }    }

ArrayList常用操作

ArrayList的add操作

ArrayList的add操作其实就是分两步走：

以size+1的大小去看下是否容纳的下新元素，否则就以1.5的原有空间扩容。

在扩容后的新数组的index位置插入新元素。

grow()方法内部实现扩容和旧元素的拷贝，采用Arrays.copyOf(elementData, newCapacity)实现。

public boolean add(E e) {        ensureCapacityInternal(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;    }    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++;    }    private void ensureCapacityInternal(int minCapacity) {        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);        }        ensureExplicitCapacity(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;        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);    }

ArrayList的remove操作

ArrayList的remove操作分两步走：

将待移除的index往后的元素拷贝至index开始的位置。

将最后一位元素置null并且size-1即可。
ArrayList的clear操作负责将数组全部置null即可。

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

ArrayList迭代器

ArrayList的迭代器实现很简单，通过创建Itr对象。在Itr类当中将cursor初始化为0，next过程中就是返回变量同时将cursor+1，hasNext()方法只是判断cursor是否等于size的值。

public Iterator
     
       iterator() {        return new Itr();    }    private class Itr implements Iterator
      
        {        int cursor;       // 默认初始化值为0        int lastRet = -1; // 上一个返回值的下标        int expectedModCount = modCount;        public boolean hasNext() {            return cursor != size;        }        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];        }    }

开篇