If immutability is a language level guarantee and not just a convention, you can use structure sharing to address this problem pretty effectively. Just about any functional language with immutable datastructures does it.