0

当我（分别）运行时：

package containers;

import java.util.*;

    public static void main(String[] args) {

    List<Integer> arLst = new ArrayList<Integer>();
    List<Integer> lnLst = new LinkedList<Integer>();

    long start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        arLst.add(i);
    }

    System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

    start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        lnLst.add(i);
    }

    System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
}

我得到大致相同的执行时间。我知道 LinkedList 的添加时间应该更快。我想知道为什么..（对于中间插入和最后一个元素来说是有道理的 - 因为数组知道在 O(1) 中插入的位置，不像 LinkedList 必须遍历整个列表，我记得）。

4

5 回答 5

4

两个列表都知道列表末尾的位置，因此插入时间几乎相同。我本来希望 LinkedList 会稍微慢一些，因为它为每个元素创建一个节点并使用更多内存。

我明白了

TIntArrayList - 141 ms
ArrayList<Integer> - 810 ms
LinkedList<Integer> - 5190 ms.

TIntArrayList 不会更有效地使用缓存为每个元素创建对象。

于 2012-08-22T13:41:11.493 回答
4

你的两个列表都是ArrayList...如果你改变它们，LinkedList你也不会注意到有很大的不同。ArrayList以您的方式构建每次插入的复杂度为 O(1)。

于 2012-08-22T13:41:19.020 回答
3

您的代码与您的解释不同。但是，这是您问题的答案：

ArrayList 与 LinkedList

于 2012-08-22T13:43:14.787 回答
2

嗯……也许是这样的：

List<Integer> lnLst = new ArrayList<>();

应该是这样的：

List<Integer> lnLst = new LinkedList<>();

而且我无法理解您要测量什么。我认为您想衡量add性能，然后您的代码应如下所示：

    public static void main(String[] args) {

        List<Integer> arLst = new ArrayList<Integer>();
        List<Integer> lnLst = new LinkedList<Integer>();

        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i++) {
            arLst.add(i);
        }

        System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

        start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i++) {
            lnLst.add(i);
        }

        System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
    }
于 2012-08-22T13:40:19.070 回答
0

...因为数组知道在 O(1) 中插入的位置，不像 LinkedList 必须遍历整个列表，我记得）。

这是不正确的。数组（不是 ArrayLists）没有固定的插入时间，Java 的 ArrayList在技术上也没有（添加操作在 ArrayList 的摊销固定时间内运行）。

此外，将元素插入链表是O(1)：

除了实现 List 接口外，LinkedList 类还提供了统一命名的方法来获取、删除和插入列表开头和结尾的元素。

如果要插入排序列表，复杂度将变为O(N).

于 2012-08-22T13:52:16.080 回答