每次遇到一个好看的小姐姐，我们一般都是会去看她的外貌，身材，大小(咳咳，我们指的是年龄大小)等等。同样的，我们在分析Java容器之间的区别时，我们也可以从继承树，底层数据结构，线程安全，执行效率来进行分析。

#### 1.底层使用的数据结构

* Arraylist 底层使用的是**Object数组**，初始化时就会指向的会是一个static修饰的空数组，数组长度一开始为**0**，插入第一个元素时数组长度会初始化为**10**，之后每次数组空间不够进行扩容时都是增加为原来的**1.5倍**。ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间(为了避免添加元素时，数组空间不够频繁申请内存)，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放后继指针next和前驱指针pre以及数据）

* LinkedList 底层使用的数据结构是**双向链表**，每个节点保存了指向前驱节点和后继结点的指针。初始化时，不执行任何操作，添加第一个元素时，再去构造链表中的节点。

#### 2.是否保证线程安全：

ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。

因为ArrayList的插入元素的方法就是裸奔的，直接将原数组index及后面的元素拷贝到index+1及后面的位置上，然后将index位置设置为插入的值，并发修改时保证不了数据安全性，所以也不允许并发修改，一旦检测到并发修改，会抛出ConcurrentModificationException异常。

```java

public void add(int index, E element) {

rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!

System.arraycopy(elementData, index, elementData, index + 1,

size - index);//将原数组index之后的元素拷贝到原数组index+1后面的位置上

elementData[index] = element;

size++;

}

```

#### 3.插入和删除的复杂度：

* ArrayList 采用数组存储，元素的物理存储地址是连续的，支持以O(1)的时间复杂度对元素快速访问。插入和删除元素后，需要将后面的元素进行移动，所以插入和删除元素的时间复杂度受元素位置的影响。复杂度是 O(n)，

* LinkedList 采用链表存储，所以不能快速随机访问。所以首尾插入，删除元素时间复杂度不受元素位置的影响，都是近似 O(1)(如果是插入到中间位置还需要考虑寻找插入位置的时间复杂度)。而数组为近似 O(n)。

#### 4.继承树

* ArrayList继承于AbstractList抽象类，实现了**List, RandomAccess, Cloneable, java.io.Serializable**接口 。

* LinkedList继承自AbstractSequentialList 实现**List, Deque, Cloneable, java.io.Serializable**接口。

**AbstractSequentialList**是AbstractList类的子类，实现了根据下标来访问元素的一些方法，主要是通过listIterator遍历获取特定元素。

**List接口**代表的是有序结合，与Set相反，List的元素是按照移动的顺序进行排列。

**Cloneable接口**代表类会重新父类Object的clone()方法，支持对实例对象的clone操作。

**java.io.Serializable**接口代表类支持序列化。

**RandomAccess**是一个标示性接口，代表ArrayList支持快速访问，而LinkedList不支持。

**Deque**接口是双端队列的意思，代表LinkedList支持两端元素插入和移除。

#### 1.使用SynchronizedList

SynchronizedList是一个线程安全的包装类。继承于SynchronizedCollection，SynchronizedCollection实现了Collection接口，SynchronizedList包含一个List对象，对List的访问修改方法进行了一些封装，在封装的方法中会对list使用同步锁加锁，然后再进行存取和修改操作。

```java

LinkedList<Integer> linkedList = new LinkedList<Integer>();

List<Integer> synchronizedList = Collections.synchronizedList(linkedList);

ArrayList<Integer> arrayList = new ArrayList<Integer>();

List<Integer> synchronizedRandomAccessList = Collections.synchronizedList(linkedList);

```

(Collections.synchronizedList()方法会判断传入的对象是否实现了 RandomAccess接口，是的话，会返回一个SynchronizedRandomAccessList对象，SynchronizedRandomAccessList是SynchronizedList的子类，只是会多一个以线程安全的方式获取子数组的方法)。

SynchronizedList类的部分代码如下：

```java

static class SynchronizedList<E>

extends SynchronizedCollection<E>

implements List<E> {

final List<E> list;//源list

final Object mutex;

SynchronizedCollection(Collection<E> c) {

this.c = Objects.requireNonNull(c);

mutex = this;//mutex就是SynchronizedList实例自己，作为同步锁使用

}

public E get(int index) {

synchronized (mutex) {

是父类中的成员变量，在父类中会将list赋值给mutex

return list.get(index);

}

}

public E set(int index, E element) {

synchronized (mutex) {return list.set(index, element);}

}

}

```

#### 2.使用CopyOnWriteArrayList

CopyOnWriteArrayList跟ArrayList类似，都是实现了List接口，只不过它的父类是Object，而不是AbstractList。CopyOnWriteArrayList与ArrayList的不同在于，

##### 1.内部持有一个ReentrantLock类型的lock锁，用于控制并发访问

```java

final transient ReentrantLock lock = new ReentrantLock();

```

在对数组进行修改的方法中，都会先获取lock，获取成功才能进行修改，修改完释放锁，保证每次只允许一个线程对数组进行修改。

##### 2.使用volatile修饰Object数组，使得变量具备内存可见性

```java

//CopyOnWriteArrayList

private transient volatile Object[] array;

//ArrayList

private transient Object[] elementData;//transient

```

