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 t

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.