Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend
MarkMLI maybe found it too obvious, but one more difference: A normal multidimensional array has a rectangular shape (in 2D) and so on in larger dimensions, while (for dynamic arrays) an array of an array can have different size rows.
Considering that, the dynamic arrays can give a memory size benefit, not a speed one. Splitting the array to smaller chunks is just marginally better, since the problem of shifting the tail remains, just the tail becomes smaller.
But the problem with the linearisation emerges - in which chunk to insert the current element given the 1D insertion index n? The chunk sizes must be extracted sequentially from n until n is smaller than the current one and that will be the 2-nd level index. Sounds optimal?
Back to the original question:
How can one optimise inserting an item into an array, anywhere but the end?
Here IMHO the most straightforward answer:
Don't use an array.
MarkMLl
Or with other words: "No one can."
The OP must give more details for the application in order to receive more beneficial answer. Other is just a speculation.
Being speculative, I would propose in turn the
linear hashing.