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.
[ Parent
| on HN ]
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.
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.