Functional data structures are used a little differently from their imperative counterparts. Instead of saying list.append(x) you would say something like

Functional data structures are used a little differently from their imperative counterparts. Instead of saying list.append(x) you would say something like list = list.withLast(x) thus assigning the newly constructed list value back to the variable 'list'. There is a small literature within computer science on efficient implementations of functional data structures. While some tricks are involved, I think it's safe to say it's a solved problem, thanks to people like Chris Okasaki and Phil Bagwell.