structural sharing is what clojure does. But you can have immutable data structures in old lisps if you only use cons, car and cdr, avoiding set-car and set-cdr.