ArrayList和LinkedList区别

对于这两种数据结构的基础比较，如，线程安全问题、底层结构，空间占用问题我就不多说了，网上很多文档写的很清楚了，这里我详细的讲下自己对ArrayList和LinkedList在数据的查询，增加，删除和修改上的性能差异：

要分析在三种情况下的差异，首先要清楚两种容器它的底层实现是什么，ArrayList底层是数组实现的，连续的地址内存空间，也就是带索引；LinkedList底层是双向链表，不是连续的内存空间，而且双向链表的每个节点都存放前驱，当前，后继节点信息。

查询：一般就两种查询，查询某索引的元素和查询某元素的索引，比如查询第N个索引下的元素，这个毫无疑问是ArrayList快，因为它底层是数组，支持快速随机访问，时间复杂度是O(1)，LinkedList不是连续的，只能一个接着一个的去找，时间复杂度是O(n)。对于查询某元素的索引，两种容器就只能遍历了，效率是差不多的
插入，也分插入的位置，是头部，是中间，是末尾？此时ArrayList的连续的内存地址这个特点就变成劣势了，当插入到头部和中间部分，Arraylist就需要数组的copy或者扩容，效率是很低的，但插入到尾部，就可以直接插入（不考虑扩容）。对于LinkedList我想有数据结构基础的朋友都会直到每个节点的所存储的数据是什么，插入头部或者中部只需要修改下待插入节点的前驱和后继即可，插入尾部也只需直接插入即可，时间复杂度是O(1)。所以在插入的位置是头部和中部是，LinkedList凭借自身存储数据的特点拥有绝对的优势，在插入到尾部时两者性能差不多。
修改，我只讨论按索引修改的，不管位置如何对于ArrayList可以直接根据索引修改元素值。但对于LinkedList维护了首尾指针，修改首位时间复杂度是O(1)，对于中间的需要是用二分查找实现的，时间复杂度是O(logn)
删除：当删除指定索引的元素或者指定元素时，两者差别和插入类似，对于删除指定的索引元素在头部或者在中部，ArrayList就需要进行数组的迁移，时间复杂度和空间复杂度都很高，但删除指定的索引在末尾，就直接置空就行了。对于LinkedList需要遍历找到目标值，在修改前后的前驱和后继，但总体效率高于ArrayList，而且它维护了头尾指针，对于删除头尾的是很快的。

总的来说，ArrayList由于底层是数组，所以查询快，但删除和插入慢。LinkedList是双向链表，查询慢，但删除和插入快。修改两者差异不大。

单线程下对ArralList进行删除操作抛出并发修改异常分析

单线程下可能很多人无法想象为什么也会抛出并发修改异常，使用list.remove(object)就会抛出该异常，所以当单线程需要删除元素时需要用迭代器的remove方法，二者的差异在哪？深入源码发现，抛出异常的条件是modCount和expectCount不相等，我们需要记住这个条件！点开Arraylist的remove发现它调用的是fastRemove，一进去就直接把modCount++，然后进行删除操作，直接把expectedCount挂一遍了，不抛异常才奇怪呢

接着进入迭代器的remove方法，发现它是先调用的Arraylist.remove，从上面我们就知道此时modCount肯定自增了，但接下来就把进行了expected = modcount的操作，这就实现了两者相等，不抛出异常了。