Java 中对 LinkedList 调用 size() 的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/863469/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the time complexity of a size() call on a LinkedList in Java?
提问by Martin Andersson
As the title asks, I wonder if the size() method in the LinkedList class takes amortized O(1) time or O(n) time.
正如标题所问的那样，我想知道 LinkedList 类中的 size() 方法是否需要分摊 O(1) 时间或 O(n) 时间。
采纳答案by GreenieMeanie
It's O(1). You can google for the source code and you will come to such:
是 O(1)。你可以谷歌搜索源代码，你会得到这样的：
From http://www.docjar.com/html/api/java/util/LinkedList.java.html
来自http://www.docjar.com/html/api/java/util/LinkedList.java.html
All of the Collection classes I have looked at store a the size as a variable and don't iterate through everything to get it.
我看过的所有 Collection 类都将大小存储为变量，并且不会遍历所有内容来获取它。
回答by Kris
O(1) as you would have found had you looked at the source code...
如果您查看源代码，就会发现 O(1) ...
From 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;
}
