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**:

- We can assign indices to every value inserted
- If the index is a b-bit number, the first value inserted gets index 2**(b-1)-1
- Every new value inserted is assigned an index that is an average of indices of previous and next elements.
- 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.