关于LinkedList和ArrayList的remove方法的效率问题
以前一直信奉教科书上的一句话，链表元素删除只涉及指针变动，数组元素删除涉及到元素移动，所以链表元素删除速度比数组元素快。

今天发现貌似没理解对，如果要删除的元素是已知索引且该索引是随机给定的，那么：
对于链表：
要先迭代寻址，再修改指针；
对于数组：
直接删除索引处元素，移动后续元素。

此外，经我测试，对于同样大小的ArrayList和LinkedList，如果进行相同次数的删除操作，那么从尾部删除和从中部删除ArrayList的效率更高，从首部删除则是LinkedList效率更高。
附上大小为100000，操作次数10000的测试结果：
ArrayList尾部删除耗时：1ms
LinkedList尾部删除耗时：4ms
ArrayList中部删除耗时：91ms
LinkedList中部删除耗时：13191ms
ArrayList首部删除耗时：211ms
LinkedList首部删除耗时：2ms
为什么中部删除效率差别这么夸张，甚至比尾部删除还大？

这样看来似乎教科书上那句话就不是绝对的了，在选择ArrayList还是LinkedList效率高这个问题上，决定性因素好像应该是待删除的元素在整个集合中是什么位置，而不是见到remove操作就选择LinkedList，不知我的理解是否正确？

能不能请各位帮我从底层分析一下这个现象产生的原因？我在寻址、移动元素在硬件层面所涉及到的操作概念比较模糊。据说相邻内存空间数据移动很快？
------解决方案--------------------

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

LinkedList遇上你这种随机索引是要吐血的啊，又不是数组存储不可以randomAccess，只能一个一个读下去
中部最耗时的原因你可以看jdk源码，位置小于一般长度从头读起大于一半长度从尾读起，自然最费时是读到中间

既然LinkedList位置大于一半长度从尾读起，那为什么尾部删除依然是ArrayList完胜LinkedList。。。比如大小为1000W，操作次数1000W时，测试结果：
ArrayList尾部删除耗时：57ms
LinkedList尾部删除耗时：156ms

如果是删最后一个元素，ArrayList删除只是将最后的元素置空，然后将size减少，LinkedList是进入元素所在节点，然后找到前一个节点，将前一个节点的next指向置空，ArrayList动作似乎更少

可以试一下删除倒数第x个的元素，触发ArrayList数组的复制操作试验下

我是楼主。。。上面三连了回复不了。。。

试了一下，我发现LinkedList遍历耗时要比ArrayList数组复制耗时要多得多。。。据我估计，LinkedList删除效率比ArrayList高的索引阀值应该是小于总数的一半的某个值，只有索引比这个阀值小的时候，LinkedList的删除操作效率才有优势。。。前提是都是随机访问。。。
请指正！

LinkedList对于随机访问本身就弱
ArrayList的内部数组是一个native method，不同架构效率可能不同
不一定和size一半有关系

楼上有个楼都说了，LinkedList删除快针对于remove(Object o)的情况，此情况下两种List都要遍历后才可以删除，LinkedList优势就很明显了

对于不同情况采取不同策略才是正道。