Constant-time adding an element? Is a computer with infinite memory and infinite word size a Truing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we allow constant-time linked link element insertion (at the beginning of the list)?
I doubt this because element insertion requires memory allocation and allocation is usually not a constant-time operation.
Oh, I've found an $O(1)$ allocation strategy:
Because our memory is infinite, we may never deallocate: Just add memory at the end of the used space by incrementing a pointer.