Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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