What is the time complexity of a size() call on a LinkedList in Java?
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.
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;}