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

Question

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

Answer 1

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

来自 LinkedList：

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

Answer 2

是 O(1)。 你可以用谷歌搜索源代码，你会发现这样的：

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

我看过的所有 Collection 类都将大小存储为变量，并且不会迭代所有内容为拿到它，为实现它。