If every time you want to change something in a data structure, you just go and change it, your code will be full of side-effects. On the other hand, copying complete structures every time is a waste of time and space. There's a middle way, with persistent data structures, which, if handled correctly, let you apply changes while creating new structures, in an efficient way.
Let's consider a simple procedure: suppose you have a list, and you want to add a new element to it. How would you do it? We can assume each node is a NodeList object.
class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}A possible list would be as follows, where a list variable would point to the first element. See figure 10.1:
Figure 10.1. The initial list. (Can you tell what is missing in this list, and where?)
If you wanted to add D between B and F (this is something musicians will understand: we have here the Circle...