Android Arraylist源码分析

本版本基于android-19 sdk源码分析
本文章只分析android 中的arraylist源码.如果想看java中arraylist源码，请移步。
Arraylist的原理实现为数组，LinkedLIst的原理实现为链表。
数组的优点为查询快，添加删除慢。
链表的优点为添加删除快，查询慢。

Arraylist 构造方法：

Arraylist 有三个构造方法分别是：

    public static final Object[] OBJECT = new Object[0];
    public ArrayList() {
        array = EmptyArray.OBJECT;
    }

此方法给arraylist创建了一个长度为0的数组对象

    public ArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity < 0: " + capacity);
        }
        array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
    }

此方法会判断传入的值是否小于0，如果小于0则抛出异常。
如果传入的值为0，则就像间接的调用了无参构造方法，为array赋值了一个长度为0的数组对象。
如果传入的值>0,则为array 创建一个指定长度大小的数组。

    public ArrayList(Collection<? extends E> collection) {
        if (collection == null) {
            throw new NullPointerException("collection == null");
        }

        Object[] a = collection.toArray();
        if (a.getClass() != Object[].class) {
            Object[] newArray = new Object[a.length];
            System.arraycopy(a, 0, newArray, 0, a.length);
            a = newArray;
        }
        array = a;
        size = a.length;
    }

此方法会传入一个Collection对象，当传入对象为空，会抛出空指针异常。
当不为空，会通过collection.toArray()方法获取一个数组对象。
如果当前对象不是Object数组，需要创建一个大小长度为collection.toArray()的Object数组，并把collection.toArray()中数据copy到新的Object数组中。并把新数组赋值给array，size设置为数组长度。

/**
     * The number of elements in this list.
     */
    int size;

在看add和remove方法前先说一个值，这个值就是arraylist的size值，这个值我理解为当前列表中元素的数量

Add方法：

1. 普通插入方法

    @Override 
    public boolean add(E object) {
        Object[] a = array;
        int s = size;
        if (s == a.length) {
            Object[] newArray = new Object[s +  
            (s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)];
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        a[s] = object;
        size = s + 1;
        modCount++;
        return true;
    }

先获取记录的Object数组对象，和当前数组长度。
当现在数组对象大小和当前列表中元素数量相等时，需要进行扩容。
举个栗子：

• 当前数组是0时，s=0，a.length=0，这时候就走进了if里面。
  (s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1) ，0<12/2, 那就创建了一个数组大小为0+12的新数组对象。把以前的数据拷贝到了新的数组对象中。数组的大小完成的扩容。
• 当前数组为12时，s=12,a.length=0,会进入if，(s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)，12<12,创建了一个数组大小为12+6的新的数组对象，并把以前的数据拷贝到了新的数据对象中，完成了扩容。
  s >> n 右移一个位，在原来的基础上除2的n次方。
  s << n 左移一个位，在原来的基础上乘2的n次方。

扩容完成过后，把当前对象赋值给a[s]，size加一。

2. 在指定位置加入对象

 @Override public void add(int index, E object) {
        Object[] a = array;
        int s = size;
        //如果当前传入值大于当前列表中元素数量，或者小于0抛出异常
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }
        //如果列表中元素数量 小于数组长度，不需要扩容
        if (s < a.length) {
            //index位置到-一个元素都后移一个位置
            System.arraycopy(a, index, a, index + 1, s - index);
        } else {
            //当列表中元素数量大于等于数组长度，需要扩容，创建一个新的数组对象。
            // assert s == a.length;
            Object[] newArray = new Object[newCapacity(s)];
            //先把原来数组从0-index拷贝到新数组
            System.arraycopy(a, 0, newArray, 0, index);
            //再把index-最后一个元素拷贝到新数组
            System.arraycopy(a, index, newArray, index + 1, s - index);
            //把新的数组赋值给array
            array = a = newArray;
        }
        //给第index个位置赋值object
        a[index] = object;
        size = s + 1;
        modCount++;
    }

变换图如下：

image.png

Remove方法：

• 根据下标移除

 @Override
    public E remove(int index) {
        Object[] a = array;
        int s = size;
        //如果删除长度大于等于当前列表中元素的数量，抛出异常
        if (index >= s) {
            throwIndexOutOfBoundsException(index, s);
        }
        //获取到第index个数组元素对象
        @SuppressWarnings("unchecked")
        E result = (E) a[index];
        //把a数组的index+1到最后一个元素，拷贝到a数组的从index开始位置。并且s-1
        System.arraycopy(a, index + 1, a, index, --s - index);
        a[s] = null;  // Prevent memory leak
        size = s;
        modCount++;
        return result;
    }

• 根据对象移除
  这里只分析object不为空的情况，因为原理一样。

  @Override
    public boolean remove(Object object) {
        Object[] a = array;
        int s = size;
        for (int i = 0; i < s; i++) {
            //当数组中存在此obj
            if (object.equals(a[i])) {
                //把a数组的i+1到最后一个元素，拷贝到a数组的从i开始位置。并且s-1
                System.arraycopy(a, i + 1, a, i, --s - i);
                //将最后一个元素置为空
                a[s] = null;  // Prevent memory leak
                size = s;
                modCount++;
                return true;
            }
        }
        return false;
    }

变换图如下：

image.png

大家可以看看CopyOnWriteArrayList这个类是否可以满足上述需求！实现原理是什么呢？