Hello,
I have just updated the Java Collections Cheatsheet with a small modification : in the first table, I have mentioned the utility class “Collections” (thank you Evernat for your feedback).
Java Collections Cheatsheet - v2
If you are not familiar with the O-Notation (in our case, n is the number of elements managed by the collection):
O(1): Constant –> the time to execute the method is constant whatever the size
O(log n): Logarithmic –> if N is doubled, the running time is increased by a constant amount
O(n): Linear –> if N is doubled, the running time is doubled too
I want to thank “commentators” of my previous post: Davide Angelocola,Maurice Naftalin (one of the authors of the “Java Generics and Collections” book 
) and
Comments 5
Small correction: O(log n) probably shouldn’t be described as the running time increasing by a constant amount. It’s actually by the square root of 2, but that means the growth is nonlinear: it has a curve, steeper than linear… but of course, much shallower than n**2.
However, the cheat sheet itself looks fantastic. I’ve just printed it to study it in detail. Thanks for the great work.
Posted 04 Sep 2009 at 5:36 am ¶There’s an error in the cheat sheet. The remove(O) operation of LinkedList works in O(n), not O(1). You can check it for yourself in the source code.
Posted 06 Sep 2009 at 2:50 pm ¶This seems to be a common misconception, i’ve made a post about it here: http://forums.sun.com/thread.jspa?threadID=5406078
Contrary to the comment from Neverwinterx, the cheatsheet is correct if slightly ambiguous. It gives the complexity of remove(0) – the first element of the list.
There is no remove(O) method on List. There is, however, a method remove(Object) and, yes, that has linear complexity. But the book and the cheatsheet don’t discuss that.
Posted 10 Sep 2009 at 11:27 am ¶The other comment is also wrong:
log 2n = log 2 + log n
(see, for example, http://en.wikipedia.org/wiki/Logarithm), so the statement (in both book and cheatsheet) that “if N is doubled, the running time is increased by a constant amount” is correct.
Posted 10 Sep 2009 at 3:35 pm ¶Hello,
Since the answer of Maurice Naftalin(author of the book) is relevant, I’ve removed my previous answer because it would upset other future readers.
Thank you Maurice for your answers.
Coderfriendly
Posted 11 Sep 2009 at 4:34 pm ¶Trackbacks & Pingbacks 1
[...] de uma grande parte das linguagens de programação e aplicações. Por exemplo, referências das Collections do JDK ou as referências standard de [...]
Post a Comment