A data structure that allows you to access items by index and delete them in O (1)

Question

I have the following task (as part of a larger task):

I need to take element k from the array as a data structure and delete it (k is any possible index). An array has O (n) for deleting elements, and List has O (n) for a search element. I would like to do both operations O (1) times.

What data structure should I use to meet this requirement?

Clarification:

Removing an element by index (5) will move the element from index (6) to index (5).

This task is the problem of topcoder srm 300 div2 500 points. It does not require such a complex data structure (simple java methods will do the job, since the maximum data is really small), but I'm curious how to deal with a much bigger problem using a c-shaped representation of the data.

So maybe I am very attached to this problem? But I will analyze it and edit the question later, after work (if you are really interested, you can see the task on the upper encoder).

Answer 1

I believe that what you are asking for is impossible.

However, if you can relax your indexing requirement to O (log n), then the ropes can satisfy it, although I'm not sure that they have a probabilistic or deterministic guarantee (I think that is probabilistic).

Answer 2

There is a solution that may be satisfactory in some cases. You must use an array and a vector to save deletions. Each time you delete an item, you put its index into the vector. Each time you read an element of an index, you recalculate its index depending on previous deletions.

Let's say you have an array:

 A = [3, 7, 6, 4, 3] 

You remove the 3rd element:

 A = [3, 7, 6, 4, 3] (no actual deletion) d = [3] 

And then read the 4th:

 i = 4 3 < 4 => i += 1 A[i] = 3 

This is not exactly O (1), but still it does not depend on the length of the array. Only for a few deleted items.

Answer 3

The only data structure that has a small overhead when adding and removing an item is a hash table. The only overhead is the cost of the hash function (and it is considered O (1) if you take a purely theoretical approach).

But, if you want it to be extremely effective, you need to:

• Approximately the number of elements that you will need to get inside your data structure (and highlight this number once for all at the beginning).
• Choose a hash function that avoids collisions, given the way your keys are distributed (collisions simply violate the effectiveness of the hash tables).

If you can fix it, then you have to be optimal.

Answer 4

Given the nature of the “dating” problem as given, it involves the constant selection and removal of the “best” member of the set — the classic priority queue. In fact, you need to build two of them (for men and women). You need to either build them in O (NlogN) (sorted list) to permanently delete O (1), or build them in linear time (heap) to remove O (logN). In general, you get O (NlogN) anyway, since you delete the entire one queue and most of the other.

So, the question is which structure supports the other part of the task, choosing the “choice” from the circle and removing it and its choice. Since this also needs to be done N times, any method that performs deletion in O (logN) will not increase the overall complexity of your algorithm. You cannot get indexed access O (1) with quick deletion given the reindexing requirement. But you can get O (logN) for indexed access and deletion using a tree (something like a rope, as indicated). This will give you O (NlogN) as a whole, which is best done anyway.