Data structure for fast insertion and fast random element removal

Question

I'm looking for a data structure that supports the following operations:

add(elem) - Add an element to the data structure.
remove_random() - Remove and return a random element.

The best I got so far is just shuffling a list on every insertion (or on every lookup), and popping from the top. However, this can be quite slow, so I'm looking for a more specialized data structure. Assume we can generate random numbers for free.

Answer 1

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement remove_random() generate a random index $k$ between $1$ and $n$, swap $A[k]$ with $A[n]$ and delete (and return) $A[n]$.

If you want a non-amortized worst-case bound on the time complexity, then an AVL in which each node $v$ has been augmented to also store the size of the subtree rooted in $v$ supports both those operation in $O(\log n)$ worst-case time per operation.

To implement remove_random() simply generate a random number $k$ between $1$ and $n$ and find the element $e$ of rank $k$ in the tree. Then delete $e$ from the tree and return it.

Answer 2

Since you clearly don't care about the order of elements changing, I think the simplest approach is to use a resizable array (like C++'s std::vector or Java's java.util.ArrayList). When you remove an element, if it's not the last element, you just move the last element to take its place.

That gives amortized-constant-time add and constant-time remove_random.

For example, in Java:

public final class Example<E> {
    private final Random random = new Random();
    private final ArrayList<E> elements = new ArrayList<>();

    public void add(final E elem) {
        this.elements.add(elem);
    }

    public E removeRandom() {
        if (this.elements.isEmpty()) {
            throw new NoSuchElementException();
        }
        final int n = this.elements.size();
        Collections.swap(
            this.elements,
            this.random.nextInt(n),
            n - 1);
        return this.elements.remove(n - 1);
    }
}

Answer 3

Another solution that provides amortized constant time operations is to use a dynamic array with insertion and removal at the end, just as in Steven's answer, but swap the last element with a random one after insert, instead of before removal as in Steven's method.

That is, instead of doing what Steven suggests (in pseudocode):

public method insert(element):
   array.push_to_end(element)

public method remove_random():
   swap_last_with_random()
   return array.pop_from_end()

private method swap_last_with_random():
   i = array.length - 1
   j = random(min: 0, max: i)
   array.swap_elements_at(i, j)

you can equivalently do:

public method insert(element):
   array.push_to_end(element)
   swap_last_with_random()

public method remove_random():
   return array.pop_from_end()

with swap_last_with_random() defined as above.

Both of these implementations can be easily shown to work correctly by induction, and they have the same asymptotic time complexity, but their performance in practice may differ.

In particular, with my implementation, multiple consecutive removals require only reading elements sequentially from the end of the array and no writes to the array at all, which might yield a more cache-friendly access pattern. Also, the fact that my method doesn't need to modify the contents of the array during element removal could potentially make implementing efficient concurrent access easier (although it's still not trivial, since removal still changes the length of the array).

All that said, I make no claim that this method is actually any faster in practice than Steven's approach. Depending on your access patterns, it could even be slower. But if performance matters, it's at least worth comparing both of them.