How many nodes are there? Let's presume there are a lot, otherwise the problem is trivial and speed doesn't matter anyway. So now you have an N-long immutable array that you are copying every time you want to change a node pointer? So you have changed the operation of pointer-changing from O(1) to O(N)? What does that do to the run time of the algorithm?
Also, your garbage velocity just went WAY up. What does this do for the runtime of your program generally?
2. Excessive generation of garbage is a problem for functional languages in general; that is nothing specific to immutable arrays. Good compilers analyze object lifetimes and perform updates in-place when possible (e.g. Mercury does this). Even if your compiler doesn't do this, the garbage generated is constant or logarithmic with respect to the size of the array for most common immutable-array implementations.
(The language implementation can of course engage in strategies to avoid a full array copy, that you as the user have little insight into, but these are often questionable as they slow down run time in other cases, and anyway, they can only mitigate this problem, which is not going to go away.)
Uh, most good implementations of languages with immutable arrays perform O(1) or O(log n) array updates. The two I use most, Mercury and Erlang, both do (O(1) and O(log n) respectively).
If you, the user, has "little insight" into the runtime of data structures you're using, you have bigger issues. Every standard library I've ever seen guarantees the asymptotic behavior of hash tables, sets, linked lists, etc. Immutable arrays are no different.
How many nodes are there? Let's presume there are a lot, otherwise the problem is trivial and speed doesn't matter anyway. So now you have an N-long immutable array that you are copying every time you want to change a node pointer? So you have changed the operation of pointer-changing from O(1) to O(N)? What does that do to the run time of the algorithm?
Also, your garbage velocity just went WAY up. What does this do for the runtime of your program generally?