关于LinkedList和ArrayList的remove方法的效率问题

Question

本帖最后由 LonelyCoder2012 于 2014-02-09 18:05:24 编辑

Answer 1

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

Answer 2

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

Answer 3

arraylist是基于动态数组的数据结构，linkedlist基于链表的数据结构。随机访问ArrayList效率高于linkedlist。remove操作linkelist高于arraylist，arraylist要移动数据的。这是数组的特性。

Answer 4

你测试是用的下标吧   remove(index)  这样删除中间元素一定是arraylist效率高  因为不用遍历了书上说的  应该是remove(object)这种方法  两种类型都要找元素  这样linkedlist效率就高

Answer 5

那尾部删除为什么依然是ArrayList效率高呢

Answer 6

那尾部删除为什么依然是ArrayList效率高呢尾部和中部有什么区别   ArrayList用下标没差

Answer 7

既然LinkedList位置大于一半长度从尾读起，那为什么尾部删除依然是ArrayList完胜LinkedList比如大小为1000W，操作次数1000W时，测试结果：
ArrayList尾部删除耗时：57ms
LinkedList尾部删除耗时：156ms如果是删最后一个元素，ArrayList删除只是将最后的元素置空，然后将size减少，LinkedList是进入元素所在节点，然后找到前一个节点，将前一个节点的next指向置空，ArrayList动作似乎更少可以试一下删除倒数第x个的元素，触发ArrayList数组的复制操作试验下

Answer 8

这种问题，看看源码就明了了，
ArrayList底层就是一个Object[]数组，数组都是定长的，那么ArrayList怎么实现动态变长呢，那就是在需要时（比如添加新元素，原始的数组长度不够了），创建一个新的数组，然后把原始数据和新插入的数据copy到新的数组里面，如果是删除的话，删除项后面有元素时，后面的元素都有向前移动。
LinkedList底层实现不再是Object数组，而是一个单向的带头的双向链表(LinkedList的内部类Entry)。删除元素时，只需要修改要删除项的前一个元素的next引用和后一个元素的prev引用即可。
所以在删除方面，LinkedList要比ArrayList效率高一些。
数据结构好久没看过了，大致是这个意思吧，说的不对的地方，其他同志请指正。

Answer 9

那尾部删除为什么依然是ArrayList效率高呢尾部和中部有什么区别   ArrayList用下标没差
按2楼那位仁兄的说法，LinkedList当索引超过长度一般时是从尾部开始查找的，于是LinkedList的尾部删除和中部删除当然就不一样了。

Answer 10

应该准确，测试次数我写了啊1楼的大小10W，操作次数1W；3楼的大小和操作次数都是1000W

Answer 11

代码如下，比较丑见谅： int capacity = 100000, delCount = 10000;
List<Integer> a1List = new ArrayList<Integer>(),
a2List = new ArrayList<Integer>(),
a3List = new ArrayList<Integer>(),
l1List = new LinkedList<Integer>(),
l2List = new LinkedList<Integer>(),
l3List = new LinkedList<Integer>();

for( int i = 0; i < capacity; i++ ) {
a1List.add( i );
a2List.add( i );
a3List.add( i );
l1List.add( i );
l2List.add( i );
l3List.add( i );
}

long start = 0, duration = 0;

start = System.currentTimeMillis();
for( int i = 0; i < delCount; i++ ) {
a1List.remove( capacity - i - 1 );
}
duration = System.currentTimeMillis() - start;
System.out.println( "ArrayList尾部删除耗时：" + duration + "ms");

start = System.currentTimeMillis();
for( int i = 0; i < delCount; i++ ) {
l1List.remove( capacity - i - 1 );
}
duration = System.currentTimeMillis() - start;
System.out.println( "LinkedList尾部删除耗时：" + duration + "ms");

start = System.currentTimeMillis();
for( int i = 0; i < delCount; i++ ) {
a2List.remove( ( capacity - i - 1 ) / 2 );
}
duration = System.currentTimeMillis() - start;
System.out.println( "ArrayList中部删除耗时：" + duration + "ms" );

start = System.currentTimeMillis();
for( int i = 0; i < delCount; i++ ) {
l2List.remove( ( capacity - i -1 ) / 2 );
}
duration = System.currentTimeMillis() - start;
System.out.println( "LinkedList中部删除耗时：" + duration + "ms" );

start = System.currentTimeMillis();
for( int i = 0; i < delCount; i++ ) {
a3List.remove( 0 );
}
duration = System.currentTimeMillis() - start;
System.out.println( "ArrayList首部删除耗时：" + duration + "ms" );

start = System.currentTimeMillis();
for( int i = 0; i < delCount; i++ ) {
l3List.remove( 0 );
}
duration = System.currentTimeMillis() - start;
System.out.println( "LinkedList首部删除耗时：" + duration + "ms" );

Answer 12

既然LinkedList位置大于一半长度从尾读起，那为什么尾部删除依然是ArrayList完胜LinkedList比如大小为1000W，操作次数1000W时，测试结果：
ArrayList尾部删除耗时：57ms
LinkedList尾部删除耗时：156ms如果是删最后一个元素，ArrayList删除只是将最后的元素置空，然后将size减少，LinkedList是进入元素所在节点，然后找到前一个节点，将前一个节点的next指向置空，ArrayList动作似乎更少可以试一下删除倒数第x个的元素，触发ArrayList数组的复制操作试验下

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

Answer 13

既然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优势就很明显了对于不同情况采取不同策略才是正道。

Answer 14

LinkedList基于双向链表 你用的好像是remove(index)

Answer 15

看了你的代码，仔细想了一下，应该是这样的。
删除尾部时，array和link差不多，都很快，是因为array不用移动元素，link可以直接定位到尾部，然后删除。
删除中部时，array比较慢，link非常慢，array每次删除需要移动一半的元素，link定位耗时相当大（每次都要重新定位到中部），由此可见，数据量较大时，定位的开销比移动元素的开销大的多。
删除首部时，array较慢，link很快，array每次删除都要移动所有的元素，而link可以直接定位到首部，直接删除。

Answer 16

希望你能搞清楚  你只比较remove的性能   前提是要保证公平用下标  本身就不公平  因为这涉及到random access性能如果你用remove对象  才叫公平  因为都要从头开始找另外你list中没有重复元素  这是测试缺陷  你没有考虑这个问题另外你集合中的元素是Integer  也有问题   移动int元素  时间是可以忽略的应该在集合里放一些大对象  这样才能比较真实的性能另外  你的内存情况也显得不足  因为你现在是内存充足的情况  所以很容易找到连续空间综上  这是个失败的测试  这两种数据结构的特点  不是你能质疑的