Read more here: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list...
If this interests you, read also about tree structures such as red-black trees. These kinds of structures support all operations that mutable structures support in O(log n) time. Of course mutable structures can always be faster, but immutable structures are far better than linear time.
For the benefit of the GP, what might be non-obvious about the way colanderman describes this, is that if you want lists that are cell-immutable but are resizeable with O(1) push() and pop(), you do your pushing and popping off the front of the list. So the pointer to the old list is still a valid pointer to its previous state. And at this point, yeah, go off and read the WP link. :)