As the title asks, I wonder if the size() method in the LinkedList class takes amortized O(1) time or O(n) time.
2 Answers
It's O(1). You can google for the source code and you will come to such:
From 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.
-
3
O(1) as you would have found had you looked at the source code...
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;
}
-
7And if you're not using Sun's implementation at all? en.wikipedia.org/wiki/… I think his question is whether it is guaranteed to be O(1), rather than whether it is O(1) in any specific implementation/version.– jalfMay 14, 2009 at 14:04
-
2The implementation has been the same since 1.2 when LinkedList was introduced, so it'll always be O(1) May 14, 2009 at 14:05
-
6This is from Java 1.6. This is not dependent on the VM but (in theory) could be different in older versions of the standard library. Check your version's source if you want to be 100% sure, but no sane developer would calculate the size on demand for something like this where everything is in memory and you can tally it up as the structure is created.– KrisMay 14, 2009 at 14:05