数组
以下是数组在内存中存储结构和扩容过程。
array数组长度为4，现在需要放入第五个值，需要先扩容，在后边找到能容下新数组长度的连续空间
新增数据空间判断
新增数据的时候需要判断当前是否有空闲空间存储数据
扩容需要申请新的连续空闲空间
上图为例，长度4需要扩容到8。必须找到长度为8的连续空间才能新建扩容数组
把老的数组复制过去，追加新的内容
回收老的数组空间
链表
- 寻找一个元素空间插入即可，不需要连续空间
- 链表长度大小不定
- 需要寻址，节省空间
时间复杂度对比
O(1)就是最低的时空复杂度了，耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
O(N)就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法，就是O(n)；
总结
- ArrayList是由数组组成，大小固定，不适合动态存储，LinkedList由双向列表组成，大小可变，扩展性强；ArrayList扩容大小为1.5倍(newCapacity = oldCapacity + (oldCapacity >> 1))
- ArrayList查询和修改方便，只需要修改和获取指定的数组值，LinkedList新增和删除方便，因为只需要添加和删除节点
- 数据结构都是存储在内存中，一般初始化时指定大小都是2的倍数，计算机分配空间都是使用次幂去分配，好处是能减少碎片空间，ArrayList扩容时需要查询连续的空间，而LinkedList只需要查询到下一个空间即可
- 同样是O(N)次遍历，ArrayList快于LinkedList，因为CPU缓存一次读取多块，ArrayList获取空间块链是连续的，而Linked获取空间块链可能是跳跃的，获取下一个元素需要利用内存中的下标去查找，CPU缓存读取速度大于内存
- forEach循环时删除元素会爆ConcurrentModificationException异常,要使用迭代器(Iterator),或者线程安全的集合,原因是java.util.ArrayList.Itr#checkForComodification方法中modCount != expectedModCount
