That would be problematic using non-immutable datastructures as well as you might end up with incorrect order or even nonsensical data if you don't use locking.

Having used immutable data structures and concurrency in non-clojure languages, I mostly resort to something like concurrentML for concurrency. Message passing lets you solve situations like that in more elegant ways.