I've been tasked with the creation of a data structure that can do the following in O(1) time:

get(i): return the element at index i.

remove(i): remove the element at index i.

add(i, e): add the element e at index i. Subsequently, all elements following e will have their index incremented by 1.

Any suggestions? I'm quite puzzled as to how I can even create something that can do all of this.

CodePudding user response：

I can't think of any combination of data structures, which can achieve such performance, because you have to keep the data in all of them in sync.

Some kind of a workaround that comes to mind is to use array as the backing structure - O(1) for getting by index. Removal at index and setting at index are O(1) as well for the operation itself, the problem is the subsequent need to shift the backing array.

To somewhat fix performance of the shifting, you should not use loops, but System.arraycopy() instead. It's extremely efficient, because it won't do n copy operations, but instead copy entire chunk of the memory at once. You can read more on the topic in Why is System.arraycopy native in Java? and Is it better to use System.arraycopy(...) than a for loop for copying arrays?

Strictly speaking, this is not O(1) time complexity, but due to the efficiency of System.arraycopy() you can get very close to it, especially for large arrays.

CodePudding user response：

List & array both ; u must confuse y add(i,e) can be in O(1). like HashMap , add(i,e) is a onetimething , move afterwords wont be count in O(1) Think , index how many data structure has index n in memory one by one ?