黑马程序员技术交流社区

标题: 集合的问题 [打印本页]

作者: 唐进 时间: 2012-10-21 15:35
标题: 集合的问题
去面试的时候别人问我LinkedList和ArrayList性能上有什么不同，求高手指点！

作者: 给生活加点料 时间: 2012-10-21 15:43
LinkedList 内部是链表，不同步，增删快，查询慢。
ArrayList 内部是数组，不同步，增删慢，查询快。
希望你记住，面试经常问。但愿有所帮助。

作者: 李建强 时间: 2012-10-21 15:53
这个问题很常见。
LinkeedList底层是链表
ArrayList底层是数组

对于随机访问set和get，ArrayList效率高，
因为LinkeedList要移动指针。
而ArrayList直接访问元素。

对于增加和删除，LinkeedList效率高，
因为ArrayList要移动数据。
而LinkeedList增加和删除耗费的时间基本固定

最后，凡事无绝对，
数据添加在后面的时候，并且需要随机访问时，ArrayList比较合适。
数据添加在前面或中间，并且顺序访问时，LinkeedList比较合适。
一般ArrayList常见。

我希望我面试的时候也被问这个问题。

作者: 杨千里 时间: 2012-10-21 16:22
毕老师的原话：|--ArrayList：底层数据结构是数组数据结构，特点：查询速度很快，增删稍慢，线程不同步
|--LinkedList：底层数据结构是链表数据结构，特点：增删速度很快，查询稍慢

作者: 草上飞 时间: 2012-10-21 21:20
今天看一框架的代码，看到有些可以使用ArrayList的地方使用的是 LinkedList，用到的情景是在一个循环里面进行顺序的插入操作。

众所周知java里面List接口有两个实现ArrayList 和 LinkedList，他们的实现原理分别是数组和链表。

正如学习数据结构时的认识，对于插入操作，链表的结构更高效，原因是可以通过修改节点的指针就可以完成插入操作，而不像数组，

需要把插入位置之后的数组元素依次后移。

下面通过一个例子来证明
public static void main(String[] args) {
      List<String> arrayList = new ArrayList<String>(); //实例一个数组
      List<String> linkedList = new LinkedList<String>(); //实例一个链表
      long time1 = System.currentTimeMillis(); //获取数组开始创建时间
      for(int i = 0; i < 1000000; i++) {
         arrayList.add(new String("abc"));
      }
      long time2 = System.currentTimeMillis(); //获取数组结束创建的时间，同时又将这个时间设置为链表开始创建的时间
      for(int i = 0; i < 1000000; i++) {
         linkedList.add(new String("abc"));
      }
      long time3 = System.currentTimeMillis(); //获取链表创建结束的时间
      System.out.println("arrayList.insert_time = " + (time2 - time1)); //数组创建的时间
      System.out.println("linkedList.insert_time = " + (time3 - time2)); //链表创建的时间
      long time11 = System.currentTimeMillis(); //获取数组开始读取的时间
      for(int i = 0; i < 10000; i++) {
         int random = RandomUtils.nextInt(10000);
         String temp = arrayList.get(random);
      }
      long time12 = System.currentTimeMillis(); //获取数组结束读取的时间，同时又是链表读取开始的时间

      for(int i = 0; i < 10000; i++) {
         int random = RandomUtils.nextInt(10000);
         String temp = linkedList.get(random); //获取链表结束读取的时间

      }
      long time13 = System.currentTimeMillis();
      System.out.println("arrayList.read_time = " + (time12 - time11)); //数组读取的时间
      System.out.println("linkedList.read_time = " + (time13 - time12)); //链表读取的时间
}

运行结果：

?arrayList.insert_time = 188 //数组创建的时间
linkedList.insert_time = 250 //链表创建的时间
arrayList.read_time = 16 //数组读取的时间
linkedList.read_time = 234 //链表读取的时间

通过结果可以看出：无论什么情况，ArrayList更加高效。尤其对于随机读取，数组的效率是链表的14倍之多。

而插入操作，两者用时相差不多，但是还是数组的实现效率高一些。

对于其中原因，仔细想想也不难想明白。

当List存储的内容不多时，写入List的最后的元素，ArrayList和LinkedList用时差不多。

但是当List存储的元素个数很大时，通过数组结构实现的ArrayList插入到最后可以通过数组下标很快访问到，但是LinkedList就需要访问每个节点直到找到最后的元素再进行插入操作，
这中操作步骤的耗时是巨大的，所以列表数量越大，LinkedList就越感吃力了。

当然，对于要求随机插入的场景，这个时候LinkedList就要比ArrayList适合了。

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

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