Java 中 LinkedList 上的 size() 调用的时间复杂度是多少？

Question

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

Answer 1

是 O(1)。你可以google一下源代码，你会得到这样的结果：

从 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;
}