java - 我应该为高效方法选择高时间复杂度数据结构还是高空间复杂度数据结构？

Question

我必须在 ArrayList 和 LinkedList 两种数据结构之间做出选择。 我有两个操作 op_one，op_two。

如果我选择 ArrayList - 我会以

for op_one ------ O(n), and at maximum n re-allocations
for op_two ------ O(1), and at maximum n re-allocations

如果我选择 LinkedList - 我会结束

for op_one ------ O(n), and zero re-allocations
for op_two ------ O(n), and zero re-allocations

我将存储数百万个可比较的元素。我将同样有可能进行这两项操作。我应该选择哪一个。

Answer 1

我建议您将它们放在一起计时，并采用一种现实的方式，看看哪个更快。如果它们没有显着差异，我会使用您认为最简单的方法。

虽然 ArrayList 和 LinkedLIst 的顺序在空间上是相同的，但 ArrayList 要小得多。

所有相同的清晰度通常是最重要的，除非你知道你有性能问题。