一、ArrayList认识
1、概念
概念：ArrayList是一个其容量能够动态增长的动态数组。但是他又和数组不一样，下面会分析对比。它继承了AbstractList，实现了List、RandomAccess, Cloneable, java.io.Serializable。
2、继承关系
为此我们需要先知道ArrayList在整个java集合框架体系里面处于一个什么样的位置。一张图来说明：
从上面我们发现ArrayList的最根部就是实现了Collection接口。下面我们深入进去，看看从ArrayList的角度来分析一下继承关系：
上面这张图基本上描述的很清晰了，实现了四个接口一个抽象类。它继承了AbstractList抽象类，实现了List、RandomAccess, Cloneable, Serializable接口。
- 它继承于AbstractList，实现了List,RandomAccess[随机访问],Cloneable[可克隆], java.io.Serializable[序列化]这些接口。
- ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
- ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。
- ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆
- ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输
- 和Vector不同，ArrayList中的操作不是线程安全的。所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
3、特点
基本的ArrayList，常常用于随机访问元素，但是在List中间插入和移除元素时较慢。同时，ArrayList的操作不是线程安全的！一般在单线程中才使用ArrayList，而在多线程中一般使用Vector或者CopyOnWriteArrayList。对于这些我们先有一个概念。
OK，对于ArrayList的基本认识，主要就是知道是动态的数组，还有其继承关系就可以了，关于他的特点，我们知道其是数组，那么特点就和数组的一样了：随机访问元素比较好。
二、从源码分析ArrayList
既然它继承了AbstractList抽象类，实现了List、RandomAccess, Cloneable, Serializable接口。 那么他肯定就会有继承过来的特性，下面对其方法先进行一个归纳整理。
1、构造方法
- ArrayList()：构造一个初始容量为10的空列表
- ArrayList(Collection<?extend E> c)：构造一个包含指定元素的列表
- ArrayList( int initialCapcity )：构造一个具有初始容量值得空列表
下面看一下代码实现：
//第一种、调用ArrayList(10) 默认初始化一个大小为10的object数组。 public ArrayList() { this(10); } //第二种 public ArrayList(int initialCapacity) { //如果用户初始化大小小于0抛异常，否则新建一个用户初始值大小的object数组。 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); this.elementData = new Object[initialCapacity]; } //第三种：将容器数组化处理并将这个数组值赋给Object数组。 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // 当c.toArray返回的不是object类型的数组时，进行下面转化。 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
2、增删改查操作
对于增删改查的基本操作，在这里只给出一些比较重要的源代码，实现起来比较简单的就不给出了。
（1）增加元素
- add(E e)：添加一个元素到列表的末尾。
- add( int index, E element ) :在指定的位置添加元素
- addAll( Collection<? extends E> c )：添加一个集合到元素的末尾.以上返回类型是boolean
- ensureCapcity（int minCapcity）：确保列表中含有minCapcity的最小容量
下面代码看一下其实现（给出第一个增加元素的方法实现）：
//第一步： public boolean add(E e) { // 加入元素前检查数组的容量是否足够 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } //第二步： private void ensureCapacityInternal(int minCapacity) { modCount++; // 如果添加元素后大于当前数组的长度，则进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //第三步：（扩容） private void grow(int minCapacity) { int oldCapacity = elementData.length; //将数组的长度增加原来数组的一半。 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果扩充一半后仍然不够，则 newCapacity = minCapacity;minCapacity实际元素的个数。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
下面代码看一下其实现（给出第二个增加元素的方法实现）：
//第一步： public void add(int index, E element) { rangeCheckForAdd(index); //检查index的值是否在0到size之间，可以为size。 ensureCapacityInternal(size + 1); // 看elementData的长度是否足够，不够扩容 //将elementData从index开始后面的元素往后移一位。 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } //第二步： private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //第三步： private void ensureCapacityInternal(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); }
（2）删除操作
- remove(Object o)：删除列表中第一个出现O的元素
- remove( int index)：删除列表中指定位置的元素
- removeAll（Collection<?> c）：删除列表中包含C的所有元素
- removeIf（Predictcate<? super E> filter）：删除列表中给定谓词的所有元素
- removeRange( int from,int to )：删除从from到to的所有元素
- clear（）：清除所有的元素。返回类型为void
看代码实现：
public E remove(int index) { //第一步：如果index>=size抛出异常 rangeCheck(index); modCount++; //第二步：获取删除元素的值 E oldValue = elementData(index); //第三步：将index后面所有的元素往前移一位。 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //第四步：返回要删除的原数。 return oldValue; }
上面的只是其中一种实现方式，再来看一种：
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; }
（3）更改操作
- retainAll( Collection<?> c )：仅仅保留列表中和C相同的元素，相当于&运算
- set（int index,E element）：用element替换index位置上的元素。
- size()：返回此列表的元素数
- sort(Comparator<? super E> c)：按照指定的排序规则排序
- subList( int from , int to )：返回从from到to之间的列表
- toArray()：将列表转化为数组
- trimToSize( )：修改当前实例的容量是列表的当前大小。
我们看一下set操作：
//第一步： public E set(int index, E element) { //检查index是否小于size，如果不是抛异常 rangeCheck(index); E oldValue = elementData(index); //覆盖ArrayList中index上的元素。 elementData[index] = element; //返回被覆盖的元素。 return oldValue; } //第二步： private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
再来看看subList操作：
public List<E> subList(int arg0, int arg1) { subListRangeCheck(arg0, arg1, this.size); return new ArrayList.SubList(this, 0, arg0, arg1); }
还有trimToSize
1）修改次数加1 2）将elementData中空余的空间（包括null值）去除，例如：数组长度为10，其中只有前三个元素有值，其他为空，那么调用该方法之后，数组的长度变为3. public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size); } }
最后就是toArray用法
// 第一种方式(最常用) Integer[] integer = arrayList.toArray(new Integer[0]); // 第二种方式(容易理解) Integer[] integer1 = new Integer[arrayList.size()]; arrayList.toArray(integer1); // 抛出异常，java不支持向下转型 //Integer[] integer2 = new Integer[arrayList.size()]; //integer2 = arrayList.toArray();
（4）查操作
- contains（Object o）：如果包含元素o,则返回为true
- get（int index）:返回指定索引的元素
- indexOf( Object o )：返回此列表中指定元素的第一次出现的索引，如果列表不包含此元素，返回-1
- lastindexOf( Object o ):返回此列表中指定元素的最后一次出现的索引，如果列表不包含此元素，返回-1
- isEmpty（）：如果列表为空，返回true.
- iterator()：返回列表中元素的迭代器
- listIterator（）：返回列表的列表迭代器（按适当的顺序）
- listIterator(int index)：从适当的位置返回列表的列表迭代器（按照正确的顺序）
先看一下contain()
public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
还有重要的iterator方法，不过在这里我们不去看，因为在遍历的时候会使用。
三、遍历
在这里给出三种常用的遍历方法
public class Test1 { public static void main(String[] args) { List<String> list1=new ArrayList<>(); list1.add("张三"); list1.add("李四"); list1.add("王五"); //第一种遍历方式：迭代器 Iterator<String> it=list1.iterator(); while(it.hasNext()) { System.out.println(it.next()); } //第二种遍历方式，效率最高 for(int i=0;i<list1.size();i++) { String aaa1=list1.get(0); System.out.println(aaa1); } //第三种方式：for-each for(String a:list1) { System.out.println(a); } } }
要问哪一种效率最高：第二种遍历的效率是最高的。想要验证的话，你只需要加一个时间差就好了。
四、ArrayList需要知道的几个问题
1、与数组的比较
2、与LinkList、Vector对比区别
分析得出下面结论：
（1）ArrayList 本质上是一个可改变大小的数组.当元素加入时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问.元素顺序存储 ,随机访问很快，删除非头尾元素慢，新增元素慢而且费资源 ,较适用于无频繁增删的情况 ,比数组效率低，如果不是需要可变数组，可考虑使用数组 ,非线程安全.
（2）LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList. 适用于 ：没有大规模的随机读取，有大量的增加/删除操作.随机访问很慢，增删操作很快，不耗费多余资源 ,允许null元素,非线程安全.
（3）Vector （类似于ArrayList）但其是同步的，开销就比ArrayList要大。如果你的程序本身是线程安全的，那么使用ArrayList是更好的选择。 Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%.
五、总结
ArrayList总体来说比较简单，不过ArrayList还有以下一些特点：
- ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了
private void writeObject(java.io.ObjectOutputStream s)、
private void readObject(java.io.ObjectInputStream s) 方法 - ArrayList基于数组方式实现，无容量的限制（会扩容）
- 添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
- 线程不安全，会出现fall-fail。下一篇文章会详细讲，
- add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
- get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
- remove(Object o)需要遍历数组
- remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
- contains(E)需要遍历数组
- 使用iterator遍历可能会引发多线程异常
谢谢大家，如有问题还请批评指正。
