1. ArrayList
1.1 简介
JDK提供的集合数据结构中，ArrayList 几乎是我们最常用的一个集合类，实现了 List 接口，本质上是一个可调整大小的数组，因此他拥有数组的特性。ArrayList 底层封装了一个 Object 数组 elementData ，通过 List 和 RandomAccess 接口提供的方法来对该数组进行访问和写入操作。ArrayList 的具体操作如下。
- 访问元素操作：提供随机访问功能，可以通过下标索引随机访问列表中的元素，访问的时间复杂度是 O(1) ；
- 插入元素操作：如果数组空间不足，会引发扩容操作，同时，如果元素插入的位置不是列表尾端，会引发插入位置后面的数组元素的复制移动，时间复杂度为 O(n) ；
- 移除元素操作：如果不知道要移除元素的下标索引，需要先查找到元素的位置，如果移除的元素不是尾端元素，会引发移除位置后面的数组元素的复制移动，时间复杂度为 O(n) ；
- 遍历元素操作：通过下标进行
for循环或者通过Iterator接口进行迭代，其性能是一样的，因为ArrayList的Iterator接口实现内部，仍然是使用索引下标访问数组。
1.2 扩容原理
ArrayList 在插入元素之前，会先计算数据空间是否充足，如果数组空间不足，会先进行扩容操作，新的容量大小等于原数组大小加上原数组大小的一半。
int newCapacity = oldCapacity + (oldCapacity >> 1);
也可以通过 ensureCapacity 方法来将数组的空间扩容到指定的大小，如果指定的容量大小小于或等于底层的数组长度 elementData.length，该方法不会执行扩容操作。所以当需要插入大量元素到ArrayList 中时，可以根据插入元素的数量，事先进行手动的扩容操作（调用 ensureCapacity 方法），这样就可以防止在插入过程中，ArrayList 频繁发生自动扩容而消耗性能。
ArrayList有三个构造函数， 其中无参构造函数ArrayList()在创建了ArrayList对象后，不会立刻分配数组空间，而是先将elementData指向一个空数组，等到程序向列表中添加元素的时候，再通过扩容操作分配数组空间，此时默认扩容长度是DEFAULT_CAPACITY = 10；而有参构造函数ArrayList(int initialCapacity)要求指定初始的容量，通过该构造器创建ArrayList对象，会立刻分配数组空间，数组大小等于参数指定的容量大小。
2. LinkedList
2.1 简介
LinkedList 是JDK对于双向链表数据结构的基本实现，内部申明了两个引用，一个是 first 指向链表首节点，一个是 last 指向链表尾节点，链表的节点数据结构 Node 内部维护了两个引用，一个是 next 指向他的后继节点，一个是 prev 指向他的前驱节点；同时 LinkedList 维护了一个 size 变量来保存链表的长度。LinkedList 未实现 RandomAccess 接口，因此不支持快速的随机访问功能；LinkedList 的具体操作如下。
- 访问元素操作：能够快速的访问头部和尾部节点，因此，可以当作队列使用；如果要访问任意位置的元素，则需要遍历链表找到对应位置的元素，JDK在实现中做了优化，如果访问的位置在列表的前半部分，则从首节点开始沿着后继节点向后遍历查找，如果访问的位置在列表的后半部分，则从尾节点开始沿着前驱节点向前遍历查找；时间复杂度为 O(n) ;
- 插入元素操作：可以快速的在头部和尾部插入节点，尤其是在头部插入节点，无需移动复制其他元素，而
ArrayList在头部插入元素时，需要将整个数组后移。在头部和尾部插入节点的时间复杂度是 O(1) ；在列表的其他位置插入元素时，需要先找到插入位置的节点，新插入节点作为原位置节点的前驱节点被插入到链表中；因此，其时间复杂度时 O(n) ； - 移除元素操作：可以快速的移除头部和尾部节点，时间复杂度时 O(1) ；如果要移除其他位置的节点，需要先找到对应位置的节点，时间复杂度时 O(n) ;
- 遍历元素操作：通过
Iterator接口进行迭代的性能好于ArrayList；
3. ConcurrentModificationException
通过 Iterator 接口遍历 ArrayList 或者 LinkedList 的时候，有时候会引发 ConcurrentModificationException；这是因为 ArrayList 和 LinkedList 都是非线程安全的 List 实现类，而通过 Iterator 对象遍历列表，实际遍历的是列表的数据视图，因此一旦在多线程环境下使用 ArrayList 和 LinkedList ，可能会出现数据不一致的问题。而这两个类本身就不是设计用在多线程环境下的，于是就采用了 fast-fail 的设计方式，在迭代过程中会对列表的实时状态进行检测，一旦发现列表结构被更改，就会立刻抛出 ConcurrentModificationException。
具体是如何的检测的呢？ArrayList 和 LinkedList 的抽象基类 AbstractList 中有一个变量 modCount ，该变量记录了列表结构被改变的次数，只要对列表进行添加或移除操作，modCount 的值都会增加。当通过 Iterator 对象遍历列表的时候：
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);
list.add(3);
list.add(4);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
if(integer==2)
list.remove(integer);
}
iterator() 方法内部创建了一个新的 Iterator 对象，在创建的时候，Iterator 对象会保存此刻列表的 modCount 值
private int expectedModCount = modCount;
在迭代过程中，每次通过 next 方法来访问列表元素，都会先检测 Iterator 对象保存的状态值 expectedModCount 是否与列表自身的 modCount 值一致；
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
一旦发现不一致，说明列表的结构被其他线程改变了，因此，会立刻抛出 ConcurrentModificationException 异常，以避免数据不一致的情况发生。
4. 总结
ArrayList 和 LinkedList 是 JDK 中 List 接口的两个基本实现。
ArrayList 实现了一个可以扩容的数组，在每次添加元素之前，都要进行容量计算，如果容量不足则会进行扩容，扩容的时候会产生内存的复制操作，所以 ArrayList 中的元素越多，扩容操作的消耗越大，因此在需要对 ArrayList 进行优化的时候，可以预估其可能存储的元素数量，在创建的时候就指定其容量大小，来尽量避免扩容操作。
LinkedList 实现了一个双向链表，头部和尾部的插入和移除操作的时间复杂度都是 O(1) ，并且 LinkedList 还实现了 Deque 接口，因此可以作为双端队列来使用。
ArrayList 和 LinkedList 都是非线程安全的列表实现类，尽量不要在多线程环境下使用，在多线程环境下，可能会引发 ConcurrentModificationException 异常，可以使用Java并发包下的 CopyOnWriteArrayList 来代替 ArrayList，ConcurrentLinkedDeque 来代替 LinkedList。
网友评论