If each pointer in the chain would keep track of how many times it has been dereferenced. Then during a dereference we could check if the sum of these ticks is greater than the size of the array (or some threshold constant times the size of the array). If that is the case then we can copy, knowing that it is paid for by all previous accesses.
When accessing an old version, we only have to update its count. While traversing a chain we can multiply that count by the remaining length of the chain. That way we don't have to mutate every link every time.
We can also add two different constructors: one with the count and one without. Then we only have to incur the extra memory (and time?) overhead if the old versions are actually used.
If each pointer in the chain would keep track of how many times it has been dereferenced. Then during a dereference we could check if the sum of these ticks is greater than the size of the array (or some threshold constant times the size of the array). If that is the case then we can copy, knowing that it is paid for by all previous accesses.
When accessing an old version, we only have to update its count. While traversing a chain we can multiply that count by the remaining length of the chain. That way we don't have to mutate every link every time.
We can also add two different constructors: one with the count and one without. Then we only have to incur the extra memory (and time?) overhead if the old versions are actually used.