1.ArrayList有那些特性
每个元素有自己索引值，元素可重复，元素可为null，
基于数组实现，可自动进行扩容
非线程安全
2.ArrayList有那些常用操作
最长见的操作有增删改查和遍历，因为ArrayList是基于数组实现的，所以会结合元素索引进行增删改查，这里就要注意检查传入值的合法性，如果操作一个不存在的索引就会引发数组越界，所以操作前必须进行索引检查。
- boolean add(E e)
添加一个元素到List尾部,一般在创建时会初始化一个默认长度的数组，jdk1.7中默认创建一个长度为0的数组，在add方法中进行扩容，默认数组长度是10，当添加第11个元素时数组会进行第二次扩容，每次扩大至原数组的1.5倍，扩容的实质就是创建一个更大的数组，再将原数组的内容复制到新数组中，原数组会被GC垃圾回收，数组最大容量为Integer.MAX_VALUE(2^31-1)，超过最大容量，就会报数组越界异常，这个方法最重要的是扩容方法如何写。
- void add(int index, E element)
在指定的索引位置插入指定元素，这里传入索引值，先要判断索引是否越界，然后再判断是否需要扩容，在指定索引处插入元素，需要将该索引后面的元素全部后移一位，将指定值设置到指定索引，这个方法最重要的是中间插入元素，索引后的元素移位，最后组成一个新数组。从这里可以看出指定索引插元素的性能肯定比添加元素到末尾差，因为它每次都会创建新数组。
- E remove(int index)
首先检查索引是否越界，删除元素和上个方法刚好相反，它是将某个位置的元素删掉(其实是被后面元素覆盖)，该位置后面的元素往前移一位，再将最后元素置null，容量减一
- boolean remove(Object o)
这个方法只传入了一个对象，所以需要遍历已有的元素，分别进行比较，找到匹配的元素的索引，后面的操作跟上个方法相同。这里需要注意，List中可能有null元素，o也可能是null，这样就不能全部用equals方法，先要判断o == null，分别用== 和equals方法比较。
- E set(int index, E element)
这个方法将指定索引的元素替换为新元素，实现比较简单，先检查索引是否越界，再替换指定位置的元素。
- E get(int index)
这个方法获取指定位置的元素，非常简单。
- int size()
这个方法返回List中当前元素个数，实现很简单，但是上面的增删操作都会去修改size值，注意这里的size是元素个数而不是数组长度。
- Iterator<E> iterator()
返回数组的迭代器，用于List遍历，实现比较复杂，下次单独写文章记录。
3.ArrayList实现原理
当前上面的操作都是一些常用的操作，实际ArrayList还有很多实用方法，这里只是简单实现下，了解其实现原理。实际工作中也不会用自己写的ArrayList。ArrayList实现原理中最重要的几个点有：
内部用一个数组来存放元素
底层使用system.arraycopy(Object src,int srcPos,Object dest,int destPos,int length)进行数组复制
使用一个全局size记录元素个数
4.ArrayList实现代码
public class ArrayList<E> implements List<E> {
private Object[] elementData;
private int size;
public ArrayList(int initCapcity){
if(initCapcity < 0){
throw new IllegalArgumentException("initCapcity 必须大于0");
}
elementData = new Object[initCapcity];
}
public ArrayList(){
elementData = new Object[10];
}
@Override
public void add(Object obj) {
grow(size + 1);
elementData[size++] = obj;
}
@Override
public void add(int index, Object obj) {
rangeCheckForAdd(index);
grow(size + 1);
System.arraycopy(elementData, index, elementData, index+1, size - index);
elementData[index] = obj;
size ++;
}
@Override
public void remove(Object obj) {
if(obj == null){
for (int i = 0; i < size; i++) {
if(elementData[i] == null){
fastRemove(i);
}
}
}else{
for (int i = 0; i < size; i++) {
if(obj.equals(elementData[i])){
fastRemove(i);
}
}
}
}
@Override
public E remove(int index) {
rangeCheck(index);
int movedNum = size - index - 1;
E oldElement = elementData(index);
System.arraycopy(elementData, index+1, elementData, index, movedNum);
elementData[--size] = null;
return oldElement;
}
@Override
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@Override
public E set(int index, E obj) {
rangeCheck(index);
E oldElement = elementData(index);
elementData[index] = obj;
return oldElement;
}
@Override
public int indexOf(E obj) {
if(obj == null){
for (int i = 0; i < size; i++) {
if(elementData[i] == null){
return i;
}
}
}else{
for (int i = 0; i < size; i++) {
if(obj.equals(elementData[i])){
return i;
}
}
}
return -1;
}
/**
* 数组扩容
* @param minCapacity
*/
private void grow(int minCapacity) {
if(minCapacity <= elementData.length){
return;
}
int oldCapacity = elementData.length;
int newCapacity = minCapacity + (oldCapacity >> 1);
if(newCapacity < minCapacity){
newCapacity = minCapacity;
}
if(minCapacity > Integer.MAX_VALUE){
newCapacity = Integer.MAX_VALUE;
}
Object[] newArray = new Object[newCapacity];
System.arraycopy(elementData, 0, newArray, 0, newCapacity);
elementData = newArray;
}
@SuppressWarnings("unchecked")
private E elementData(int index){
return (E) elementData[index];
}
private void fastRemove(int i) {
int numMoved = size - i -1;
if(numMoved > 0){
System.arraycopy(elementData, i+1, elementData, i, numMoved);
}
elementData[-- size] = null;
}
private void rangeCheck(int index){
if(index >= size || index <0)
throw new IndexOutOfBoundsException("index:"+index+",size:"+size);
}
private void rangeCheckForAdd(int index){
if(index > size || index <0)
throw new IndexOutOfBoundsException("index:"+index+",size:"+size);
}
}
