二、数组列表 —— ArrayList
1、构造方法
ArrayList 是 Java 中的动态数组，底层实现就是对象数组，只不过数组的容量会根据情况来改变。
它有个带 int 类型参数的构造方法，根据传入的参数，扩展初始化的数组容量，这个方法是推荐使用的，因为如果预先知道数组的容量，可以设置好初始值，而不用等每次容量不够而扩容，减少 Arrays.copyOf 的次数：
它的很多方法的实现都是依靠 Arrays 这个工具类完成的，足以体现它与数组之间的密切关系。
比如有个带 Collection 类型的构造方法，实现如下：
2、常用方法
1) trimToSize 方法
Trims the capacity of this ArrayList instance to be the list's current size.
An application can use this operation to minimize the storage of an ArrayList instance.
该方法可以去掉 ArrayList 占用的多余的空间或内存，因为 ArrayList 每次扩容后总会有所剩余，如果数组很大，占用的多余的空间会比较大，内存不够时可以使用此方法。
2）ensureCapacity 方法
public void ensureCapacity(int minCapacity)
Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
除了在初始化 ArrayList 的时候可以事先定义一个给定的容量之外，还可以用此方法提高 ArrayList 的初始化速度。看下面的例子：
1 public static void main(String[] args) { 2 int n = 100000; 3 String str = "hello google"; 4 5 // 没有调用 ensureCapacity() 方法初始化 ArrayList 对象 6 ArrayList<String> list = new ArrayList<>(); 7 long startTime = System.currentTimeMillis(); 8 for (int i = 0; i <= n; i++) { 9 list.add(str); 10 } 11 long endTime = System.currentTimeMillis(); 12 System.out.println("time: " + (endTime - startTime) + " ms"); 13 14 // 调用 ensureCapacity() 方法初始化 ArrayList 对象 15 list = new ArrayList<>(); 16 startTime = System.currentTimeMillis(); 17 list.ensureCapacity(n); 18 for (int i = 0; i < n; i++) { 19 list.add(str); 20 } 21 endTime = System.currentTimeMillis(); 22 System.out.println("time: " + (endTime - startTime) + " ms"); 23 }
结果为：
3）isEmpty 方法
注意此方法是判断是否为空，不是是否为 null
public boolean isEmpty() {return size == 0; }
4）indexOf 、lastIndexOf 和 contain 方法
indexOf 方法返回 list 中首次出现给定对象的索引值（从 0 开始），如果不存在则返回 -1。
lastIndexOf 方法返回 list 中最后一次出现给定对象的索引值（从 size - 1 开始），如果不存在则返回 -1。
contain 方法 参数为 Object o，判断 list 中是否包含给定的对象，存在则返回 true，源码如下：
5）add，get 和 set 方法
三个很简单的方法，区别在于：add 方法是数组长度 +1，将给定对象放在最后的位置，set 方法是替换指定索引位置的元素，get 方法则是获取指定索引位置的元素。
6）remove 方法
删除指定索引位置的元素或者指定元素，不推荐使用，对数组操作比较复杂，如果你使用了此方法，说明你应该考虑用 LinkedList 了。
3、最佳使用建议
1）ArrayList 是 Array 的复杂版本
ArrayList 内部封装了一个 Object 类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于 ArrayList 的许多方法，如 Index、IndexOf、Contains、Sort 等都是在内部数组的基础上直接调用 Array 的对应方法。
2）内部的 Object 类型的影响
对于一般引用类型来说，这部分的影响不大，但是对于值类型，往 ArrayList 里面添加和修改元素，都会引起装箱和拆箱操作，频繁的操作可能会影响一部分效率。
3）数组扩容
这是对 ArrayList 效率影响比较大的一个因素。
每当执行 Add、AddRange、Insert、InsertRange 等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它就会以当前容量的两倍来重新构建一个数组，将旧元素 Copy 到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。
例 1：比如，一个可能有 200 个元素的数据动态添加到一个以默认 16 个元素大小创建的 ArrayList 中，将会经过：
16*2*2*2*2 = 256
四次的扩容才会满足最终的要求，那么如果一开始就以 ArrayList list = new ArrayList(210) 的方式创建 ArrayList，不仅会减少 4 次数组创建和 Copy 的操作，还会减少内存使用。
例 2：预计有 30 个元素而创建了一个 ArrayList：
ArrayList List = new ArrayList(30);
在执行过程中，加入了 31 个元素，那么数组会扩充到 60 个元素的大小，而这时候不会有新的元素再增加进来，而且有没有调用 TrimSize 方法，那么就有 1 次扩容的操作，并且浪费了 29 个元素大小的空间。如果这时候，用 ArrayList list = new ArrayList(40) 那么一切都解决了。
所以说，正确的预估可能的元素，并且在适当的时候调用 TrimSize 方法是提高 ArrayList 使用效率的重要途径。
特别感谢：
1、Java 中 ArrayList 类的用法
2、《Thinking In Java》
3、《Core Java Volume I》
