Re:What's wrong with this code, really?
by icebraining on Friday September 16, 2011 @10:44AM
(#3004606)
> If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.
I'd expect any decent linked list implementation to keep an integer with the current size. Java certainly does: http://www.docjar.com/html/api/java/util/LinkedList.java.htm...
Re:What's wrong with this code, really?
by masklinn on Friday September 16, 2011 @09:33AM
(#3004367)
> If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.
You're still going to run in O(n^2) if you remove from the back (as you'd do if you run in reverse).
Linked list are far more efficient if you build in reverse but remove in iteration order (just replace your head pointer with head.next)
Though you have to be careful with that, because the obvious code for removing from a collection in reverse:
for(i = list.size; i >= 0; i--)
list.removeAt(i);
Is itself a schlemiel algorithm on any singly-linked list...You're removing i+1 elements here :)
Re:What's wrong with this code, really?
by Confusion on Saturday September 17, 2011 @03:19AM
(#3007476)
That really depends on the implementation of the linked list. I don't think it would actually behave O(n^2) in most implementations.
Re:What's wrong with this code, really?
by willfarrell on Friday September 16, 2011 @11:43AM
(#3004890)
for(i = list.size; i--;)
list.removeAt(i);
If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.
c.f. https://secure.wikimedia.org/wikipedia/en/wiki/Schlemiel_the...