4 ms·
Using the author's terminology: the last two, the h-list and the d-list, ought to have O(1) insertion anywhere too. Since he calls removal at any position O(1)
by notaddicted 17y ago
Using the author's terminology: the last two, the h-list and the d-list, ought to have O(1) insertion anywhere too. Since he calls removal at any position O(1) he must already have a pointer to the desired item. Also, this implies that insertion anywhere is O(1) in all four list types.
- latitude 17y agoSure 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.
- aliston 17y agoI 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.
- latitude 17y agoIt does not say that the insertion is O(1). It says that it's O(1) _at the head_.
- aliston 17y agoMy 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.
- _delirium 17y agoYeah, 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.