There are many strategies to deal with that efficiently. Eg. negative indices (having memory before index 0), append-and-reverse.

You can also map memory before an existing mapping, but it's a bit system-and-platform dependent. (But an entirely feasible thing to do).

Naively you can also grow-and-shift or copy ... the first one is actually incredibly fast due to perfect locality, and also very simple to implement. It's still, technically, O(n^2) when building a list, so it's usually a better idea to go for append-and-reverse (which works outside the actual list implementation). Normally that's not a problem at all, and often no reversal has to be materialized.

If you know the format you want, and read infrequently, just implement it as an append and read it backwards.

If you have frequent reads, you can also consider writing your data to a file (or a memfd), and then using mmap to construct the memory layout you want. You will then see that prepend is worse-case log^3 (depth of the pagetable, assuming you have to keep moving the whole thing) time, which is much better than finger trees, and if you prepend often you can make it constant time (by choosing a high start virtual address: remember, there's 64 bits of address but only 48 bits of memory, so you can have 64k big objects without much work) which makes it faster than linked lists.

Another idea: use VMX extensions and collaborate between each layer to trade a lower constant mean and coefficient to parameterise max to log^k. Gains here might require very big data sets though.

deques support fast prepending. You can implement them on top of shared memory, although as the canonical implementation is block based and uses indirection for access, the dynamic resizing capability is less useful.