List
ArrayList和LinkedList是我们常用的集合数据结构。他们的类结构以及依赖关系如下图。
ArrayList、Vector、LinkedList 集合类继承了 AbstractList 抽象类，而 AbstractList 实现了 List 接口，同时也继承了 AbstractCollection 抽象类。ArrayList、Vector、LinkedList 又根据自我定位，分别实现了各自的功能。ArrayList 和 Vector 使用了数组实现，这两者的实现原理差不多，LinkedList 使用了双向链表实现。
ArrayList
ArrayList的实现
- ArrayList 实现了 List 接口，继承了 AbstractList 抽象类，底层是数组实现的，并且实现了自增扩容数组大小。
- ArrayList 还实现了 Cloneable 接口和 Serializable 接口，所以他可以实现克隆和序列化。
- ArrayList 还实现了 RandomAccess 接口。RandomAccess 接口是一个标志接口，他标志着“只要实现该接口的 List 类，都能实现快速随机访问”。
ArrayList的属性
- 数组长度 size
- 对象数组 elementData
- 初始化容量 default_capacity， 其中初始化容量默认大小为 10。
1 //默认初始化容量 2 private static final int DEFAULT_CAPACITY = 10; 3 //对象数组 4 transient Object[] elementData; 5 //数组长度 6 private int size;
ArrayList 的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据。如果采用外部序列化法实现数组的序列化，会序列化整个数组。ArrayList 为了避免这些没有存储数据的内存空间被序列化，内部提供了两个私有方法 writeObject 以及 readObject 来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间。因此使用 transient 修饰数组，是防止对象数组被其他外部方法序列化。
ArrayList的初始化
- ArrayList 类实现了三个构造函数，第一个是创建 ArrayList 对象时，传入一个初始化值；
- 第二个是默认创建一个空数组对象；
- 第三个是传入一个集合类型进行初始化。当 ArrayList 新增元素时，如果所存储的元素已经超过其已有大小，它会计算元素大小后再进行动态扩容，数组的扩容会导致整个数组进行一次内存复制。
因此，我们在初始化 ArrayList 时，可以通过第一个构造函数合理指定数组初始大小，这样有助于减少数组的扩容次数，从而提高系统性能。
ArrayList的增删改查方法
新增元素
两种新增，一种是新增元素在数组最尾部，另一种是在指定位置新增元素。
两种新增方式相同点是在新增之前都会判断数组大小是否足够，如果不足就会按照原来数组的 1.5 倍大小进行扩容，在扩容之后需要将数组复制到新分配的内存地址。
不同点是添加元素到任意位置，会导致在该位置后的所有元素都需要重新排列，而将元素添加到数组的末尾，在没有发生扩容的前提下，是不会有元素复制排序过程的。
删除元素
ArrayList 的删除方法和添加任意位置元素的方法是有些相同的。ArrayList 在每一次有效的删除元素操作之后，都要进行数组的重组，并且删除的元素位置越靠前，数组重组的开销就越大。
遍历元素
由于 ArrayList 是基于数组实现的，所以在获取元素的时候是非常快捷的。
LinkedList
LinkedList的实现
- LinkedList 类实现了 List 接口、Deque 接口
- 继承了 AbstractSequentialList 抽象类
- LinkedList 既实现了 List 类型又有 Queue 类型的特点
- LinkedList 也实现了 Cloneable 和 Serializable 接口，同 ArrayList 一样，可以实现克隆和序列化。
由于 LinkedList 存储数据的内存地址是不连续的，而是通过指针来定位不连续地址，因此，LinkedList 不支持随机快速访问，LinkedList 也就不能实现 RandomAccess 接口。
LinkedList的属性
- LinkedList first 属性 头部指针
- LinkedList last 属性 尾部指针
- size 属性，列表大小
1 transient int size = 0; 2 transient Node<E> first; 3 transient Node<E> last;
我们可以看到这三个属性都被 transient 修饰了，原因很简单，我们在序列化的时候不会只对头尾进行序列化，所以 LinkedList 也是自行实现 readObject 和 writeObject 进行序列化与反序列化。
LinkedList 定义了一个 Node 结构，Node 结构中包含了 3 个部分：元素内容 item、前指针 prev 以及后指针 next
1 private static class Node<E> { 2 E item; 3 Node<E> next; 4 Node<E> prev; 5 6 Node(Node<E> prev, E element, Node<E> next) { 7 this.item = element; 8 this.next = next; 9 this.prev = prev; 10 } 11 }
LinkedList的增删改查方法
新增元素
LinkedList 添加元素的实现很简洁，但添加的方式却有很多种。默认的 add (Ee) 方法是将添加的元素加到队尾，首先是将 last 元素置换到临时变量中，生成一个新的 Node 节点对象，然后将 last 引用指向新节点对象，之前的 last 对象的前指针指向新节点对象。
LinkedList 也有添加元素到任意位置的方法，如果我们是将元素添加到任意两个元素的中间位置，添加元素操作只会改变前后元素的前后指针，指针将会指向添加的新元素，所以相比 ArrayList 的添加操作来说，LinkedList 的性能优势明显。
删除元素
在 LinkedList 删除元素的操作中，我们首先要通过循环找到要删除的元素，如果要删除的位置处于 List 的前半段，就从前往后找；若其位置处于后半段，就从后往前找。这样做的话，无论要删除较为靠前或较为靠后的元素都是非常高效的，但如果 List 拥有大量元素，移除的元素又在 List 的中间段，那效率相对来说会很低。
遍历元素
LinkedList 的获取元素操作实现跟 LinkedList 的删除元素操作基本类似，通过分前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的，特别是在 for 循环遍历的情况下，每一次循环都会去遍历半个 List。所以在 LinkedList 循环遍历时，我们可以使用 iterator 方式迭代循环，直接拿到我们的元素，而不需要通过循环查找 List。