Question

ArrayList和LinkedList到底哪一个插入效率更高？

Answer 1

说到ArrayList和LinkedList我们不得不放出下面的这张图来帮助我们更好的了解他们的区别。

从图中我们已经可以看出他们的区别了

ArrayList是顺序结构，所以定位很快，我们可以根据下标可以很容易的找到我们的想要的位置，但在插入数据时我们要移动后边的所有数据，所以插入数据很慢。
而LinkedList 是链表结构，像串起来的珠子，我们只能一个个的顺着那条虚拟的线去找，虽然不能快速的查找，但是插入数据的时候只需要更改相应位置前后的连接，所以插入数据很快。

这时候大部分人会想当然的说LinkedList的插入效率比ArrayList的要高，因为LinkedList是基于链表的，插入元素时只要改变一下指针指向的位置就可以了。

要说得出这样的结论有错吗？说实在的，这样考虑没有错，但是当我们把插入这个步骤在一次细分， 插入=定位+添加元素 ，现在我想你已经觉得上边得出的结论考虑不全面了吧。

ArrayList 定位快 添加元素需要以后之后的数据
LinkedList 定位慢 添加元素只需更改前后指定位置

现在你还有比较两个快慢的依据吗？

这时候我们就要考虑影响定位和添加的共同因素--插入的位置

当我们向第一位插入时，我们的定位基本相同，由于ArrayList需要移动之后的所有数据，所以相对就慢了很多。

如下所示

对于在最后的插入快慢保持怀疑态度，按理说应该是相差无几的，毕竟定位快慢相差无几，插入后均不需要操作其他数据。所以会有ArrayList快于LinkedList或者ArrayList慢于LinkedList的两种结果，有知道原因的望指出。