alternative to CopyOnWriteArrayList for frequent writes, occasional iterating

Question

I have an ArrayList that is to be cached and shared across multiple threads indefinitely. Operations include frequent adds and removes, plus occasional iterating over it.

The ArrayList lives in a wrapper class which manages access to it:

public class MyListWrapper<T> implements Iterable<T> {

    private List<T> innerList = new ArrayList<T>();

    public Iterator<T> iterator() {
        return innerList.listIterator();
    }

    public void add(T element) {
        innerList.add(element);
        //app-specific logic
    }

    //remove(T), etc in the same pattern...
}

I'm currently making preparations for thread safety. At first, CopyOnWriteArrayList seemed like the best answer, but its performance concerns me, since modifications will be made more often than anything else.

Would a manual change to the wrapper class such as this be a better alternative?:

public Iterator<T> iterator() {
    return new ArrayList<T>(innerList).listIterator();
}

//plus concurrency tweaks for any non-atomic modifications to innerList

Please help me find the best approach.

Answer 1

You could try using a Collections.newSetFromMap(new ConcurrentHashMap<T, Boolean>()); This will give you a concurrent hash set which will give you near O(1) add and remove.

Answer 2

A possibility is to use ConcurrentLinkedQueue if you can live with the Queue interface instead of the List. I would argue that more use cases than you expect may be satisfied with a Queue. One key advantage of List is random access (based on index), but in a concurrent situation random access is neither necessary nor desirable.

ConcurrentLinkedQueue is an excellent concurrent implementation of Queue.