注意点
1. 易忽略方法：反转list， Collections.reverse(res);
一. ArrayList
1.常用方法
add(Object);
add(index, Object);
set(index, Object);
get(index);
remove(index);
size();
与Array特点基本相同
2. add方法
ArrayList其实依然是Array，这意味着它也是固定长度（immutable length）和没有空位（no holes）的。
ArrayList初始化数字长默认是10。超过长度后自动补长3/2 or 2 倍。
add方法是add在最后，复杂度O(1)。然而每次在达到极限长度时，都需要补长、拷贝，此时复杂度时O(n)，总体复杂度O(1)是balance（amortized）的结果。
如果需要取消额外的空间，可用trimToSize方法。
3.remove方法
remove一个index位置的数字。remove最后一个时是O(1)，平均复杂度是O(n)，因为需要shift。
二. LinkedList
1.常用方法
addFirst(Object);
addLast(Object);
getFirst();
getLast();
removeFirst();
removeLast();
add(index，Object);
链表分为Singly linked list，doubly linked list， circular linked list
java中的linkedlist是双向非循环链表。只有头尾指针，不能通过index查找数据。需要空间存放指针。
2.实现linked list
（注意reference type取数据之前，要养成先判断是不是null）
（1）nested static class：node
nested class只在一个类中使用，有利于封装性
static用于没有access外部非静态变量的类，如需access外部变量，则改用non-static class
（2）注意判断head == null的情况
注意返回值是node还是value
3.remove(index)，insert方法
linked list与array list中，复杂度均为O(n)
不同点在于，linked list是查找时复杂度为O(n)，删除/插入复杂度为O(1)。ArrayList查找复杂度O(1)，删除/插入复杂度O(n)，因为shift。
三. iterator
1. 使用
例子：
List<Integer> numbers = new LinkedList<Integer>();
numbers.add(1);
Iterator<Integer> itr = numbers.iterator();
迭代器使用期间，不能添加/删除元素。否则回报错 java.util.ConcurrentModificationException。
2. 实现
(1)需要迭代的类implements Iterable接口
(2)override Iterator()方法, 返回新的myIterator类对象。
(3)构建myIterator类，implement Iterator接口，override hasnext() 和next()方法，有时需要重写remove方法。