可以看到区别主要在于CopyOnWriteArrayList的Object是使用volatile来修饰的，volatile可以使变量具备内存可见性，一个线程在工作内存中对变量进行修改后，会立即更新到物理内存，并且使得其他线程中的这个变量缓存失效，其他线程在读取会去物理内存中读取最新的值。（volatile修饰的是指向数组的引用变量，所以对数组添加元素，删除元素不会改变引用，只有对数组变量array重新赋值才会改变。所以为了保证内存可见性，CopyOnWriteArrayList.add()方法在添加元素时，都是复制出一个新数组，进行修改操作后，再设置到就数组上）

注意事项:Object数组都使用transient修饰是**因为transient修饰的属性不会参与序列化**，ArrayList通过实现writeObject()和readObject()方法来自定义了序列化方法(基于反序列化时节约空间考虑，如果用默认的序列方法，源elementData数组长度为100，实际只有10个元素，反序列化时也会分配长度为100的数组，造成内存浪费。)

**下面是CopyOnWriteArrayList的add()方法:**

```java

public boolean add(E e) {

final ReentrantLock lock = this.lock;

//1. 使用Lock,保证写线程在同一时刻只有一个

lock.lock();

try {

//2. 获取旧数组引用

Object[] elements = getArray();

int len = elements.length;

//3. 创建新的数组，并将旧数组的数据复制到新数组中

Object[] newElements = Arrays.copyOf(elements, len + 1);

//4. 往新数组中添加新的数据

newElements[len] = e;

//5. 将旧数组引用指向新的数组

setArray(newElements);

return true;

} finally {

lock.unlock();

}

}

```

#### SynchronizedList和CopyOnWriteArrayList优缺点

##### SynchronizedList:读写都加锁

SynchronizedList是通过对读写方法使用synchronized修饰来实现同步的，即便只是多个线程在读数据，也不能进行，如果是读比较多的场景下，会性能不高，所以适合读写均匀的情况。

##### CopyOnWriteArrayList:读不加锁，写加锁

而CopyOnWriteArrayList是读写分离的，只对写操作加锁，但是每次写操作(添加和删除元素等)时都会复制出一个新数组，完成修改后，然后将新数组设置到旧数组的引用上，所以在写比较多的情况下，会有很大的性能开销，所以适合读比较多的应用场景。

首先结论如下：

第1种方法 - 普通for循环正序删除（结果：会漏掉元素判断）

第2种方法 - 普通for循环倒序删除（结果：正确删除）

第3种方法 - for-each循环删除（结果：抛出异常）

第4种方法 - Iterator遍历，使用ArrayList.remove()删除元素（结果：抛出异常）

第5种方法 - Iterator遍历，使用Iterator的remove删除元素（结果：正确删除）

下面让我们来详细探究一下原因吧！

首先初始化一个数组arrayList，假设我们要删除等于3的元素。

```java

public static void main(String[] args) {

ArrayList<Integer> arrayList = new ArrayList();

arrayList.add(1);

arrayList.add(2);

arrayList.add(3);

arrayList.add(3);

arrayList.add(4);

arrayList.add(5);

removeWayOne(arrayList);

}

```

#### 第1种方法 - 普通for循环正序删除（结果：会漏掉对后一个元素的判断）

```java

for (int i = 0; i < arrayList.size(); i++) {

if (arrayList.get(i) == 3) {//3是要删除的元素

arrayList.remove(i);

//解决方案: 加一行代码i = i - 1; 删除元素后，下标减1

}

System.out.println("当前arrayList是"+arrayList.toString());

一些集合（例如Collection, Vector, ArrayList，LinkedList, HashSet, Hashtable, TreeMap, AbstractList, Serialized Form）的Iterator实现中，如果提供这种并发修改异常检测，那么这些Iterator可以称为是"fail-fast Iterator"，意思是快速失败迭代器，就是检测到并发修改时，直接抛出异常，而不是继续执行，等到获取到一些错误值时在抛出异常。

异常检测主要是通过modCount和expectedModCount两个变量来实现的，

- modCount

集合被修改的次数，一般是被集合(ArrayList之类的)持有，每次调用add()，remove()方法会导致modCount+1

- expectedModCount

期待的modCount，一般是被Iterator(ArrayList.iterator()方法返回的iterator对象)持有，一般在Iterator初始化时会赋初始值，在调用Iterator的remove()方法时会对expectedModCount进行更新。（可以看看上面的ArrayList.Itr源码）

然后在Iterator调用next()遍历元素时，会调用checkForComodification()方法比较modCount和expectedModCount，不一致就抛出ConcurrentModificationException。

单线程操作Iterator不当时也会抛出ConcurrentModificationException异常。（上面的例子就是）

#### 总结

因为ArrayList和HashMap的Iterator都是上面所说的“fail-fast Iterator”，Iterator在获取下一个元素，删除元素时，都会比较expectedModCount和modCount，不一致就会抛出异常。

所以当使用Iterator遍历元素(for-each遍历底层实现也是Iterator)时，需要删除元素，一定需要使用 **Iterator的remove()方法** 来删除，而不是直接调用ArrayList或HashMap自身的remove()方法,否则会导致Iterator中的expectedModCount没有及时更新，之后获取下一个元素或者删除元素时，expectedModCount和modCount不一致，然后抛出ConcurrentModificationException异常。


大致是这样一个图，Collection是一个接口，代表是集合，它有三个子接口，分别是有序集合List，队列Queue，无序集合Set。Map代表键值对。实际上关系会更加复杂一些，以ArrayList为例：

ArrayList不单是实现了List接口，而且还继承于AbstractList抽象类，同时实现了RandomAccess，Cloneable，Serializable接口。

HashMap不单是实现了Map接口，而且继承于AbstractMap抽象类，同时实现了Cloneable，Serializable接口。