ArrayList与LinkedList的区别

我们在分析Java容器之间的区别时，我们也可以从继承树，底层数据结构，线程安全，执行效率来进行分析。

1.底层使用的数据结构

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

2.是否保证线程安全：

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

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

//ArrayList的插入元素的方法
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支持两端元素插入和移除。