Java 常用List集合使用场景分析

1. 前言

本文通过介绍ArrayList、LinkedList、Vector、CopeyOnWriteArrayList底层实现原理和四个集合的区别，了解底层实现原理，可以学到很多代码设计的思路，开阔自己的思维。

知识图解：

2. 知识预览

• ArrayList：基于数组实现的非线程安全的集合。 查询元素快， 插入、删除中间元素慢。

• LinkedList：基于链表实现的非线程安全的集合。查询元素慢，插入、删除中间元素快。

• Vector：基于数组实现的线程安全的集合。线程同步（方法被Synchronized修饰），性能比ArrayList差。

• CopyOnWriteArrayList：基于数组实现的线程安全的写时复制集合。线程安全(ReentrantLock加锁)，性能比Vector高，适合读多写少的场景。

2.1 ArrayList和LinkedList读写快慢的本质

• ArrayList：查询数据快，是因为数组可以通过下表直接找到元素。写数据慢有两个原因：

  • 数组复制过程需要时间
  • 扩容需要实例化新数组也需要时间

• LinkedList：查询数据慢，是因为链表需要遍历每个元素直至找到为止。写数据快的原因：

  • 除了实例化对象需要时间外，只需要修改指针集合完成添加和删除元素

3. 四种结合的对比

3.1 ArrayList

ArrayList是基于动态数组实现的非线程安全的集合。当底层数组满的情况下还在继续添加元素时，ArrayList则会执行扩容机制扩大其数组长度。

下面从ArrayList源码中分析查询操作和添加操作：

// 查询元素
public E get(int index) {
truerangeCheck(index);					// 检查是否越界
truereturn elementData(index);
}
// 顺序添加元素
public boolean add(E e) {
trueensureCapacityInternal(size + 1);  	// 扩容机制
trueelementData[size++] = e;
truereturn true;
}
// 从数组中间添加元素
public void add(int index, E element) {
truerangeCheckForAdd(index);			// 数组下标越界检查
trueensureCapacityInternal(size + 1);  	// 扩容机制
trueSystem.arraycopy(elementData, index, elementData, index + 1, size - index); // 复制数组
trueelementData[index] = element;		// 替换元素
truesize++;
}
// 从数组中删除元素
private void fastRemove(int index) {
truemodCount++;
trueint numMoved = size - index - 1;
trueif (numMoved > 0)
truetrueSystem.arraycopy(elementData, index+1, elementData, index, numMoved);
trueelementData[--size] = null; // clear to let GC do its work
}

1. 查询操作：
   1. 先判断下表是否越界
   2. 然后通过下表从数组中返回元素

2. 添加操作：

   1. 通过扩容机制判断原数组是否还有空间，若没有重新实例化一个空间更大的新数组，把旧数组的数据拷贝到新数组中
   2. 在新数组最后一位元素添加值

3. 中间插入：

   1. 先判断下表是否越界
   2. 扩容
   3. 若插入的下标为i，则通过复制数组的方式将i后面所有的元素，往后移一位
   4. 新数据替换下标为i的旧元素，删除也是一样，只是数组往前移一位，最后一个元素设置为Null

结论：

• ArrayList快在下标定位，慢在数组复制

疑问：能否将每次扩容的长度设置大点，减少扩容的次数，从而提高效率？其实每次扩容的长度大小是很有讲究的。若扩容的长度太大，会造成大量的闲置空间；若扩容的长度太小，会造成频发的扩容(数组复制)，效率更低

3.2 LinkedList

LinkedList是基于双向链表实现的非线程安全的集合，它是一个链表结构，不能项数组一样随机访问，必须是每个元素依次遍历知道找到元素为止。其结构的特殊性导致查询数据慢。

下面从LinkedList源码中分析查询操作和添加操作:

// 查询元素
public E get(int index) {
truecheckElementIndex(index); 	// 检查是否越界
truereturn node(index).item;
}
Node<E> node(int index) {
trueif (index < (size >> 1)) { 	// 类似二分法
truetrueNode<E> x = first;
truetruefor (int i = 0; i < index; i++)
truetruetruex = x.next;
truetruereturn x;
true} else {
truetrueNode<E> x = last;
truetruefor (int i = size - 1; i > index; i--)
truetruetruex = x.prev;
truetruereturn x;
true}
}
// 插入元素
public void add(int index, E element) {
truecheckPositionIndex(index);	// 检查是否越界
trueif (index == size)			// 在链表末尾添加
truetruelinkLast(element);
trueelse						// 在链表中间添加
truetruelinkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
truefinal Node<E> pred = succ.prev; 
truefinal Node<E> newNode = new Node<>(pred, e, succ);
truesucc.prev = newNode;
trueif (pred == null)	
truetruefirst = newNode;
trueelse				
truetruepred.next = newNode;
truesize++;
truemodCount++;
}

