> Performance differences between ArrayList and LinkedList9个
List li = new LinkedList();
for (int i = 0; i < 100; i++) {
li.add(i);
}
long start1 = System.nanoTime();
li.get(57);
long end1 = System.nanoTime();
long diff1 = end1-start1;
System.out.println("Time taken by LinkedList = "+diff1);
List al = new ArrayList();
for (int i = 0; i < 100; i++) {
al.add(i);
}
我在两个列表上执行了什么操作,当我打印出时间时,ArrayList总是比LinkedList运行得更快.
有人可以解释一下表现更好的时间吗？
还要让我知道代码中是否有错误.谢谢！
解决方法
原因如下 – ArrayList由具有初始容量的数组支持.因此,如果您将项目插入列表中,则必须重新调整其阵列容量以适应新插入的项目,如果执行索引特征插入,则还可能需要移动现有项目.另一方面,LinkedList由链表支持,其中创建一个项目始终在一个恒定的时间内执行 – 创建一个项目并将其分配到列表的末尾.这里没有重新调整.
现在要从ArrayList获取一个项目,它总是需要一个固定的时间,因为它可以很容易地在一个恒定的时间内对背景数组进行索引.但是从LinkedList中获取项目可能会导致您遍历整个链接列表以查找项目节点.因此,在这种情况下,它的性能要低于ArrayList.
从上面的讨论中可以看出,当你有更多的插入时,LinkedList总是会优于ArrayList,因为后者的内部调整大小与插入相关联,而前者没有.另一方面,如果您有不频繁的插入和频繁查找,ArrayList总是会优于LinkedList,因为后者您可能必须遍历整个链接列表结构才能找到所需的项目,而前者可以快速找到您的项目数组索引在恒定时间.
当您处理大量项目(例如数千个项目)时,上述所有效果都将可见并影响您的应用程序的性能.对于较少的项目,性能差异不太明显.
现在,关于你的代码,你有一些严重的问题.对于起动器,您使用的是一种原始类型,因为您失去了仿制药所提供的所有类型的安全性,这是不好的.编写新代码时,应始终使用Collection API的通用版本.所以,改变你的代码如下 –
List<Integer> li = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {
li.add(i);
}
long start1 = System.nanoTime();
li.get(57);
long end1 = System.nanoTime();
long diff1 = end1 - start1;
System.out.println("Time taken by LinkedList = "+diff1);
List<Integer> al = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
al.add(i);
}
请参见Effective Java项目23：不要在新代码中使用原始类型进行详细说明.
编辑
从评论中的讨论中可以看出,如果您需要在列表中间或随机位置插入元素,则ArrayList在性能方面优于LinkedList,因为前者将使用memcpy来移动元素非常快,后者必须遍历到所需的索引才能正确插入新元素,这是较慢的.所以对于随机插入,ArrayList也胜过LinkedList.唯一的情况是LinkedList优于ArrayList,如果您只插入到列表的末尾,并且有很多这些插入.