Collection with constant time insertion (amortised) and constant time uniform random removal

RandomColl.java

import java.util.*;

public class RandomColl<T> {
    ArrayList<T> lst;
    Random rng;
    public RandomColl() {
        lst = new ArrayList<>();
        rng = new Random();
    }

    public void add(T elem) {
        lst.add(elem);
    }
    public T remove() {
        if (lst.size() == 0) {
            throw new NoSuchElementException();
        }
        int elemIdx = rng.nextInt(lst.size());
        T last = lst.remove(lst.size() - 1);
        if (lst.size() == elemIdx) {
            return last;
        } else {
            T elem = lst.get(elemIdx);
            lst.set(elemIdx, last);
            return elem;
        }
    }
    // sample usage
    public static void main(String[] args) {
        RandomColl<Integer> rc = new RandomColl<>();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                rc.add(i*10 + j);
            }
            for (int j = 0; j < 5; j++) {
                System.out.println(rc.remove());
            }
        }
    }
}