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

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

复制代码

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

集合里面的元素太少了  比较不出来  如果是1000个以上就看看出来了   你这个才5个元素   

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

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

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

数据量太小有偶然性

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

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

巩固学习了，加深理解。

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

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

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

OK，了解！:handshake

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

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

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

了然了就好

学习了！！！

学习了!是个不错的帖子！:D

ArrayList每次增或删除时，都会新创建一个数组不？

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

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

ArrayList 插入和删除元素会有移动下标的开销，数据越多，开销越大

ArrayList 插入和删除元素会有移动下标的开销，数据越多，开销越大

赞。。。。。。