ArrayList和LinkedList的区别

对于Java的容器来说，我们最常用的即是List和Map，而List中最常见的则是ArrayList和LinkedList,从他们的名字中也可以知道ArrayList是基于数组实现的list，而LinkedList则是基于链表实现的。

• 首先，我们观察源码可以发现，无论是ArrayList还是LinkedList在其内部方法上，都没有同步手段，所以，两者皆不提供线程安全性。

• 其次，在底层结构上边，ArrayList使用Object数组实现，而LinkedList使用了双向链表进行实现。由于其底层实现的不同导致了其访问，存储以及插入效率的差异化相必也是理所当然的。源码中二者关键属性定义：

  
  ArrayList存储内容的定义
  LinkedList链表头以及链表尾定义
  LinkedList节点属性定义

• 插入删除效率问题
  ArrayList底层使用Object数组实现，如果直接插入的话会在数组的末尾添加，时间复杂度即为O(1)，如果指定位置插入的话，指定位置的元素以及指定位置之后的元素则全部需要往后挪动一个位置，指定位置删除的情况类似，LinkedList使用链表存储，指定位置插入只需修改前一个节点的next为自己，插入节点的prev改为原处于该位置节点的prev，将原处于该位置的prev改为插入的节点，插入节点的next改为原处于该位置节点，指定位置删除的情况类似。所以ArrayList插入删除效率要低于LinkedList。

• 访问效率问题
  ArrayList使用数组实现，所以支持随机访问，而LinkedList不支持随机访问，指定位置访问时，LinkedList需要从头或者从尾部开始向后向前访问。

• 内存空间占用问题
  ArrayList的空间占用在于数组的初始大小，如果不是充满的数组的话，会有位置空闲，这一部分空间是浪费的，而LinkedList则是每一个节点都需要较大的空间，来存储prev以及next数据。