Singly-linked lists are a fundamental computational structure. A singly-linked list is simply an item and a pointer to another singly-linked list. To add an item, simply create a new singly-linked list with that item and a pointer to the old list. Since you are not copying data, this is O(1).
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.
Singly-linked lists are a fundamental computational structure, and I'm not disagreeing with anything in the spirit of your comment, but I want to point out that linked lists are pretty much never the right implementation choice for an application programmer unless you're working in a language with no decent stdlib and you also care hugely about every byte of RAM/storage/etc. Which does happen, but is not very common, in practice.
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. :)
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.