摘要：包提供了两种比常用很多，原因是查找更容易封装了一个数组数组的初始化封装一个空数组封装一个大小为的数组数组如何实现扩容都需要先进行扩容检查，类似，对象调用方法，要进行对象判空，操作之前要进行，线程检查扩容检查增加的大小与数组比较计算数组扩容的
List
java.util包提供了两种
ArrayList LinkedList
ArrayList比LinkedList常用很多，原因是:
ArrayList查找更容易
ArrayList封装了一个数组Object[]
数组的初始化
ArrayList array = new ArrayList();
封装一个空数组, {}
ArrayList array = new ArrayList(10);
封装一个大小为10的数组 new Object[10];
数组如何实现扩容
ArrayList.add/addAll都需要先进行扩容检查，
类似，
对象调用方法，要进行对象判空， UI操作之前要进行，线程检查
扩容检查: size+增加的大小 与 数组.length 比较
计算数组扩容的数组长度：
首先，扩容至原数组大小的一倍，size+增加的大 小与其比较：
如果大于，扩容至原数组大小的一倍
如果小于，扩容至size+增加的大小;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容使用的是: Array.copyof(array, newLen)
removeAll如何实现
与remove()不同，remove使用System.copy完成数组的 部分移动
而removeAll,使用的算法：
ArrayList array1 = new ArrayList();
array1.addAll({0,3,5,7,3,6});
int[] array2 = {3,5,4};
array1.removeAll(array2);
首先，遍历array1中每个元素，若元素 不在array2内，将计数位置的值设置为元素的值并将计 数+1;
遍历完成后，计数为数组剩余元素的个 数，将计数之后的元素清空.
算法详细:
0,3,5,7,3,6 ;
遍历之后，计数为2，数组为0,7,6,7,3,6;
清空之后，0,7,6,null,null,null;
trimToSize()
数组扩容后即使删除元素，数组的length也不会该改变，
意味着即使删除了某些元素数组占用的内存大小不会改变;
数组只会不断的增大,且出现大量null的元素.
trimToSize()方法用于改变数组的length,将为null的元素释放掉，等待GC
这也是防止内存浪费的一种方式，当ArrayList经历了多次删除操作之后，使用trimToSize(),避免内存浪费.
trimToSize()使用Array.copyof()来改变数组的length
总结
ArrayList本质上维护了一个数组，也就意味者它具有数组的优缺点：增删难，查找易
Node的数据结构
Node{ E element; Node prev; Node next; }
基本结构
Nodefirst, last
Linked是双向链表,first,last指向表头，表尾
总结
LinkedList是一个Deque,双向链表，
增删易，查找难，造成在编码中很少使用
java.util包提供了两种Map:
1.HashMap
2.TreeMap
Android为了性能优化，提供了HashMap的替代品:
1.ArrayMap
2.SparseMap
它俩可以在数据量都在千级以内的情况下，
如果key的类型为int，使用SparseMap,
如果key的类型为其它类型，使用ArrayMap
HashMap相比TreeMap更常用
数据结构
Node的数据结构:
