Worst case Singly-Linked List Insertion/deletion is O(1)

[RyanCallen]

Shouldn't the worst case insertion/deletion time of a Singly-Linked List be O(n). Both would involve traversal of the entire linked list to find the last node.

[HalosGhost]

If I understand correctly, the notion is that insertion or deletion of a node at index n (given that you have a pointer to the node at n-1) is O(1).

So, while it is true that, if you do not know the node at n-1, you will perform a search (which is O(n)), the insertion/deletion itself is O(1) whereas the search needed to get to that point is O(n).

I was confused by this earlier and I do not believe it is ideal, but I am not sure how else it should be represented.

Additionally, this appears to be a duplicate of #65

[pablomusumeci]

Came here to report the same mistake.

More information over here http://stackoverflow.com/a/14048223/6630282

[alexshpilkin]

Actually, you can delete a node in a singly linked list in O(1), even if you only have a pointer to that node and not its predecessor. The cost is copying the node data and having a sentinel node at the end.

Specifically, to delete node n, set data(n) := data(next(n)), then set next(n) := next(next(n)), then free what used to be next(n) in case you’re doing automatic memory allocation.

(In other news, you can do mark&sweep garbage collection in time proportional to live memory.)