I am looking for a data structure that stores an ordered list of elements E = (K, V) and supports the following operations for no more than O (log (N)) time, where N is the number of elements. Memory usage is not a problem.
- E get (index) // get the item by index
- int find (K) // find the index of the element whose K matches
- delete (index) // delete an item by index, the following indices decrease the indices by 1
- insert (index, E) // insert an element into the index, the following elements increase their indices by 1
I considered the following incorrect solutions:
- Use an array:
find, deleteand insertwill continue to be O (N) - Use array + map K for index:
deleteand insertwill still cost O (N) to move items and update the map. - Use linked list + K map at item address:
getand findwill still cost O (N)
In my imagination, the last solution is the closest, but instead of a linked list, a self-balancing tree in which each node stores the number of elements to the left of it will allow us to do getin O (log (N)).
However, I'm not sure that I'm right, so I want to ask if my imagination is true and if there is a name for such a data structure so that I can look for a ready-made solution.
source
share