首页 > 代码库 > LinkedList的一种错误用法
LinkedList的一种错误用法
最近在做图像处理的时候,发现某一段代码非常的慢,慢得让人无法接受。主要的代码是顺序访问一个LinkedList的元素,效果是随着index的变大,速度越来越慢,list的元素个数在百万以上。找到原因,分享出来,也希望大家不要跳入同一个陷阱。还是那一句话,可运行的代码和高质量的代码之间还是有比较远的距离。
LinkedList错误用法示例
代码里面加入了一些打印时间相关的代码,主要是为了直观的显示运行的耗时。
错误代码
public static void main(String[] args) { // add elements int size = 2000000; List<String> list = new LinkedList<String>(); for (int i = 0; i < size; i++) { list.add("Just some test data"); } long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.get(i); if (i % 10000 == 0) { System.out.println("query 10000 elements spend: " + (System.currentTimeMillis() - startTime)); startTime = System.currentTimeMillis(); } } }
控制台输出如下:
错误原因
错误的代码就是list.get(i)
,LinkedList的底层是一个链表,随机访问i的时候,链表只能从头往后数,第i个才返回。所以时间随着i的变大时间会越来越长。
正确用法
顺序访问,LinkedList绝对不要用get方法,即使LinkedList的元素个数只有很少的几个。养成好习惯,免得犯错。
for each
for (String element : list) { // process element here }
iterator
Iterator<String> iter = list.iterator(); while (iter.hasNext()) { String element = iter.next(); // process element here }
直接换为ArrayList
public static void main(String[] args) { // add elements int size = 2000000; List<String> list = new ArrayList<String>(); for (int i = 0; i < size; i++) { list.add("Just some test data"); } long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.get(i); if (i % 10000 == 0) { System.out.println("query 10000 elements spend: " + (System.currentTimeMillis() - startTime)); startTime = System.currentTimeMillis(); } } }
ArrayList的控制台输出如下:
LinkedList VS ArrayList
下面比较一下LinkedList和ArrayList的效率。
新增、查询、删除比较
ArrayList测试代码如下:
public static void main(String[] args) { // add elements int size = 20000000; List<String> list = new ArrayList<String>(); long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.add("Just some test data"); } System.out.println("add " + size + " elements spend: " + (System.currentTimeMillis() - startTime)); // query startTime = System.currentTimeMillis(); String median = list.get(size / 2); System.out.println("query median spend: " + (System.currentTimeMillis() - startTime)); // delete startTime = System.currentTimeMillis(); list.remove(median); System.out.println("delete median spend: " + (System.currentTimeMillis() - startTime)); }
LinkedList测试代码如下:
public static void main(String[] args) { // add elements int size = 20000000; List<String> list = new LinkedList<String>(); long startTime = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.add("Just some test data"); } System.out.println("add " + size + " elements spend: " + (System.currentTimeMillis() - startTime)); // query startTime = System.currentTimeMillis(); String median = list.get(size / 2); System.out.println("query median spend: " + (System.currentTimeMillis() - startTime)); // delete startTime = System.currentTimeMillis(); list.remove(median); System.out.println("delete median spend: " + (System.currentTimeMillis() - startTime)); }
各自特点
- 新增
ArrayList比LinkedList快很多,超过一个数量级。很是意外。 - 随机查询
在i值很大的时候,ArrayList比LinkedList快很多,i越大,差距越大。ArrayList底层是数组,随机访问时间效率是O(0),而LinkedList是O(n)。 - 删除
LinkedList比ArrayList快很多。LinkedList的删除操作时间效率为O(0),而ArrayList是O(n),ArrayList需要查找数据、移动数据,所以慢。
总结
尽量使用ArrayList,ArrayList满足不了需求的时候再用LinkedList。根据LinkedList的特点,在下面几种情况下才使用LinkedList。
- 需要使用
java.util.List
接口之外的API
LinkedList实现了Queue和Stack等接口,可以用来当作一些特殊的容器。吐槽JDK里面LinkedList的设计,塞太多东西了,和名字不符。 - 元素删除比较频繁
如果数据量大,删除频繁,只能用LinkedList。 - 内存碎片化且元素很多
ArrayList底层是一个数组,数组要求一段连续的内存快。LinkedList也可以充分利用内存的一些碎片。特别是JVM使用Concurrent Mark-Sweep Collector垃圾回收器的时候,显得尤为重要。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。