问题 哪一个运行得更快，ArrayList或LinkedList？ [重复]

如果你必须执行大量的插入和不频繁的查找，请使用a 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);
}

看到 有效的Java， 第23项：不要在新代码中使用原始类型 详细解释。

编辑

从评论中的讨论中可以明显看出，如果您需要在列表中间或随机位置插入元素，那么 ArrayList性能优于 LinkedList 在性能方面，因为前者会使用 memcpy 移动非常快的元素，后者必须遍历到所需的索引以正确插入新元素，这是较慢的。所以对于随机插入 ArrayList 也表现优异 LinkedList。唯一的情况 LinkedList性能优于 ArrayList 如果你只插入列表的末尾，并且有很多这些插入。