Previous | Next --- Slide 7 of 35
Back to Lecture Thumbnails
Calloc

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:

1. Two insertions: the outcome on this slide occurs -- only the "winner" node remains;
2. 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;
3. Deletion / Deletion: There could be double deletion, and the case in 2) might also occur.