1. 查询操作：

   1. 先判断元素是靠近头部还是尾部

   2. 若靠近头部，则从头部开始依次查询判断，和ArrayList的elementData(index)相比慢了很多

2. 插入操作：

   1. 判断插入元素的为止是链表的尾部还是中间。

   2. 若在尾部添加元素，直接将尾节点的下一个指针指向新增节点

   3. 若在链表中间添加元素，先判断插入的为止是否为首节点，是则将首节点的上一个指针指向新增节点。否则先获取当前节点的上一个节点（简称A），并将A节点的下一个指针指向新增节点，然后新增节点的喜爱一个指针指向当前节点。

3.3 Vector

Vector 的数据结构和使用方法与ArrayList差不多。最大的不同就是Vector是线程安全的。从下面的源码可以看出，几乎所有的对数据操作的方法都被synchronized关键字修饰。synchronized是线程同步的，当一个线程已经获得Vector对象的锁时，其他线程必须等待直到该锁被释放。从这里就可以得知Vector的性能要比ArrayList低。
若想要一个高性能，又是线程安全的ArrayList，可以使用Collections.synchronizedList(list);方法或者使用CopyOnWriteArrayList集合

public synchronized E get(int index) {
trueif (index >= elementCount)
truetruethrow new ArrayIndexOutOfBoundsException(index);

truereturn elementData(index);
}
public synchronized boolean add(E e) {
truemodCount++;
trueensureCapacityHelper(elementCount + 1);
trueelementData[elementCount++] = e;
truereturn true;
}
public synchronized boolean removeElement(Object obj) {
truemodCount++;
trueint i = indexOf(obj);
trueif (i >= 0) {
truetrueremoveElementAt(i);
truetruereturn true;
true}
truereturn false;
}

3.4 CopyOnWriteArrayList

在这里我们先简单了解一下CopyOnWrite容器。它是一个写时复制的容器。当我们往一个容器添加元素的时候，不是直接往当前容器添加，而是先将当前容器进行copy一份，复制出一个新的容器，然后对新容器里面操作元素，最后将原容器的引用指向新的容器。所以CopyOnWrite容器是一种读写分离的思想，读和写不同的容器。
应用场景：适合高并发的读操作（读多写少）。若写的操作非常多，会频繁复制容器，从而影响性能。

CopyOnWriteArrayList 写时复制的集合，在执行写操作（如：add，set，remove等）时，都会将原数组拷贝一份，然后在新数组上做修改操作。最后集合的引用指向新数组。
CopyOnWriteArrayList 和Vector都是线程安全的，不同的是：前者使用ReentrantLock类，后者使用synchronized关键字。ReentrantLock提供了更多的锁投票机制，在锁竞争的情况下能表现更佳的性能。就是它让JVM能更快的调度线程，才有更多的时间去执行线程。这就是为什么CopyOnWriteArrayList的性能在大并发量的情况下优于Vector的原因。

private E get(Object[] a, int index) {
truereturn (E) a[index];
}
public boolean add(E e) {
truefinal ReentrantLock lock = this.lock;
truelock.lock();
truetry {
truetrueObject[] elements = getArray();
truetrueint len = elements.length;
truetrueObject[] newElements = Arrays.copyOf(elements, len + 1);
truetruenewElements[len] = e;
truetruesetArray(newElements);
truetruereturn true;
true} finally {
truetruelock.unlock();
true}
}
private boolean remove(Object o, Object[] snapshot, int index) {
truefinal ReentrantLock lock = this.lock;
truelock.lock();
truetry {
truetrueObject[] current = getArray();
truetrueint len = current.length;
truetrue......
truetrueObject[] newElements = new Object[len - 1];
truetrueSystem.arraycopy(current, 0, newElements, 0, index);
truetrueSystem.arraycopy(current, index + 1, newElements, index, len - index - 1);
truetruesetArray(newElements);
truetruereturn true;
true} finally {
truetruelock.unlock();
true}
}

4. 总结

看到这里，如果面试官问你ArrayList和LinkedList有什么区别时

如果你回答：ArrayList查询快，写数据慢；LinkedList查询慢，写数据快。面试官只能算你勉强合格。
如果你回答：ArrayList查询快是因为底层是由数组实现，通过下标定位数据快。写数据慢是因为复制数组耗时。LinkedList底层是双向链表，查询数据依次遍历慢。写数据只需修改指针引用。
如果你继续回答：ArrayList和LinkedList都不是线程安全的，小并发量的情况下可以使用Vector，若并发量很多，且读多写少可以考虑使用CopyOnWriteArrayList。
因为CopyOnWriteArrayList底层使用ReentrantLock锁，比使用synchronized关键字的Vector能更好的处理锁竞争的问题。