Ordered list with O(1) random access and removal

Question

Does there exist a data structure with the following properties:

• Elements are stored in some order
• Accessing the element at a given index takes O(1) time (possibly amortized)
• Removing an element takes amortized O(1) time, and changes the indices appropriately (so if element 0 is removed, the next access to element 0 should return the old element 1)

For context, I reduced an algorithm question from a programming competition to:

Over m queries, return the kth smallest positive number that hasn't been returned yet. You can assume the returned number is less than some constant n.

If the data structure above exists, then you can do this in O(m) time, by creating a list of numbers 1 to n. Then, for each query, find the element at index k and remove it. During the contest itself, my solution ended up being O(m^2) on certain inputs.

I'm pretty sure you can do this in O(m log m) with binary search trees, but I'm wondering if the ideal O(m) is reachable. Stuff I've found online tends to be close, but not quite there - the tricky part is that the elements you remove can be from anywhere in the list.

Answer 1

1. well the O(1) removal is possible with linked list

   each element has pointer to next and previous element so removal just deletes element and sets the pointers of its neighbors like:

   element[ix-1].next=element[ix+1].prev
   

2. accessing ordered elements at index in O(1) can be done with indexed arrays

   so you have unordered array like dat[] and index array like idx[] the access of element ix is just:

   dat[idx[ix]]
   

3. Now the problem is to have these properties at once

   you can try to have linked list with index array but the removal needs to update index table which is O(N) in the worst case.

   if you have just index array then the removal is also O(N)

   if you have the index in some form of a tree structure then the removal can be close to O(log(N)) but the access will be also about O(log(N))

Answer 2

I believe there is a structure that would do both of this in O(n) time, where n was the number of points which had been removed, and not the total size. So if the number you're removing is small compared to the size of the array, it's close to O(1).

Basically, all the data is stored in an array. There is also a priority queue for deleted elements. Initialise like so:

Data = [0, 1, 2, ..., m]
removed = new list

Then, to remove an element, you add it's original index (see below for how to get this) to the priority queue (which is sorted by size of element with smallest at the front), and leave the array as is. So removing the 3rd element:

Data = [0, 1, 2, 3,..., m]
removed = 2

Then what's now the 4th and was the 5th:

Data = [0, 1, 2, 3,..., m]
removed = 2 -> 4

Then what's now the 3rd and was the 4th:

Data = [0, 1, 2, 3,..., m]
removed = 2 -> 3 -> 4

Now to access an element, you start with it's index. You then iterate along the removed list, increasing the index by one each time, until you reach an element which is larger than the increased value of the index. This will give you the original index(ie. position in Data) of the element you're looking for, and is the index you needed for removal.

This operation of iterating along the queue effectively increases the index by the number of elements before it that were removed.

Sorry if I haven't explained very well, it was clear in my head but hard to write down.

Comments:

• Access is O(n), with n number of removed items
• Removal is approximately twice the time of access, but still O(n)
• A disadvantage is that memory use doesn't shrink with removal.
• Could potentially 're-initialise' when removed list is large to reset memory use and access and removal times. This operation takes O(N), with N total array size.

So it's not quite what OP was looking for but in the right situation could be close.