黑马程序员技术交流社区

标题: 关于ArrayList和LinkedList添加删除操作的速度比较 [打印本页]

作者: 依然超级赛亚人 时间: 2014-8-24 07:08
标题: 关于ArrayList和LinkedList添加删除操作的速度比较
本帖最后由依然超级赛亚人于 2014-8-24 07:10 编辑

有一道关于ArrayList和LinkedList添加以及删除操作的速度比较问题真是颠覆了我的认知。记得学的是ArrayList添加和删除都比LinkedList慢，可是我写了下面这段程序测试，结果却出人意料，和预想正好一个相反的结果。我也知道那两三个技术分不是这么轻易就能得到的，但是我确实搞不懂这里的原理了。之前在其它版块发布过这个帖子，但是无人问津真无奈。所以想，“黑马币之下必有勇夫”，希望大神们给与解答。

/*
通过编码分别测试ArrayList 和 LinkedList 添加、删除对象时的耗时情况（精确到纳秒），
并总结出以上两种集合的数据结构的不同之处。
*/
import java.util.*;
class ListTest00
{
public static void main(String[] args)
{
//先测试ArrayList添加，删除操作的耗时情况。
ArrayList<String> array = new ArrayList<String>();
long begin = System.nanoTime();//标记起始时间
array.add("javaEE01");
array.add("javaEE02");
array.add(1,"javaEE03");//插入元素，其他均为添加元素
array.add("javaEE04");
array.add("javaEE05");
long end = System.nanoTime();//标记终止时间
System.out.println("ArrayList集合添加操作耗时为："+(end-begin)+"纳秒");
long begin1 = System.nanoTime();
array.clear();//删除操作。
long end1 = System.nanoTime();
System.out.println("ArrayList集合删除操作耗时为："+(end1-begin1)+"纳秒");

复制代码

作者: 胥亮 时间: 2014-8-24 07:08
ArrayList底层的实现是数组，所以用下标访问的速度比较快，但是插入和删除元素，会有移动元素的开销，所以速度比LinkedList差。LikedList底层是链表实现的，所以插入和删除元素时间复杂度较LinkedList好，但是随即访问需要遍历元素，所以效率比ArrayList差。
这里有个帖子是用1000个元素做的测试你看看http://blog.csdn.net/it_wangxiangpan/article/details/8693803

作者: 胥亮 时间: 2014-8-24 08:11
集合里面的元素太少了比较不出来如果是1000个以上就看看出来了你这个才5个元素

作者: 依然超级赛亚人 时间: 2014-8-24 08:13

胥亮发表于 2014-8-24 08:11
集合里面的元素太少了比较不出来如果是1000个以上就看看出来了你这个才5个元素 ...

果真是元素个数问题吗？当时讲这块知识的时候应该没有讲有这个条件的限制啊？难道是我没记住？

作者: wzningjie 时间: 2014-8-24 09:20
ArryList只是查找快，下标直接查找，时间复杂度为O(1)，而插入删除时间复杂度为O(n)。
然而LinkedLis是链表实现的，所以查找必须从头查找时间复杂度为O(n)，而插入删除只需要在查找到的情况下一步就能完成插入删除，时间复杂度为O(1)。
再说了，你就这几个数据根本测不出来，你试试1000个数据，甚至10000个数据就会很明显。

作者: wzningjie 时间: 2014-8-24 09:22
数据量太小有偶然性

作者: 依然超级赛亚人 时间: 2014-8-24 10:15

胥亮发表于 2014-8-24 08:24
ArrayList底层的实现是数组，所以用下标访问的速度比较快，但是插入和删除元素，会有移动元素的开销，所以 ...

经过大家的指点，我通过反复尝试暂时得出一个结论：单纯添加（add）和删除（clear）来说，ArrayList比LinkedList好太多，因为只是顺序的链接与删除；无序的插入（add(int index,element)）和删除（remove(int index)）LinkedList在一定数量以后比ArrayList强，而且是元素越多（最好千的级别以上），顺序越乱，越没有规律性可言就越有优势。
我之前也知道论插入，LinkedList好。但是我就是认为在所有添加（包括插入）与删除的情况下（不分数量）总是LinkedList有优势，现在看来是有条件限制的，这不免让我对LinkedList的看法有了一点“鄙视”，呵呵。

作者: dreamseekerkun 时间: 2014-8-24 10:33
巩固学习了，加深理解。

作者: 0小菜鸟0 时间: 2014-8-24 17:58
ArrayList是增删慢，查询快，底下是由数组实现，就是增删的时候开辟一个长度适合的数组赋值过去，主要是开辟空间浪费了时间，元素少当然不觉的，在以后的项目中，成千上万的数据，那时候就有明显的效果了

作者: 夜半风 时间: 2014-8-24 20:27
linkedlist相当于数据结构里面的单链表，删除添加只要移动指针就行了，比较快，查询的话是要从头查到尾直到找到为止，查询比较慢。Arraylist呢，底层运用的是数组，数据越多增删操作越慢，因为要移动数据，但是其查询起来很快。在数据较少的情况下两者的效率比较并不明显，数据多了以后相差会很大

作者: 依然超级赛亚人 时间: 2014-8-25 06:31

0小菜鸟0 发表于 2014-8-24 17:58
ArrayList是增删慢，查询快，底下是由数组实现，就是增删的时候开辟一个长度适合的数组赋值过去，主要是开 ...

OK，了解！:handshake

作者: 依然超级赛亚人 时间: 2014-8-25 06:33

夜半风发表于 2014-8-24 20:27
linkedlist相当于数据结构里面的单链表，删除添加只要移动指针就行了，比较快，查询的话是要从头查到尾直到 ...

说的很对，之前一直以为没那么多限制，以为什么情况下的增删都是LinkedList快，现在了然了！

作者: 夜半风 时间: 2014-8-25 10:50

依然超级赛亚人发表于 2014-8-25 06:33
说的很对，之前一直以为没那么多限制，以为什么情况下的增删都是LinkedList快，现在了然了！ ...

了然了就好

作者: hi2hcs 时间: 2014-8-27 17:22
学习了！！！

作者: 宇渊 时间: 2014-10-12 18:51
学习了!是个不错的帖子！:D

作者: Mr.JUN 时间: 2014-11-4 14:18
ArrayList每次增或删除时，都会新创建一个数组不？

作者: 依然超级赛亚人 时间: 2014-11-11 20:39

Mr.JUN 发表于 2014-11-4 14:18
ArrayList每次增或删除时，都会新创建一个数组不？

这个问题提得好，但是我不是很清楚，可以研究一下。ArrayList的底层是数组，数组的长度是不可变的，进行增删这种改变数组长度的操作的话估计会创建新数组，这只是我个人的想法，你还是找些资料看看吧！

作者: 小马范 时间: 2014-12-8 20:09
ArrayList 插入和删除元素会有移动下标的开销，数据越多，开销越大

作者: 小马范 时间: 2014-12-8 20:12
ArrayList 插入和删除元素会有移动下标的开销，数据越多，开销越大

作者: 菜鸟学徒 时间: 2016-1-6 19:12
赞。。。。。。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2