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

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. :)