List是列表结构的抽象，从不同的实现场景分为不同的类别，如多线程、数组和节点实现等。从线程安全实现分为：单线程实现（ArrayList、LinkedList）、多线程实现（Vector、CollectionsSynchronizedList）；从实现方式分为数组Array、节点Linked实现。如下图所示，图中Collection分为两条之路，synchronized和unSynchronized,此外Vector是AbstractionCollection下的synchronized实现。
List和AbstractList
上一篇博文
Collection适配器
有提到接口和抽象类搭配来降低类的复杂度和代码规模的好处，此处List扩展Collection，而AbstractList继承AbstractCollection又实现了List，同样也是类适配。List在Collection基础上新增了9个方法，用户满足列表的基本操作，如下图所示。
在AbstractList中实现了非具体的indexOf、lastIndexOf、listIterator、iterator和subList，而将List的基本操作remove、add、get和set交于具体的实现类进行实现。这里有必要说明下AbstractList.Itr和AbstratList.ListItr这两个内部类，它们都会抛出ConcurrentModificationException，也称为fail-fast异常。
– fail-fast
在多线程或单线程环境下并发的修改List集合结构所采用的检测机制，例如
public static void main(String[] args) {
final List<String> strs = new ArrayList<String>();
strs.add("haha");
final Iterator<String> itr = strs.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
strs.remove(); //在进行遍历访问时修改了strs的结构，抛出fail-fast异常
}
}
//看下内部实现
public abstract class AbstractList
extends AbstractCollection implements List {
private class Itr implements Iterator {
int cursor;
int lastRet;
int expectedModCount; //fail-fast关键在这个字段
//... ... ...
private Itr() {
cursor = 0;
lastRet = -1;
//在创建实例时，将修改次数进行记录，一旦发生变化则说明List结构发生改变，抛出CurrentModificationException异常
expectedModCount = modCount;
}
final void checkForComodification() {
if(modCount != expectedModCount) {
throw new CurrentModificationException();
}
}
}
}
其实在List的实现类中，
必须保证对List的状态访问时不会动态的修改List结构，从而可能导致访问出现元素不存在或者死循环
。同理ListIterator也实现了fail-fast异常，而且扩展了Iterator接口，将列表的顺序访问特性进行封装，才用双向指针（next、previous）来动态的访问当前元素的前后元素。
ArrayList、LinkedList和Vector列表实现
前面的接口和抽象适配器都只定义了列表应该包含的基本功能，而列表的实现者根据内部存储元素的介质不同分为：ArraList、LinkedList两种，前者内部又数组实现，而后在通过元素指针实现，它们都是线性结构。
-
ArrayList
Array作为List的内部容器，它的特性包括：容量动态扩展、快速访问和友好的CRUD操作API。每次修改当前列表的结构时，都需要创建新数组，同时要拷贝当前数组的元素，需要额外的内存开销。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable {
private transient E[] elementData;
private int size;
/*
首先要说明的是size属性,它是ArrayList的实际元素个数，在ArrayList的构造函数里size的默认大小是10，最大值是2147483647L（32位JVM）,默认按capacity(数组大小) 1.5 + 1动态扩展ArrayList大小，其内部扩展是通System.arraycopy本地方法来实现数组的动态复制。
*/
public void ensureCapacity(int capacity) {
this.modCount++;
int srcLen = this.elementData.length;
if(capacity > srcLen) {
E[] oldData = this.elementData；
int targetLen = srcLen * 3 / 2 + 1;
if(targetLen < capacity) {
targetLen = capacity;
}
this.elementData = (E[])new Object[targetLen];
System.arraycopy(oldData, 0, this.elmentData, 0, srcLen);
}
}
/*
其次，ArrayList的快速访问，因为数组可以通过下标进行访问，所以ArrayList的访问速度更加快速。
*/
public E get(int index) {
RangeCheck(index);
return this.elementData[index];
}
public E set(int index, E element) {
RangeCheck(index);
Object localObject = this.elementData[index];
this.elementData[index] = element;
return localObject;
}
/*
此外，在List末尾附加元素更加快速，当容量不需要进行扩展时。
*/
public boolean add(E element) {
ensureCapacity(this.size + 1);
this.elementData[this.size++] = element;
return true;
}
// ... ... ...
}-
LinkedList
Linked节点包装元素的List实现，它的特性包括：不限大小、快速增删元素和友好的CRUD操作API。每次查找元素需要从header开始移动，查询速度较慢，此外，元素被包装在Entry节点中，需要维护next、previous前后两个指针的指向。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Queue<E>, Cloneable, Serializable {
priate transient Entry<E> header; //双端链表的头结点
private transient int size; //理论上大小无限制，但是size最大为2147483647
private static class Entry<E> { //包装节点
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
public LinkedList() {
//头元素
this.header = new Entry(null, null, null);
this.size = 0;
this.header.next = (this.header.previous = this.header);
}
/*
首先，修改List结构快速，无需额外的外部内存开销,只需要修改当前节点的next、previous指向即可。
*/
private E remove(Entry<E> e) {
if(e == header)
throw new NoSuchElementException();
E result = e.elment;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = e.element = null;
size--;
modCount++;
return result;
}
private Entry<E> addBefore(E element, Entry<E> e) {
Entry<E> newEntry = new Entry<E>(element, e, e.previous);
newEntry.next.previous = newEntry;
newEntry.previous.next = newEntry;
size++;
modCount++;
return newEntry;
}
}-
Vector
在多线程环境下，由于ArrayList不能满足安全性，而synchronized锁定当前对象保证操作的原子性是java自带的安全措施，所以Vector将方法加上synchronized。从这里可以看出，早起的同步措施比较简单，JDK想要通过synchronized来实现，但是synchronized本身存在的this逃逸问题以及锁定范围过广的性能问题都使得Vector不适用于大多数情况。
public class Vector<E> extends AbstractList
implements List, RandomAccess, Cloneable, Serializable {
private E[] elementData;
private int elementCount;
private int capacityIncrement;
public synchronized void copyInto(E[] eArr) {
System.copyarray(elementData, 0, eArr, 0, elementCount);
}
//... ... ...
}-
Collections.SynchronizedList
ArrayList、LinkedList不能保证线程安全，而Vector又存在synchronized锁范围太大，那么改善的理由是将synchronized的锁范围放小，也就有了Collection.SynchronizedList
public class Collections {
static class SynchronizedList<E>
extends SynchronizedCollection implments List<E> {
List<E> list;
public boolean equals(E element) {
synchronized(mutex) {
return list.equals(elment);
}
}
public E get(int index) {
synchronized(mutex) {
return list.get(index);
}
}
// ... ... ...
}
}-
CopyOnWriteArrayList
在多线程环境下，只有进行写时才会存在问题，而每个线程都只是单纯的读取数据并不会产生数据不一致问题。所以CopyOnWriteArrayList将synchronized加在必要的写方法中，从而减少List操作中不必要的性能损耗。从名字上就能体现出CopyOnWriteArrayList的算法，它在remove、add等相关操作中都是将当前elemenetData[]数组拷贝一份，也就是每次都执行数组拷贝，所以也叫
safe-fast
机制。将拷贝作为原子操作，对当前List进行控制，从而避免fail-fast问题，因为每次都是新的元素数组。
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, Serializable {
private volatile transient E[] array;
//加上synchronized保证方法的原子性，System.arraycopy保证容器的原子性
public synchronized boolean add(E paramE) {
int i = this.array.length;
Object[] arrayOfObject = (Object[])new Object[i + 1];
//拷贝操作
System.arraycopy(this.array, 0, arrayOfObject, 0, i);
arrayOfObject[i] = paramE;
this.array = arrayOfObject;
return true;
}
public synchronized E remove(int paramInt) {
int i = this.array.length;
rangeCheck(paramInt, i);
Object localObject = this.array[paramInt];
Object[] arrayOfObject = (Object[])new Object[i - 1];
//拷贝操作
System.arraycopy(this.array, 0, arrayOfObject, 0, paramInt);
int j = i - paramInt - 1;
if (j > 0)
//拷贝操作
System.arraycopy(this.array, paramInt + 1, arrayOfObject, paramInt, j);
this.array = arrayOfObject;
return localObject;
}
}
结论
List列表从结构上分为数组列表ArrayList、链表列表Linked，从线程安全性分为ArrayList和LinkedList单线程列表、Vector和Collections.SynchronizedList以及CopyOnWriteArrayList多线程列表，从检测机制分为fail-fast、safe-fast。所以，在实际的业务需求中，需要结构当前程序环境加以利用，而不会盲目选择，因为它们都具有各自的特点，例如在单线程环境中追求元素的查询可以用ArrayList，频繁更新可以用LinkedList，而需要加锁用Collections.synchronizedList(List)包装等。