News for hackers. Stuff that matters.
Re:What's wrong with this code, really? by icebraining on Friday September 16, 2011 @10:34AM (#3004564)
And for singly linked lists, deleting the last would be O(n), while the first would be O(1) (just change the head to point to the next node).

Parent has a point for arrays/arraylists, though, you need to copy everything after the element.

Re:What's wrong with this code, really? by scott_s on Friday September 16, 2011 @05:33PM (#3006408)
Singly linked lists can still maintain a tail and before-tail pointer, maintaining O(1) tail operations.
Re:What's wrong with this code, really? by jbri on Friday September 16, 2011 @06:12PM (#3006534)
So after you delete the last element, how do you get the new before-tail pointer?

If you recalculate it right there, you've actually done nothing in terms of the algorithmic complexity. If you defer it either until it's needed or until you next enumerate the list, then you get to O(1) in the case of individual removes at the end (as long as they're interspersed with other operations), but you're still O(n^2) for removing the entire list starting at the tail.

Re:What's wrong with this code, really? by scott_s on Friday September 16, 2011 @08:12PM (#3006807)
Sigh. You're right. It's amazing how many linked lists I've implemented, and how often I still can screw it up. A singly-linked list with a head and tail pointer allows O(1) tail insertion, but still has O(n) tail deletion.