Yeah, I was confused by this. Why is deletion not still O(n)? The back pointer doesn't gain you anything, because you can just drag along a temporary "last next" pointer when you're scanning to find the element to delete, which you have to do either way, so the s-list is asymptotically no slower at deletion--- O(n) to find the element to delete, and O(1) to delete it.

Sure thing, I've considered adding that. But since it is not directly related to the stack/queue/etc split, I kept it out for the sake of simplicity.

I think its more confusing to say that insertion is O(1) when insertion in the general case is O(n). Hash tables should be another discussion.

It does not say that the insertion is O(1). It says that it's O(1) _at the head_.

My post was in response to the thread above -- the bottom line is that for all of the linked lists you mention insertion/deletion is O(n) in the general case and O(1) at the head. The way its currently written is confusing and wrong.