Efficient Data Structure for random access and random inserts

Revision en5, by NiKS001, 2018-08-13 07:28:06

I have been trying to find a efficient Linear Container Data Structure which can support:

1. Fast access to any index
2. Fast insert after any index

For example:

Initial structure:
Index:  0  1  2  3  4  5
Data:   7 19  1  3 12  2
Accessing index 4 gives 12
Accessing index 5 gives 2
After I insert 5 after index 2:
Index:  0  1  2  3  4  5  6
Data:   7 19  1  5  3 12  2
Accessing index 4 now gives 3
Accessing index 5 gives 12

Vectors:

Vectors perform well for operation 1 (Access index i).

Linked lists:

Linked lists can perform well for operation 2 (Insert after index i) if we have a pointer to the node at index i.

Balanced binary trees:

  1. We can assign indices to every value inserted
  2. If the index is a b-bit number, the first value inserted gets index 2**(b-1)-1
  3. Every new value inserted is assigned an index that is an average of indices of previous and next elements.
  4. In this scheme, we can quickly reach a point where two values have neighboring indices. (Worst case O(b) operations.)

Does anyone have a better solution to handle these operations?

You can also share any known bounds on these operations (supported together) that you are aware of.

Tags data structure, container, vector, binary tree, linked lists, array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English NiKS001 2018-08-13 07:28:06 0 (published)
en4 English NiKS001 2018-08-13 07:27:35 103 (saved to drafts)
en3 English NiKS001 2018-08-13 07:22:23 0 (published)
en2 English NiKS001 2018-08-13 07:21:34 776 Completed the content
en1 English NiKS001 2018-08-13 06:55:12 522 Initial revision (saved to drafts)