java - 为什么在链表中通过索引访问项目比在数组中慢？

Question

我认为我遗漏了一个非常明显的点，但在我的 Java 教科书中找不到它。

我知道链表的节点存储不一定必须在内存中连续。这是否也意味着链表不可索引？如果是这样，那么在链表中查找项目的唯一方法就是遍历列表，对吧，而您可以通过索引从数组中获取？

Answer 1

Why is accessing an item by index slower in a linked list than an array?

链表具有一系列条目。如果您想获取(例如)位置 42 处的元素，代码必须:

• 获取第一个元素的条目(位置0)
• 点击next链接前往位置1的条目
• 点击next链接前往位置2的条目

等等......总共42次。

没有捷径。

I am still not understanding why a linked list is not indexable ....

现在，LinkedList 是可索引的，因为存在一个get(int) 操作有效。只是索引 LinkedList 的效率低。一般来说，在长度为 N 的链表中执行 get(i) 需要 O(N) 步骤。与数组或 ArrayList 相比，您可以一步检索数据结构的任何元素。我们说复杂度是O(1)。

将此与一般的 Set 对象，特别是 HashSet 进行对比。 HashSet 类不可索引，因为没有 get(int) 方法来检索位置 i 处的 set 元素。事实上，即使是集合中“位置 i”的概念也是毫无意义的。 Set 中元素的顺序未指定，并且(对于某些 Set 实现，如 HashSet)，它实际上可能是不确定的。