Consider appending a node to a list. In the mutation world, we traverse the list until we reach the end and then change the last node to point to the new node. This is costly when the list is long and has a complexity of O(n).
For a persistent list (immutable and structurally shared) appending a new value, we need to traverse until the end of the list, copying all the elements on the way.
However, as noted, appending to a list is anyway a slow operation. When we need to append values, we need to ask ourselves whether lists are the right fit for the problem.
Whenever we want to grow a list by appending to the end, we should instead use a vector. When we are done with all of the appending, we could convert the vector into a list, if needed. ...