java - 在 Java 中对 LinkedList 调用 size() 的时间复杂度是多少？

Question

正如标题所问，我想知道 LinkedList 类中的 size() 方法是否需要分摊的 O(1) 时间或 O(n) 时间。

Answer 1

它是 O(1)。你可以谷歌搜索源代码，你会得到这样的：

来自http://www.docjar.com/html/api/java/util/LinkedList.java.html

我看过的所有 Collection 类都将大小存储为变量，并且不会遍历所有内容来获取它。

Answer 2

如果您查看源代码，您会发现 O(1)...

从链表：

private transient int size = 0;

...

/**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
   return size;
}