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.↵
↵
~~~~~↵
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.↵
