哪一个运行得更快,ArrayList或LinkedList？

Question

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运行得更快.有人可以解释哪个时间表现更好吗？如果代码中有问题,请告诉我.谢谢!

Answer 1

如果您必须执行大量插入和不频繁查找,请使用LinkedList.使用ArrayList如果超过插入执行多个查询.

原因如下 - 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是,如果您只在列表的末尾插入,并且有很多这些插入.