Singly linked lists. Removing an element?

Question

Algorithms

Is there a way to remove an element from a singly linked list in O(1)? Provided that we have a pointer to the element to be removed.
For O(n) it is not a problem to do this with a search, but how without it for O(1)?

Answer 1

Only if you know the PREVIOUS element. Otherwise, for honest O (1) you will not remove anything from a singly linked list.
You can amortize delete in O(1) by simply marking that element as deleted. But then all the functions that iterate over the list must actually remove such marked elements during the pass.
The total running time of the algorithm will be as if the removal was O(1). But some individual operations can be much slower than with an honest constant. For example, if you add an element to the beginning of the list a bunch of times and immediately remove it, then the output of the list will be slow, despite the fact that the list should be empty.
But in practice, this method is probably not used. Because you are taking a pointer to the element to be removed somewhere. Usually, you can get a pointer to the previous one along with it. Or stupidly use doubly linked lists.

Answer 2

If this is not the last element, then we assign the value from the next one to it, then we delete the next one