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 can perform well for operation 2 (Insert after index i) if we have a pointer to the node at index i.

Balanced binary trees:

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 NiKS001 2018-08-13 07:28:06 0 (published)
en4 NiKS001 2018-08-13 07:27:35 103 (saved to drafts)
en3 NiKS001 2018-08-13 07:22:23 0 (published)
en2 NiKS001 2018-08-13 07:21:34 776 Completed the content
en1 NiKS001 2018-08-13 06:55:12 522 Initial revision (saved to drafts)