ArrayList内部是使用可増长数组实现的,所以是用get和set方法是花费常数时间的,但是如果插入元素和删除元素,除非插入和删除的位置都在表末尾,否则代码开销会很大,因为里面需要数组的移动。
LinkedList是使用双链表实现的,所以get会非常消耗资源,除非位置离头部很近。但是插入和删除元素花费常数时间。
我们来看下面一个例子:
public void listTest1(List<Integer> list, int n) { list.clear(); for (int i=0; i<n; i++) { list.add(i); } }
上面这个例子,不论是ArrayList还是LinkedList运行的时间都是O(N),因为每次的操作都是在表末尾进行的。如果我们把add方法换成下面的呢!
list.add(0, i);
该完之后,对于LinkedList运行时间是O(N),但是对于ArrayList则是O(N^2),一位每次添加都需要移动数组,运行时间是O(N)
再看看下面的这个例子:计算list中数据之和
public int listSum(List<Integer> list) { int sum = 0; for (int i=0; i<list.size(); i++) { sum += list.get(i); } return sum; }
这个例子对于ArrayList运行时间是O(N),但是对于LinkedList运行时间就是O(N^2),但是如果我们使用增强for循环,那么就会不一样。代码如下:
public int listSum2(List<Integer> list) { int sum = 0; for (Integer i: list) { sum += i; } return sum; }
这样无论是ArrayList和LinkedList其运行时间都是O(N),因为迭代器会有效的从一项到下一项推进。
下面我们说一个remove方法
问题:将一个表中的所有偶数项全部删除,要求不能创建新表。
最简单的就是,进行for遍历,然后取出数值判断是否是偶数,如果是就删除,代码如下:
public static void removeEvensOne(List<Integer> list) { for (int i=0; i<list.size(); i++) { if (list.get(i) % 2 == 0) { list.remove(i); //移除的是i位置上的元素 } } }
我们来分析一下,如果传入的参数是Arraylist,那么效率一定会很低,我做了一下测试,创建一个400000项的ArrayList,程序运行时间大约是16s。想着如果传入的是LinkedList是否会很快,答案是否!对于LinkedList运行时间至少要一分多钟,这就奇怪了LinkedList不是删除操作是常数时间吗。我们仔细看看这里面需最消耗时间的是list.get(i)和list.remove(i),首先对于LinkedList的get()操作时间复杂度是O(N),对于remove(i)时间,LinkedList需要到达位置i,那么如何到达,只能是从第一个元素一直搜索下去,其时间复杂读也是O(N),所以对于这个程序LinkedList消耗的时间要比ArrayList多的多。
既然用for循环需要.get(i),那我们使用增强for循环好了,代码如下:
public static void removeEvensThree(List<Integer> list) { for (Integer i: list) { if (i%2 == 0) { list.remove(i); //移除的是元素i } } }
运行一下,抛出异常java.util.ConcurrentModificationException。也就是说list.remove()破坏了增强for循环,这个方法不行,但是它给了我们一个思路:在迭代器找到一个偶数时,我们可以使用迭代器来删除这个偶数值。我们使用Iterator迭代器,代码如下:
public static void removeEvensTwo(List<Integer> list) { Iterator<Integer> it = list.iterator(); while (it.hasNext()) { if (it.next() % 2 == 0) { it.remove(); } } }
这个代码中我们不需要查找,还是使用400000个元素的list进行测试,ArrayList没有什么变化,时间依然是16s,这是因为即使迭代器位于要删除的节点上,删除之后元素还是要移动。对于LinkedList花费的时间小于1s。
从上面我们可以看出:ArrayList虽然get和set快,但是remove却很慢。对于LinkedList虽然删除和插入很快,但是如果期间使用了get那么一样会很慢。如果是有大量的删除操作我们还是使用Iterator迭代器比较好。
相关推荐
1.List是接口类,ArrayList和LinkedList是List的实现类 2.ArrayList是动态数组(顺序表)的数据结构 3.LinkedList
测试ArrayList和LinkedList的add方法
关于arraylist和linkedList的区别
【Java面试题】ArrayList和LinkedList区别
一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要...
ArrayList、LinkedList、Vector区别简介。
05丨ArrayList还是LinkedList?使用不当性能差千倍.html
2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动 3.LinkedList不支持高效的随机元素访问 4.ArrayList的
10.ArrayList 和LinkedList的区别.avi
ArrayList 和LinkedList各自的特点是什么,自己实用中的总结
ArrayList Vector LinkedList 区别与用法.
合理运用ArrayList与LinkedList
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
今天介绍一下Java的两个集合类,ArrayList和LinkedList,这两个集合的知识点几乎可以说面试必问的。感兴趣的朋友跟随小编一起看看吧
arraylist 和linked list的时间复杂度
1,ArrayList是数组的数据结构,LinkedList是链表的数据结构。 2,随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于 3,索引(index)的数据结构,可以直接映射到。 4,插入、...
对比Vector、ArrayList、LinkedList1
10.ArrayList和LinkedList基于动态数组,连续内存存储,适合下标访问(随机访问)扩容机制:因为数组长度固定,超出长度存数据时需要新建数组,然后
ArrayList-LinkedList-源码.rar
今天小编就为大家分享一篇对ArrayList和LinkedList底层实现原理详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