2 ms·
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
by _delirium 17y ago
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.