I would like to learn how to make graphs and perform some local operations on them in Haskell, but the question is not specific to Haskell, and instead of graphs we may consider doubly linked lists.

Question: What would be an idiomatic or recommended way to implement a doubly linked list (or other doubly linked or circular data structure) and operations on it in a language that mainly supports and advocates for immutable data structures (Haskell, Clojure, etc.)? In particular, how to use in-place updates, which are formally forbidden by the language?

I can easily imagine that if some local operation is performed on a doubly linked list (if an item is inserted, for example), there may be no need to copy the entire list immediately due to the laziness of the language. However, since the list is doubly linked, if it is modified in one place, none of the old nodes can be used in the new version of the list, and they would need to be somehow marked, copied, garbage-collected sooner or later. Obviously these are redundant operations if only the updated copy of the list shall be used, but they would add an "overhead" proportional to the size of the list.

Does this mean that for such tasks immutable data is simply inappropriate, and functional declarative languages without "native" support for mutable data are not as good as imperative ones? Or, is there some tricky workaround?

P.S. I have found some articles and presentations on this subject in the Internet but had hard time following them, while i think that the answer to this question should not take more than one paragraph and maybe a diagram... I mean, if there is no "functional" solution to this problem, the answer probably is "use C". If there is one, then how complicated can it be?

There is a related question "Data structures in functional programming", but my specific question about using in-place updates instead of inefficient alternatives is not discussed there.