I'm building an entire application out of immutable objects so that multi-threading and undo become easier to implement. I'm using the Google Collections Library which provides immutable versions of Map, List, and Set.

My application model looks like a tree:

• Scene is a top-level object that contains a reference to a root Node.
• Each Node can contain child Nodes and Ports.

An object graph might look like this:

Scene
 |
 +-- Node
      |
      +-- Node 
           |
           +- Port
      +-- Node
           |
           +- Port
           +- Port

If all of these objects are immutable, controlled by a top-level SceneController object:

• What is the best way to construct this hierarchy?
• How would I replace an object that is arbitrarily deep in the object tree?
• Is there a way to support back-links, e.g. a Node having a "parent" attribute?