How can we optimize insertion on ArrayList?

Question

In fact this is a interview question asked a few days ago.

The interviewer wants me to express the difference between ArrayList and LinkedList, and asked to optimize the insertion operation on ArrayList, in other words, to re-implement add(int index, E element) and of course the complexity of get(int index) operation can be sacrificed.

My answer was to separate the array into k sub-arrays and update a counting array representing the number of elements already in the corresponding sub-array. And the memory of every sub-array is allocated dynamically with an expected initial size. When I need to insert a data into the ArrayList, I can locate a sub-array first, and do the operation within a small array. And if insertions are not too frequent or the indexes are uniform distributed, the time complexity of inserting can be O(log(k) + n/k + k) in average, where log(k) means we should locate the sub-array first with binary searching on the counting array's sum array, n/k is for data movement or even memory re-allocation, and k stands for the updating of the sum array.

I'm sure there are better solutions. I do need some suggestions, thanks!

Answer 1

One of the solutions could be:

• add(int index, E element) always add element to the end of array (you have to also store the index where this element should be added) - complexity O(1)
• get(int index) has to restore correct order of array (if some elements were added after the last invocation) - knowing the positions in which each element should be, you can restore correct order in O(n)