Functional programming uses immutable data structures by default. Every "modification" creates a new version.
Persistent list (cons list):
prepend(x, list) := new node pointing to list
# Shares entire old list
Persistent map (tree-based):
insert(key, value, tree) := path copy from root to insertion point
# Shares all unchanged subtrees
Languages like Haskell, Clojure, and Scala provide persistent structures by default. In C++/Java, you implement them explicitly.
The functional approach makes concurrency safer: no race conditions on shared immutable data.