As the title asks, I wonder if the size() method in the LinkedList class takes amortized O(1) time or O(n) time.
Thanks!
+5
A:
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;
}
Kris
2009-05-14 13:58:51
And if you're not using Sun's implementation at all? http://en.wikipedia.org/wiki/Java_Class_Library#Alternative_implementationsI think his question is whether it is guaranteed to be O(1), rather than whether it is O(1) in any specific implementation/version.
jalf
2009-05-14 14:04:43
The implementation has been the same since 1.2 when LinkedList was introduced, so it'll always be O(1)
Valentin Rocher
2009-05-14 14:05:24
This 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.
Kris
2009-05-14 14:05:34
+9
A:
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.
GreenieMeanie
2009-05-14 14:00:48