Efficient Data Structure for random access and random inserts
Difference between en4 and en5, changed 0 character(s)
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.↵

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)