ArrayList 和 LinkedList #
ArrayList #
ArrayList是一个可扩容的，底层用数组实现的，非线程安全的集合类
- 实现RamdonAsceess接口，无实质内容，声明性质，表明ArrayList支持随机访问
- 实现Cloneable，声明需要复写clone()接口，且可以支持克隆
- 实现Serializable，声明可序列化
- 初始容量10，最大容量Integer.MAX_VALUE - 8。
- 出现可能越界的操作时检查是否需要扩容，每次扩容为原来的1.5倍
- 内部维护元素的数组使用transient修饰，阻止默认的序列化和反序列化。原因是大多情况下数组不是满的，默认的序列化会把空的部分也序列化进去。ArrayList自己实现了合适的序列化和反序列化方法
- 内部维护一个自增变量，记录修改的次数，添加、删除、扩容都会使操作数++，相当于版本号。作用是在迭代器遍历过程中检查数组是否被修改，迭代器遍历过程中是禁止修改的。只要版本号不对，就会抛出异常，这就是fail-fast
- 扩容方法是新建一个更大容量的数组，然后将元素复制过去。
LinkedList #
LinkedList一个内部用双向链表实现的List，同时实现了Deque接口，可以当作队列或者栈来使用。
- 实现Cloneable和Serializable，可以被克隆也可以被序列化
- 克隆时和ArrayList一样是浅拷贝
- 实现了Deque接口，支持两端的元素插入和删除
- 继承AbstractSequential类，声明支持按次序访问
- 内部维护头节点和尾节点，以及元素个数
- 内部静态类Node包含元素、前驱和后继节点
- 支持从头部、尾部、任意位置添加、删除元素
对比 #
ArrayList是数组，LinkedList是链表
- 基于数组的ArrayList，底层连续存储
知道第一个元素的位置就可以通过索引快速访问到后续元素，随机查找速度O(1)
删除数据和插入数据可能需要重排数据中的所有数据或者是更新索引，开销大O(n)
ArrayList需要扩容，每次扩容会备用一些没被使用的数组空间 - 基于链表的LinkedList，底层可以离散存储
每个节点存储数据、前一个元素引用、后一个元素引用 增删时不需要像数组那样重新计算大小或者更新索引，增删速度O(1)
查询需要逐个元素直到找到，效率低O(n)