I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from the same article, where it describes how to implement a persistent linked list:

enter image description here

The author says:

Inserting a new item into a persistent singly linked list will not alter the existing list but create a new version with the item inserted into it. Instead of copying the entire list and then inserting the item into the copy, a better strategy is to reuse as much of the old list as possible.

Since the two versions (Red and Yellow + Red) have common nodes (specifically, the last three Red nodes), how can one access these two versions simultaneously, for example in a multithreaded application?


1 Answer 1


Such list is intended to be immutable - the shared nodes will never be written to. There is no problem with several threads reading from the same memory location.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.