链表搜索Java中的时间复杂度

Question

我对 LinkedList 在 java 中的搜索复杂性感到困惑。我已经读过从 LinkedList 搜索元素的时间复杂度是 O(n)。比如说，

LinkedList<String> link=new LinkedList<String>();
    link.add("A");
    link.add("B");
    link.add("C");
    System.out.println(link.get(1));

现在，从这里通过 get(index) 方法我们可以说搜索一个元素应该花费 O(1) 次。但我读过它需要 O(n)。有人可以帮我弄清楚概念吗？

Answer 1

链表实现中的访问，如java.util.LinkedList，是 O(n)。为了从列表中获取一个元素，有一个循环遵循从一个元素到下一个元素的链接。在最坏的情况下，在n元素列表中，n执行循环的迭代。

将其与基于数组的列表（如java.util.ArrayList. 给定一个索引，执行一个随机访问操作来检索数据。那是 O(1)。