In FP, you typically "change" a data structure by creating a shallow copy of it with a few parts replaced, but the rest just pointing back to the original - nothing's changed directly, and when data is no longer used, it's eventually garbage collected. (Typically, with a generational and/or copying collector, whose costs are proportional to surviving data.)

This works better with trees and lists than it does arrays and hash tables, because changes to those usually require adjusting as a whole. To add to the head of a linked list, you can just create a new cell of [new value, head of old list], which is very cheap. (Adding to the tail can be done with e.g. a deque). At the same time, anything that adds to the list won't interfere with other code that is holding a reference to the same list, or even accessing it concurrently.

Probably the best way to learn about purely functional data structures is from the book of the same name by Chris Okasaki.