17 
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 运行得快。有人可以解释哪个在所花费的时间方面表现更好吗？如果代码有问题，也请告诉我。谢谢！

4

4 回答 4

16

如果您必须执行大量插入和不那么频繁的查找，请使用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是，如果您只在列表末尾插入，并且有很多这样的插入。

于 2013-09-11T07:05:04.237 回答
2

数组列表在读取方面总是比链表快。ArrayList 基本上是数组实现，为数组分配的内存是顺序的，因此读取速度更快。但是，当您使用需要在列表之间插入或删除的列表时，链接列表会更快。因为它只需要在节点之间添加链接。在这两种情况下，数组列表会比较慢。用法可以是：

ArrayList - 更快的读取操作，列表之间的插入、删除更慢。链表 - 读取操作比数组列表慢，但列表之间的插入、删除更快。

于 2013-09-11T07:08:42.393 回答
1

ArrayList由数组支持，并且LinkedList支持节点与参考链接。

所以对数组的操作ArrayList实际上是对数组的求值操作。添加操作以摊销的常数时间运行，即添加 n 个元素需要O(n)时间。所有其他操作都以线性时间运行（粗略地说）。与实现的常数因子相比，常数因子较低LinkedList。

并且LinkedList所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。

阅读有关文档的更多信息 -

于 2013-09-11T07:05:40.043 回答
0

LinkedList添加每个元素时将涉及创建新节点，而它不在数组列表中。

如果您知道初始大小，然后在创建时将其传递给，它可以避免像;ArrayList那样重建数组new ArrayList(100)

于 2013-09-11T07:07:42.530 回答