巨型LinkedList的遍历

Question

对于一个项目，我需要编写一种方法，该方法是使用Listiterator使用LinkedList填充的LinkedList的遍历，然后使用LinkedList的GET（index）方法。

我在Listiterator上穿越它没有问题，并且在75毫秒左右完成。但是，在尝试了500万个整数上的Get方法遍历之后，我刚刚在1.5小时的时间内停止了跑步。

我使用的getTraverse方法例如下面的代码（但是，我的类别与类中的其他方法分组为非静态，但以相同的方式工作）。

public static long getTraverse(LinkedList<Integer> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < linkedList.size(); i++) {
        linkedList.get(i);
    }
    long stop = System.currentTimeMillis();
    return stop - start;
}

这对于50、500、5000、50000的整数的LinkedLists效果很好，并且花了相当长的时间，但完成了500000。

我的教授往往对指示非常含糊，并且在提出问题时非常无用。因此，我不知道我的代码是否被打破，或者他是否在准则中被整数带走了。任何输入都将受到赞赏。

Answer 1

想想如何实现LinkedList作为节点链 - 您会看到要到达要启动的特定节点，您必须从头部开始并穿越该节点。

您正在 LinkedList n 次上调用.get()，这需要遍历列表，直到达到该索引为止。这意味着您的getTraverse()方法需要O（n^2）（或二次）时间，因为对于每个元素，它都必须遍历列表。

正如埃利奥特·弗里施（Elliott Frisch）所说的那样，我怀疑您确切地发现了您的教练希望您发现的东西 - 不同的算法可能具有截然不同的跑步时间，即使它们原则上也可以做同样的事情。

Answer 2

a LinkedList已针对插入进行了优化，这是一个恒定的时间操作。

搜索LinkedList要求您迭代每个元素以查找所需的元素。您提供了get方法的索引，但是在封面下，它正在将列表穿越到该索引。

如果添加了一些打印语句，您可能会看到第一个X元素的检索很快，并且随着您的索引元素的进一步索引。

ArrayList（由数组支持）已优化用于检索，并且可以在恒定时间内为所需的元素索引。尝试更改代码以使用ArrayList，然后查看get运行的速度。