1
$\begingroup$

I'm unsure about the safety of deletion in a linked list. I've seen the issue posed by a parallel insertion and deletion (resulting in the loss of the insertion) and proposed solutions to that problem. That makes perfect sense. However, nowhere have I seen it mentioned that an unlucky traversal in parallel with a deletion can cause problems. For example, if we have the linked list:

A -----> B -----> C* ------> D

and one process (process 1) is traversing it, currently pointing at C (as indicated by the *), however before process 1 reads the next pointer of C, another process (process 2) deletes C and frees its memory. Then, when the process 1 attempts to read C's next pointer, it will be reading uninitialized memory (which could be used to store an int for example), and thus could be pointed to an invalid location, and cause a segmentation fault by dereferencing that pointer.

How can this issue be avoided?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.