Algorithm for deleting one element in an single linked list with O(1) complexity

Question

I'm a student of computer science in Germany. My professor gave use the following question to think about:

'Given a reference to a node in a single linked list (which is not the last node). Give an algorithm to delete this element from the list which has O(1) complexity while maintaining the integrity'.

I thought about this, but I'm pretty sure, that there is no such algorithm. since it is a single linked list, you must loop through every node in the list until you reach the node which should be delete, because you have to modify the next-Pointer in the node before the deleted. Which would lead to O(n) complexity.

Am I missing anything?

Answer 1

It depends on whether or not the nodes are mutable (in value).

There is a way of doing it, if you can do what you like with the nodes:

toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next

All the information from toDelete has now been overwritten, by the information in the old toDelete.next. (Depending on the platform, you may then need to free the old toDelete.next - which means keeping a temporary reference to it. Not good if anyone else still has a reference to it, of course. In Java/C# you'd just ignore it.)

I tried to work out a way of hinting at it without giving it away, but it's kinda tricky...

It does rely on this not being the last node in the list though.

Answer 2

Not exactly considered deleting a node but you can copy the data of the next node to the current and delete the next node:

// pseudocode:
this.data = next.data;
var temp = this.next;
this.next = next.next;
delete temp;

Answer 3

If the nodes are basic structures in memory, you can copy the contents of the "next" node into the memory location of the deleted node, and deallocate the memory where the "next" node used to be.

Answer 4

Yes. You keep as your iterating pointer, a pointer to the next pointer of the previous list.

walk = &head;
while (!match(*walk)) {
    walk = &walk[0]->next;
    if (!*walk) return ;
}
*walk = walk[0]->next;

Answer 5

Assuming you have the pointer to the node you wish to delete. Replicate the next value into the current node. Replace the current pointer to the node the next pointed at.

Answer 6

move the data, not the link. look to this other thread: Deleting a middle node from a single linked list when pointer to the previous node is not available