Efficient Data Structure for random access and random inserts

Правка en4, от NiKS001, 2018-08-13 07:27:35

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.

Теги data structure, container, vector, binary tree, linked lists, array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)