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

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

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

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

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

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

使用方法如下

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

final Object mutex;

SynchronizedCollection(Collection<E> c) {

this.c = Objects.requireNonNull(c);

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

}

synchronized (mutex) {

抛出异常的根本原因在于for-each是使用Iterator来实现遍历的，调用ArrayList.remove()方法会将modCount+1，而Iterator内部的expectedModCount确没有更新，这样在进行下次循环时调用Iterator.next()会对modCount和expectedModCount进行比较，不一致就会抛出ConcurrentModificationException异常。

可以看到下面Itr的源码中，在Itr.remove()方法中删除元素后会对 expectedModCount更新，所以我们在使用删除元素时使用Itr.remove()方法来删除元素就可以保证expectedModCount的更新了，具体看**第5种**方法。

public void tranverse() {

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

list.add(1);

list.add(2);

list.add(3);

list.add(3);

list.add(4);

list.add(5);

Iterator<Integer> iterator = list.iterator();

while (iterator.hasNext()) {

Integer value = iterator.next();

System.out.println(value);

if (value.equals(3)) {

iterator.remove();

iterator.remove();//在循环中多次调用iterator的remove方法会抛出异常

iterator.remove();

}

}

}

**Iterator的源代码**

第4种方法其实是第3种方法在编译后的代码，所以第四种写法也会抛出ConcurrentModificationException异常。这种需要注意的是，每次调用iterator的next()方法，会导致游标向右移动，从而达到遍历的目的。所以在单次循环中不能多次调用next()方法，不然会导致每次循环时跳过一些元素，我在一些博客里面看到了一些错误的写法，比如这一篇[《在ArrayList的循环中删除元素，会不会出现问题？》](https://juejin.im/post/5b92844a6fb9a05d290ed46c)文章中：