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)你看过源代码了......

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