Android ArrayList★_app

1.ArrayList

ArrayList的数据结构：

容量：CAPACITY ；实际大小：size；

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

//存放元素的数组

transient Object[] elementData;

//数组的大小。size代表的是已使用elementData的元素的数量，也即是size()方法的大小

private int size;

2.构造方法

ArrayList的构造方法一共有3个。构造方法就做一件事情，就是初始化一下储存数据的容器，即elementData。

①无参构造方法

//构造一个初始容量为10的空列表

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };

可以看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组，也就是说在JDK1.8中调用无参构造方法时，底层elementData数组是空数组。

如果创建ArrayList对象的时候不传入参数，则使用此无参构造方法创建ArrayList对象。DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object[]，将elementData初始化。空的Object[]会给默认容量10。但是这里我们并没有看到数组的容量变为10啊，那么什么时候会被初始化为10的数组呢？答案是有元素被加入时(add方法)。当进行第一次add的时候，elementData将会变成默认的长度：10。

②参数是容量大小的构造函数

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

}

private static final Object[] EMPTY_ELEMENTDATA = { };

构造一个指定容量为capacity的空ArrayList。这是一个带初始容量大小的有参构造函数。

③参数是collection的构造函数

public ArrayList(Collection c) {

elementData = c.toArray(); //调用toArray()方法把collection转换成数组

if((size = elementData.length) != 0) {

if (elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class);

} else {

this.elementData = EMPTY_ELEMENTDATA;

}

构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。这个有参构造方法构造时赋的值是它的父类Collection对象。

先将collection对象转换成数组，然后将数组的地址赋给elementData。如果数组的实际大小等于0（c中没有元素），将空数组EMPTY_ELEMENTDATA赋值给elementData；如果size的值大于0，则执行Arrays.copy方法，把collection对象的内容copy到elementData中。

3.add方法

add方法有两个，一个是带一个参数的，一个是带两个参数的。

①boolean add(E e) 将指定元素追加到列表的末尾

public boolean add(E e) {

ensureCapacityInternal(size + 1); //确认list容量，如果不够，容量加1。注意：只加1，保证资源不被浪费

elementData[size++] = e;// 将元素e放在size的位置上,并且size++。这个 *** 作相当于 element[size] = e, size++

return true;

}

这个add方法是在list的末尾添加一个元素。size是数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1个容量的数组能否放得下。

//数组容量检查，不够时则进行扩容

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 static final int DEFAULT_CAPACITY = 10;

calculateCapacity方法用来计算容量。判断初始化的elementData是不是空的数组，如果是空数组说明是第一次add，此时一调用add方法，就需要扩容。

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

// minCapacity代表的是本次add *** 作所需要的最小容量， elementData.length代表的是当前元素数组的长度

if (minCapacity - elementData.length > 0)

grow(minCapacity); // 扩容

}

1)如果elementData元素是空的，就是第一次添加元素，minCapacity=size+1，也就是等于1，空的数组没有长度就存放不了，所以就将minCapacity变成10，也就是默认容量的大小。也就是此时elementData数组需要的最小容量变为10了，此时ensureExplicitCapacity()方法中的minCapacity就是10。到此只是说elementData数组需要的容量至少是10，还没有改变elementData的大小。

2)如果elementData数组中的元素不是空的，那么它此时需要的最小容量就是原先的数组长度加1，minCapacity代表着elementData中元素增加之后的实际数据个数。

要始终记住minCapacity = size+1,在ensureExplicitCapacity()方法中，首先 *** 作数自增1，再把需要的最小空间容量与数组当前实际长度进行比较。

接着往下看，ArrayList能自动扩展大小的关键就grow()方法里：

//扩容，保证ArrayList至少能存储minCapacity个元素。第一次扩容逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity

private void grow(int minCapacity) {

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1); //新的容量=当前容量+当前容量/2，即将当前容量扩大1.5倍

//如果扩容后的容量还是小于想要的最小容量，则将扩容后的容量再次扩容为想要的最小容量

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

// 如果扩容后的容量大于最大值（会出现内存不足的情况），则进行大容量分配

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// 新的容量大小已经确定好了，就copy数组，改变容量大小

elementData = Arrays.copyOf(elementData, newCapacity);

}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

hugeCapicaty方法用以当 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;

}

②void add(int index, E element) 将指定元素插入到列表中的指定位置。将当前位于该位置的元素(如果有的话)和随后的任何元素向右移动

public void add(int index, E element) {

rangeCheckForAdd(index);//越界检查

ensureCapacityInternal(size + 1);

// 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素后移一个位置。arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量)

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

//将指定的index位置赋值为element

elementData[index] = element;

size++; //实际容量+1

}

private void rangeCheckForAdd(int index) {

if (index > size || index < 0)//插入的位置不能大于size 和小于0，如果是就报越界异常

throw new IndexOutOfBoundsException( outOfBoundsMsg(index));

}

4.get() 返回list中指定位置的元素

public E get(int index) {

rangeCheck(index);//越界检查

return elementData(index);//返回索引为index的元素

}

//越界检查。检查指定索引是否在范围内。如果不在，抛出一个运行时异常。这个方法不检查索引是否为负数，它总是在数组访问之前立即优先使用，如果给出的索引index>=size，抛出一个越界异常

private void rangeCheck(int index) {

if (index >= size)

throw new IndexOutOfBoundsException( outOfBoundsMsg(index));

}

private String outOfBoundsMsg(int index) {

return "Index: "+index+", Size: "+size;

}

// 位置访问 *** 作，返回索引为index的元素

E elementData(int index) {

return (E) elementData[index];

}

从代码中可以看到，因为ArrayList底层是数组，所以它的get方法非常简单，先是判断一下有没有越界（索引小于0或者大于等于数组实际长度，错误信息返回索引和数组的实际长度），之后就直接通过数组下标来获取元素。

5.set() 用指定的元素替换列表中指定位置的元素

public E set(int index, E element) {

rangeCheck(index); //越界检查

//记录被替换的元素（旧值）

E oldValue = elementData(index);

//替换元素（新值）

elementData[index] = element;

return oldValue; //返回被替换的元素

}

确保set的位置小于当前数组的长度（size）并且大于0，获取指定位置index元素，然后放到oldValue存放，将需要设置的元素放到指定位置index上，最后将原来位置的元素oldValue返回。

6.remove()方法

ArrayList有3个删除方法。

①E remove(int index)

//删除list中位置为指定索引index的元素，索引之后的元素向左移一位

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

// size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值

elementData[--size] = null;

return oldValue; //返回被删除的元素

}

②boolean remove(Object o)

//从列表中删除第一次出现的指定元素。如果列表不包含该元素，将保持不变

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;

}

//私有的remove方法，该方法跳过边界检查，并且不返回已删除的值

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; // 便于GC

}

因为arrayList可以存储null值，所以分了两种情况，循环遍历所有对象，得到对象所在索引位置，然后调用fastRemove方法，执行remove *** 作。在fastRemove中，定位到需要remove的元素索引，先将index后面的元素往前面移动一位（调用System.arraycooy实现），然后将最后一个元素置空。

③ 删除多个元素

从该列表中删除索引位于两者之间的所有元素，包含fromIndex，但是不包含toIndex，并将后面的元素向左移动

protected void removeRange(int fromIndex, int toIndex) {

modCount++;

int numMoved = size - toIndex;//被删除的索引后面的个数

System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

int newSize = size - (toIndex-fromIndex);//新数组的长度

for (int i = newSize; i < size; i++) {

elementData[i] = null;//便于GC

}

size = newSize;

}