Is there a concurrent List in Java's JDK?

Question

How can I create a concurrent List instance, where I can access elements by index? Does the JDK have any classes or factory methods I can use?

Answer 1

ConcurrentLinkedQueue

If you don't care about having index-based access and just want the insertion-order-preserving characteristics of a List, you could consider a java.util.concurrent.ConcurrentLinkedQueue. Since it implements Iterable, once you've finished adding all the items, you can loop over the contents using the enhanced for syntax:

Queue<String> globalQueue = new ConcurrentLinkedQueue<String>();

//Multiple threads can safely call globalQueue.add()...

for (String href : globalQueue) {
    //do something with href
}

Answer 2

There is a concurrent list implementation in java.util.concurrent. CopyOnWriteArrayList in particular.

Answer 3

Disclaimer : This answer was published in 2011, before JDK 5, and before much advanced and optimal concurrent APIs. So, while the following will work, it is not the best option.

---

You can very well use Collections.synchronizedList(List) if all you need is simple invocation synchronization:

 List<Object> objList = Collections.synchronizedList(new ArrayList<Object>());

Answer 4

Because the act of acquiring the position and getting the element from the given position naturally requires some locking (you can't have the list have structural changes between those two operations).

The very idea of a concurrent collection is that each operation on its own is atomic and can be done without explicit locking/synchronization.

Therefore getting the element at position n from a given List as an atomic operation doesn't make too much sense in a situation where concurrent access is anticipated.

Answer 5

You have these options:

• Collections.synchronizedList(): you can wrap any List implementation (ArrayList, LinkedList or a 3rd-party list). Access to every method (reading and writing) will be protected using synchronized. When using iterator() or enhanced for loop, you must manually synchronize the whole iteration. While iterating, other threads are fully blocked even from reading. You can also synchronize separately for each hasNext and next calls, but then ConcurrentModificationException is possible.

• CopyOnWriteArrayList: it's expensive to modify, but wait-free to read. Iterators never throw ConcurrentModificationException, they return a snapshot of the list at the moment of iterator creation even if the list is modified by another thread while iterating. Useful for infrequently updated lists. Bulk operations like addAll are preferred for updates - the internal array is copied less many times.

• Vector: very much like synchronizedList(new ArrayList<>()), but iteration is synchronized too. However, iterators can throw ConcurrentModificationException if the vector is modified by another thread while iterating.

Other options:

• Queue or Deque might be an alternative if you only add/remove at the ends of the list or iterate it. Queue allows only adding at one end and removing from the other end, Deque allows adding and removing on both ends. There's no access by index. There are multiple implementations with better concurrency properties than any List can provide. Look at "All Known Implementing Classes" in the Queue javadoc, those implementations that are in the java.util.concurrent package are concurrent. You can also have a look at JCTools, it contains faster queue implementations specialized for single consumer or single producer.
• Collections.unmodifiableList(): wait-free, thread-safe, but non-modifiable
• List.of & List.copyOf: Another non-modifiable list in Java 9 and later.

Answer 6

CopyOnWriteArrayList is a thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

CopyOnWriteArrayList is a concurrent alternative of synchronized List implements List interface and its part of java.util.concurrent packageand its a thread-safe collection.

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException when underlying CopyOnWriteArrayList is modified during Iteration use a separate copy of ArrayList.

This is ordinarily too costly because copy array involved every update operation a cloned copy will be created. CopyOnWriteArrayList is the best choice only for frequent read operation.

/**
         * Returns a shallow copy of this list.  (The elements themselves
         * are not copied.)
         *
         * @return a clone of this list
         */
        public Object clone() {
            try {
                @SuppressWarnings("unchecked")
                CopyOnWriteArrayList<E> clone =
                    (CopyOnWriteArrayList<E>) super.clone();
                clone.resetLock();
                return clone;
            } catch (CloneNotSupportedException e) {
                // this shouldn't happen, since we are Cloneable
                throw new InternalError();
            }
        }

• http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/CopyOnWriteArrayList.html

• https://docs.oracle.com/javase/9/docs/api/java/util/concurrent/CopyOnWriteArrayList.html

• https://www.logicbig.com/tutorials/core-java-tutorial/java-collections/concurrent-collection-cheatsheet.html

Answer 7

Mostly if you need a concurrent list it is inside a model object (as you should not use abstract data types like a list to represent a node in a application model graph) or it is part of a particular service, you can synchronize the access yourself.

class MyClass {
  List<MyType> myConcurrentList = new ArrayList<>();
  void myMethod() {
    synchronzied(myConcurrentList) {
      doSomethingWithList;
    }
  }
}

Often this is enough to get you going. If you need to iterate, iterate over a copy of the list not the list itself and only synchronize the part where you copy the list not while you are iterating over it.

Also when concurrently working on a list you usually do something more than just adding or removing or copying, meaning that the operation becomes meaningful enough to warrent its own method and the list becomes member of a special class representing just this particular list with thread safe behavior.

Even if I agree that a concurrent list implementation is needed and Vector / Collections.sychronizeList(list) do not do the trick as for sure you need something like compareAndAdd or compareAndRemove or get(..., ifAbsentDo), even if you have a ConcurrentList implementation developers often introduce bugs by not considering what is the true transaction when working with a concurrent lists (and maps).

These scenarios where the transactions are too small for what the intended purpose of the interaction with a concurrent ADT (abstract data type) always lead to me hide the list in a special class and synchronizing access to this class objects method using the synchronized on the method level. Its the only way to be sure that the transactions are correct.

I have seen too many bugs to do it any other way - at least if the code is important and handles something like money or security or guarantees some quality of service measures (e.g sending message at least once and only once).