Concurrent ArrayList

Question

I need an ArrayList-like structure allowing just the following operations

• get(int index)
• add(E element)
• set(int index, E element)
• iterator()

Because of the iterator being used in many places, using Collections#synchronizedList would be too error-prone. The list can grow to a few thousand elements and gets used a lot, so I'm pretty sure, that CopyOnWriteArrayList will be too slow. I'll start with it to avoid premature optimizations, but I'd bet it won't work well.

Most accesses will be single-threaded reads. So I'm asking what's the proper data structure for this.

---

I though that wrapping the synchronizedList in something providing a synchronized iterator would do, but it won't because of the ConcurrentModificationException. Concenrning concurrent behavior, I obviously need that all changes will be visible by subsequent reads and iterators.

The iterator doesn't have to show a consistent snapshot, it may or may not see the updates via set(int index, E element) as this operation gets used only to replace an item with its updated version (containing some added information, which is irrelevant for the user of the iterator). The items are fully immutable.

---

I clearly stated why CopyOnWriteArrayList would not do. ConcurrentLinkedQueue is out of question as it lacks an indexed access. I need just a couple of operations rather than a fully fledged ArrayList. So unless any java concurrent list-related question is a duplicate of this question, this one is not.

Answer 1

In your case you can use a ReadWriteLock to access a backed List, this allows multiple Threads to read your list. Only if one Thread needs write access all reader-Thread must wait for the operation to complete. The JavaDoc make's it clear:

A ReadWriteLock maintains a pair of associated locks, one for read-only operations and one for writing. The read lock may be held simultaneously by multiple reader threads, so long as there are no writers. The write lock is exclusive.

Here is a sample:

public class ConcurrentArrayList<T> {

    /** use this to lock for write operations like add/remove */
    private final Lock readLock;
    /** use this to lock for read operations like get/iterator/contains.. */
    private final Lock writeLock;
    /** the underlying list*/
    private final List<T> list = new ArrayList();

    {
        ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
        readLock = rwLock.readLock();
        writeLock = rwLock.writeLock();
    }

    public void add(T e){
        writeLock.lock();
        try{
            list.add(e);
        }finally{
            writeLock.unlock();
        }
    }

    public void get(int index){
        readLock.lock();
        try{
            list.get(index);
        }finally{
            readLock.unlock();
        }
    }

    public Iterator<T> iterator(){
        readLock.lock();
        try {
            return new ArrayList<T>( list ).iterator();
                   //^ we iterate over an snapshot of our list 
        } finally{
            readLock.unlock();
        }
    }