Note that simultaneous deletion is also a problem with this code, we might free the node twice for example.
traveling_saleswoman
Another possible situation with simultaneous deletion is that you could delete two adjacent nodes, and then lose the second half of the list when the preceding node points to a deleted node.
Lawliet
If we try to add and delete the same node, we could get a race condition on whether the node is in the list at the end of the operations as well (assuming we can try to delete nodes that aren't necessarily in the list yet)
yimmyz
To summarize what could go wrong when the non-thread-safe implementation is run across many different threads:
Two insertions: the outcome on this slide occurs -- only the "winner" node remains;
Insertion / Deletion: It is possible that when establishing the next link of the new node, it points to the node being deleted, thereby cutting off the entire remaining portion of the linked list;
Deletion / Deletion: There could be double deletion, and the case in 2) might also occur.
Note that simultaneous deletion is also a problem with this code, we might free the node twice for example.
Another possible situation with simultaneous deletion is that you could delete two adjacent nodes, and then lose the second half of the list when the preceding node points to a deleted node.
If we try to add and delete the same node, we could get a race condition on whether the node is in the list at the end of the operations as well (assuming we can try to delete nodes that aren't necessarily in the list yet)
To summarize what could go wrong when the non-thread-safe implementation is run across many different threads:
next
link of the new node, it points to the node being deleted, thereby cutting off the entire remaining portion of the linked list;