Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?
Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time.

I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only.

Let $n$ be the maximal size (capacity) of the list. Let’s divide the list into $O(\sqrt{n})$ blocks of equal size $B$ (which is $O(\sqrt{n})$ too). Let also $b_j$ denote a cyclic shift of the $j$-th block.

When you need to access $i$-th element of the list, you calculate its position as follows in $O(1)$:

$$f(i) = (b_j + i \mod B) + B \times j$$

where $j = \lfloor \frac{i}{B} \rfloor$.

When you need to insert something into $i$-th position, you first make a cyclic shift of everything from $j$-th block to the end:


Decrement all $b$ values starting from $j$.
Swap the elements on the boundaries of consequtive blocks, so that every element is in its right place.
Then you fix $j$-th block by rebuilding it from scratch.


This gives you $O(\sqrt{n})$ insertion complexity.