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)
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)