2 ms·
Singly linked lists can still maintain a tail and before-tail pointer, maintaining O(1) tail operations.
by scott_s 15y ago
Singly linked lists can still maintain a tail and before-tail pointer, maintaining O(1) tail operations.
- jbri 15y agoSo 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.
- scott_s 15y agoSigh. 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.