Efficient Data Structure for random access and random inserts

Правка en3, от NiKS001, 2018-08-13 07:22:23

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?

Теги 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)