Efficient data structure for fast random access, search, insertion and deletion
Posted
by Leonel
on Stack Overflow
See other posts from Stack Overflow
or by Leonel
Published on 2009-05-20T21:28:49Z
Indexed on
2010/04/28
6:53 UTC
Read the original article
Hit count: 306
I'm looking for a data structure (or structures) that would allow me keep me an ordered list of integers, no duplicates, with indexes and values in the same range.
I need four main operations to be efficient, in rough order of importance:
- taking the value from a given index
- finding the index of a given value
- inserting a value at a given index
- deleting a value at a given index
Using an array I have 1 at O(1), but 2 is O(N) and insertion and deletions are expensive (O(N) as well, I believe).
A Linked List has O(1) insertion and deletion (once you have the node), but 1 and 2 are O(N) thus negating the gains.
I tried keeping two arrays a[index]=value and b[value]=index, which turn 1 and 2 into O(1) but turn 3 and 4 into even more costly operations.
Is there a data structure better suited for this?
© Stack Overflow or respective owner