-1

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.

Enzo
  • 29
  • 3
  • are you sure you read it correctly? "Subsequently, all elements following e will have their index incremented by 1." doen't seem like a O(1) operation to me – Icarus Oct 08 '22 at 07:46
  • What happens after remove? I guess elements following `i` need to be shifted to the left(index decrement by one)? – Chaosfire Oct 08 '22 at 07:52
  • @Icarus i asked whether it's correct, and i was told yes - and that i was also allowed to operate using multiple separate data structures if needed – Enzo Oct 08 '22 at 08:04
  • @Chaosfire you are correct – Enzo Oct 08 '22 at 08:05
  • in arraylist the remove() has O(n). O(1) for deleting at index O(n) for shifting – Icarus Oct 08 '22 at 08:13
  • @Icarus i am aware of that. the problem is that shifting itself has a time complexity, and it defeats the purpose of making remove() O(1) if its going to take another O(n) to shift the rest of the elements – Enzo Oct 08 '22 at 08:18
  • i don't believe it is possible. in fact, if sth like that does exist, we would all be using it. – Icarus Oct 08 '22 at 08:22
  • 2
    This is not possible. You can do all operations in O(log n) time using a B-tree-like structure similar to a rope: https://en.wikipedia.org/wiki/Rope_(data_structure) If you explain your use case, we might be able to advise about how it's usually done. – Matt Timmermans Oct 08 '22 at 12:44

1 Answers1

-1

I can't think of any combination of data structures, which can achieve such performance for all methods, 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? This is probably what ArrayList is doing under the hood when resizing and shifting.

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

Chaosfire
  • 4,818
  • 4
  • 8
  • 23