Let's say the entries of the original list and the new one point to the same objects, still for a list of a thousand entries you need to copy all the link entries to add one on top of it. What am I missing?
If you are working in an immutable context, meaning that you are building immutable data structures to contain immutable values, there are many useful structures that you can use.
For instance, the "single linked list" or simply "list" has constant-time push and pop operations. Here such a list of 3 elements (NIL is a special value that says "no more list")
L = (((v1, (v2, (v3, NIL)))
To add v0 in front, you just create a new "cell" that reuses the old list (which remains valid by itself) as the "tail" of the new list:
L2 = (v0, L)
L2 = (v0, (((v1, (v2, (v3, NIL))))
Depending on your requirements, there are more complicated and smarter data structures that can make the operations you care about either constant, or at most logarithmic.
I did scheme assignments as part of the programming language course back in the early nineties - but then I was wondering why the runtime environment had so many GC pauses (it was some A* search assignment, if I remember correctly) also it wasn't quite fast by any standards
* GC: it probably had a very simple algorithm, rather than a fancy generational GC
* Data structures: it wouldn't support modern functional structures like HAMT
* Compilation: you probably used an interpreter, rather than compiling the code to bytecode or native code
...and of course, the algorithm itself. It may not have been designed for functional data structures, or you may not even have implemented it in a functional style in the first place (Scheme supports mutation).
It's a Scheme-to-C compiler (plus interpreter / repl / script runner.) The Scheme code is transformed into continuation passing style (CPS) and then translated into C function calls that never return, but call other functions instead, forever. Therefore the C stack can only grow, never shrink, and is used as a natural "nursery" or first generation of allocation. When it eventually overflows, the garbage collector is invoked, which scans the stack for "live" values and moves them into the permanent generation (on the heap) and resets the stack; after which, execution resumes.
It's the most ingenious way I've ever seen to turn not just Scheme, but any language with automatic allocation into fully standard C code. I think there's only one non-portable function written in assembly, the garbage collector that runs when the C stack overflows. That's a small price to pay to have a compiler that can piggyback on any existing C compiler, for virtually any platform. (It's not even entirely in assembly. IIRC, it uses some kind of setjmp / longjmp sorcery.)
Moreover, the generated C code is fully tail-recursive and call/cc comes for free, so you can use first-class continuations in complex ways, without any performance penalty. It has hygienic macros and all the advanced stuff you expect from a modern Scheme. And of course you can link to any C library, use standard C APIs from Scheme and have your code compiled to optimized machine code.
If only Scheme was not a dynamically typed language... but that's a rant for a different time.
If you just want to insert an element at the beginning of the list you can use the original list as the tail of the new list. It's immutable, so it's not going to change under you.
If you want to insert stuff randomly, you wouldn't use lists to get the best results in a functional setting. You might use something like finger trees instead.
You would want a persistent data structure, such as persistent HAMT (as in clojure, scala and others) for associative map or a tree of subvectors for an appendable ordered list. These allow most of the structure to be shared between typical mutated versions and allow value semantics as a bonus.
