I wonder if this would be a good candidate for the basis of a persistent ("functional") data structure?

O(1) pointer changes for insert/remove is a good sign, since pointer changes tend to become space overhead in a persistent data structure.