Yes, but with granularity at the "node" level instead of being across the whole container. Imagine a linked list.

If you add prepend an element to an existing list, no copy is necessary. It's just a new head with the tail being the original list. That's an easy case.

If you add a node in the middle of the list you can still share the unchanged tail between the two slightly different prefix sequences.

No, because you don't copy the whole structure. You create a new partial structure.

E.g. let's say you create a map with keys A and B. You then insert a new key C. In memory you might have two objects: One is the origi al map with A and B and the other has "Key C and a ref to the first map".

Well, yeah, only there ain't any writes (and therefore, no copying).

The simplest example would be with linked lists, I suppose: you have a list A->B->C, then you take the B->C sublist and prepend X to it, so you now have X->B->C, but A->B->C is still around, and "B->C" part is shared between those.

Copy-on-write generally refers to copying everything on every write; this is a persistent data structure, which can do updates while only copying a small part of itself. Same purpose as COW, but more efficient for larger data structures we want to make lots of small updates on.

No, there is no "write" because the old value never chnages. It's "create an overlay on write"

There’s also a Rust crate that does it like that: https://docs.rs/im/latest/im/