ArrayList原理
一、定义
ArrayList是android开发应用最多的一种集合，在处理比较复杂的业务时候，需要遍历来查找数据和操作数据的时候都会考虑用ArrayList去实现。
二、介绍
1，ArrayList的原理跟javaScript类似都是基于数组实现的，这样可以节约空间，众所周知数组是有容量限制，因此它是一个动态数组，超出限制时会自动增加原来的1/2（50%）容量，所以其容量能自动增长，即自动扩容机制，如果可预知数据量的多少，可在构造ArrayList时指定其容量。
2，实现所有可选的列表操作，并允许所有元素，包括null。
3，提供一些方法来操作内部用来存储列表的数组的大小（这类大致相当于载体，但它是不同步的）
三、缺点
非线程安全,只能用在单线程环境下，不能适应数据动态地增减的情况（当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费）。
四、实现方式
1，构造函数
//可以构造一个默认初始容量为10的空列表
public ArrayList() {
this(10);
}
//构造一个指定初始容量的空列表
public ArrayList(int initialCapacity) {
super();
if(initialCapacity <0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData =new Object [initialCapacity];
}
//构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。
public ArrayList(Collection c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
2，储存方式
// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。
public E set(int index, E element) {
RangeCheck(index);
EoldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
// 将指定的元素添加到此列表的尾部。
public boolean add(E e) {
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
// 将指定的元素插入此列表中的指定位置。如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
// 如果数组长度不足，将进行扩容。
ensureCapacity(size+1); // Increments modCount!!
// 将 elementData中从Index位置开始、长度为size-index的元素，
// 拷贝到从下标为index+1位置开始的新的elementData数组中。
// 即将当前位于该位置的元素以及所有后续元素右移一个位置。
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
// 从指定的位置开始，将指定collection中的所有元素插入到此列表中。
public boolean addAll(int index, Collection c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
3， 元素删除：
// 移除此列表中指定索引上的元素。
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
4，元素更改（这一栏本身是不需要的，只不过对数据操作离不开增删改查，所以单独的在列出来）
// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。
public E set(intindex, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;returnoldValue;
}
5，元素读取
// 返回此列表中指定索引上的元素。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
6，调整数据容器
//在实际添加大量元素前，咱们也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
public void ensureCapacity(int minCapacity) {
if(minCapacity > oldCapacity) {
Object oldData[] = elementData;
intnewCapacity = (oldCapacity *3) /2+1;
if(newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
//将底层数组的容量调整为当前列表保存的实际元素的大小的功能。
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
综上两种方法
ensureCapacity方法中elementData的长度会被拓展，size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况，将出现空间的浪费。
trimToSize将返回一个新的数组elementData，元素内容保持不变，length和size相同，节省空间。
