ArrayList 与 LinkedList 列表结构分析

ArrayList

ArrayList 内部维护了一个动态的Object 数组，ArrayList 的动态增删就是对这个数组的动态增删。

1、ArrayList 的构造以及初始化

ArrayList 实例变量

ArrayList构造函数：

ArrayList 构造函数

ArrayList 在调用构造函数初始化时（new），如果是无参构造，则是为elementData赋值为Object[0]，即创建一个容量为0的空数组；有参数，则创建指定容量大小的空数组。

2、ArrayList的容量分配机制

ArrayList 的容量上限：ArrayList 容量是有上限的，理论上允许分配Integer.Max_VALUE - 8大小的容量。

ArrayList 最大容量

调用 add 方法时扩容规则：

add 源码

当使用无参构造函数初始化 ArrayList 时，在第一次 add 时会将容量大小设置为默认值10；当容量大小少于元素个数时，会进行扩容，扩容大概会增长50%。

总结：每次扩容都会伴随数组的复制操作，因此一次给定恰当的容量会提高一点性能。

ArrayList 扩容流程

3、ArrayList 迭代器

ArrayList 迭代器源码

checkForComodification 是 java-collection-framwork 中的一种 fast-fail 的错误检测机制。

fast-fail事件产生的条件：当多个线程对Collection进行操作时，若其中某一个线程通过iterator去遍历集合时，该集合的内容被其他线程所改变，则会抛出ConcurrentModificationException异常。

Itr 迭代器定义了一个exceptedModCount， 记录 modCount 副本，在 ArrayList 执行改变结构的操作时，例如 add，remove，clear 方法时，modCount 的值会改变。故通过 iterator 去遍历集合，使用list的 add，remove，clear 方法时，由于modCount 的值改变了，但是Itr 迭代器里的  exceptedModCount 未改变，导致 checkForComodification 会抛出 ConcurrentModificationException 异常。解决方案：使用 Itr 的add，remove 方法（高并发场景不适用）。注：for(String str : strs) 该形式的遍历底层是 Itr 迭代器。

使用J.U.C中的 CopyOnWriteArrayList 解决 fast-fail 问题：

CopyOnWriteArrayList 是线程安全的，具体看下它的 add 方法源码：

add 源码

CopyOnWriteArrayList 就是写时复制的 ArrayList。当开始写数据的操作时，ArrayList.copyOf 一个新的数组，这样不会影响读操作。

这样的代价就是会损耗内存，带来性能的问题。CopyOnWriteArrayList 写的时候在内存中生成一个副本对象（容量+1），然后将新增的元素放入数组最后一位，最后将新的副本数组覆盖原来数组。

CopyOnWriteArrayList 无法保证数据实时的一致，只能保证结果一致。适用于并发下读多写少的场景，例如缓存。

LinkedList 

LinkedList 即链表，相对于顺序表，链表存储数据不需要使用地址连续的内存单元。减少了修改容器结构而带来的移动元素的问题。

1.结点（Node）的定义

LinkedList是双向链表， 每个结点分别存有上一个结点和下一个结点的信息。它的定义如下：

Node 结点

2、LinkedList 构造以及初始化

成员：LinkedList中维护了三个成员变量，用以记录链表中的结点个数，结点的前驱（表头）以及后继（表尾）。

LinkedList 成员变量 构造方法

LinkedList 没有容量的属性，即没有扩容的概念。

3、LinkedList 的结构操作

add:

几种add 源码

get:

get 源码 get 下node方法 源码

size >> 1：位运算，将size 的二进制向右移一位，相当于 size/2；举个栗子：

4的二进制位：0100，向右移一位得：0010（2），故相当于取一半。

node(int index) 源码中，我们发现，当 index 属于前半部分的计数，从头遍历查找（最后一个下标为 index - 1，即为所需数据）；当 index 属于后半部分的计数，从末尾遍历查找，充分利用了双向链表的特点。

remove:

remove 源码

删除元素，遍历整个表。

LinkedList，ArrayList 总结

ArrayList 是基于动态数组的数据结构，LinkedList 基于链表的数据结构。

对于随机访问get 和set 方法，ArrayList 优于 LinkedList，因为 LinkedList 要根据传入的 index，遍历链表获取元素。

对于add，LinkedList 比较占优势，它直接放入链表尾部就行了，而 ArrayList需要扩容。对于 remove 方法，因情况而定，因为 LinkedList 是需要遍历整个表的，如果数据量很大的话，与 ArrayList 的移动数据所消耗的性能是差不多的。