[aeflash]

I came across a similar solution when creating graphs with immutable data structures. Just store your nodes in an array, and describe the links between them as pairs of indexes. It does require that extra level of indirection, as hinted at in the "Dual Index Problem" article he links to. It is a bit odd, since you're basically reimplementing mutable pointers, where each operation returns a new set of memory.

I will add as a disclaimer that I'm somewhat new to the world of immutable data, and am still experimenting with this graph structure -- seeing how it scales with complicated data and relations.