367

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?

6
  • 30
    Why not constructive? Several proposed CopyOnWriteArrayList that is not found in .Net. You can say that both questions relate to each other but not to close this one!!! Aug 3, 2011 at 7:11
  • 1
    I have no idea why Jarrod Roberson would think it was a good idea to take the detailed edits made by Stephan and revert them back to the original, poorly-phrased question. Jarrod's answer is still a perfectly acceptable one. In fact, CopyOnWriteArrayList is the only concurrent class implementing List in the JDK. Puzzled... Jul 20, 2015 at 14:08
  • 13
    Because the accepted answer was to the original question and Stephan put a completely unrelated question with a bunch of source code that the original poster did not include anywhere changing the question completely, which generated more answers that were suggesting things other than the List which the original specifically says is a requirement which is considered vandalism. A moderator already locked the question because of the people that are complaining that the answers do not answer that vandalized version of the question.
    – user177800
    Jul 20, 2015 at 15:13
  • 1
    /locked/closed/ previous comment
    – user177800
    Jul 20, 2015 at 15:49
  • 11
    There's no reason for this question to be closed. It asks about classes in the JDK, which is nothing like searching for a library; it's the base of Java.
    – maaartinus
    Sep 2, 2018 at 17:10

8 Answers 8

242

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
}
7
  • 4
    I think that the simplified for statement (:) is called foreach: docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html Sep 3, 2014 at 6:16
  • 2
    @AlikElzin-kilaka You're right. I think that name has always bothered me, because the actual syntax doesn't include the word "each", but I'll update the answer to use the official name. :) Sep 3, 2014 at 13:05
  • 4
    @AlikElzin-kilaka Nitpicking, but according to the JLS version 8 it is called the "enhanced for statement". The same in the java tutorial.
    – Roland
    May 24, 2017 at 6:38
  • 1
    @Roland definitely NOT nitpicking. There is (now) a difference between "for each" and "enhanced for" in Java.
    – hfontanez
    Nov 27, 2018 at 21:37
  • 4
    @Roland indirectly. I believe they renamed the "for each loop" to "enhanced for" to eliminate confusion between the Stream.forEach and what is now known as the enhanced for.
    – hfontanez
    Dec 4, 2018 at 17:24
214

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

4
  • 101
    Note it copies the whole list on every insert, so it is often inefficient.
    – dfrankow
    Mar 28, 2013 at 12:56
  • 27
    @dfrankow But it can more more efficient if you're iterating much more than you're updating.
    – arkon
    Jul 18, 2015 at 18:13
  • Doesn't work well as shown here. I have exceptions even though I just use its addAll method and read it using stream. stackoverflow.com/questions/1527519/…
    – devssh
    Mar 26, 2018 at 10:01
  • 1
    This answer – accepted and with 200+ upvotes – is misleading as being the right way to solve concurrency with an ArrayList. As the earlier comments describe, CopyOnWriteArrayList is not a good fit if the usage is mostly writes, with few reads. The answer posted by @Oliv is more complete and informative.
    – Kaan
    Jul 13, 2022 at 19:52
165

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>());
2
  • 86
    The result of synchronizedList is "synchronized" but not "concurrent". One fundamental issue that many List operations -- which are index-based -- are themselves not atomic and need to be part of a larger mutual exclusion construct.
    – user166390
    Aug 2, 2011 at 18:02
  • 6
    IMO, asing a Vector is more straightforward rather than Collections.synchronizedList(new ArrayList<Object>()).
    – Stephan
    Nov 21, 2013 at 16:05
62

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.

2
  • 8
    Joachim, I think you hit the nail on the head. Take for example, a read-only list as a concurrent list. Getting the element at position N from the list not only makes sense, but it is the nutshell of the problem. So, an immutable list (lower case L) would be a good example, but it is not a List (upper case L). The CopyOnWriteArrayList is concurrent, but many people don't like the performance. A solution along the lines of ropes (string ropes) would probably be a good winner.
    – johnstosh
    Oct 8, 2013 at 12:12
  • 2
    Very good point. But the List the OP is going use might have very specific usage. E.g. it might be filled in concurrent environment, then "locked" (whatever it means) and then accessed safely by index. So, in the first phase of filling such a List will still require a thread-safe implementation. Unfortunately, the OP was not specific about how the List he is looking for is going to be used.
    – igor.zh
    Feb 5, 2018 at 21:51
47

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.
8

enter image description here

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();
            }
        }
0

If you never plan to delete elements from the list (since this requires changing the index of all elements after the deleted element), then you can use ConcurrentSkipListMap<Integer, T> in place of ArrayList<T>, e.g.

NavigableMap<Integer, T> map = new ConcurrentSkipListMap<>();

This will allow you to add items to the end of the "list" as follows, as long as there is only one writer thread (otherwise there is a race condition between map.size() and map.put()):

// Add item to end of the "list":
map.put(map.size(), item);

You can also obviously modify the value of any item in the "list" (i.e. the map) by simply calling map.put(index, item).

The average cost for putting items into the map or retrieving them by index is O(log(n)), and ConcurrentSkipListMap is lock-free, which makes it significantly better than say Vector (the old synchronized version of ArrayList).

You can iterate back and forth through the "list" by using the methods of the NavigableMap interface.

You could wrap all the above into a class that implements the List interface, as long as you understand the race condition caveats (or you could synchronize just the writer methods) -- and you would need to throw an unsupported operation exception for the remove methods. There's quite a bit of boilerplate needed to implement all the required methods, but here's a quick attempt at an implementation.

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NavigableMap;
import java.util.Objects;
import java.util.Map.Entry;
import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentAddOnlyList<V> implements List<V> {
    private NavigableMap<Integer, V> map = new ConcurrentSkipListMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return map.values().contains(o);
    }

    @Override
    public Iterator<V> iterator() {
        return map.values().iterator();
    }

    @Override
    public Object[] toArray() {
        return map.values().toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return map.values().toArray(a);
    }

    @Override
    public V get(int index) {
        return map.get(index);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return map.values().containsAll(c);
    }

    @Override
    public int indexOf(Object o) {
        for (Entry<Integer, V> ent : map.entrySet()) {
            if (Objects.equals(ent.getValue(), o)) {
                return ent.getKey();
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        for (Entry<Integer, V> ent : map.descendingMap().entrySet()) {
            if (Objects.equals(ent.getValue(), o)) {
                return ent.getKey();
            }
        }
        return -1;
    }

    @Override
    public ListIterator<V> listIterator(int index) {
        return new ListIterator<V>() {
            private int currIdx = 0;

            @Override
            public boolean hasNext() {
                return currIdx < map.size();
            }

            @Override
            public V next() {
                if (currIdx >= map.size()) {
                    throw new IllegalArgumentException(
                            "next() called at end of list");
                }
                return map.get(currIdx++);
            }

            @Override
            public boolean hasPrevious() {
                return currIdx > 0;
            }

            @Override
            public V previous() {
                if (currIdx <= 0) {
                    throw new IllegalArgumentException(
                            "previous() called at beginning of list");
                }
                return map.get(--currIdx);
            }

            @Override
            public int nextIndex() {
                return currIdx + 1;
            }

            @Override
            public int previousIndex() {
                return currIdx - 1;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }

            @Override
            public void set(V e) {
                // Might change size of map if currIdx == map.size(),
                // so need to synchronize 
                synchronized (map) {
                    map.put(currIdx, e);
                }
            }

            @Override
            public void add(V e) {
                synchronized (map) {
                    // Insertion is not supported except at end of list
                    if (currIdx < map.size()) {
                        throw new UnsupportedOperationException();
                    }
                    map.put(currIdx++, e);
                }
            }
        };
    }

    @Override
    public ListIterator<V> listIterator() {
        return listIterator(0);
    }

    @Override
    public List<V> subList(int fromIndex, int toIndex) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean add(V e) {
        synchronized (map) {
            map.put(map.size(), e);
            return true;
        }
    }

    @Override
    public boolean addAll(Collection<? extends V> c) {
        synchronized (map) {
            for (V val : c) {
                add(val);
            }
            return true;
        }
    }

    @Override
    public V set(int index, V element) {
        synchronized (map) {
            if (index < 0 || index > map.size()) {
                throw new IllegalArgumentException("Index out of range");
            }
            return map.put(index, element);
        }
    }

    @Override
    public void clear() {
        synchronized (map) {
            map.clear();
        }
    }

    @Override
    public synchronized void add(int index, V element) {
        synchronized (map) {
            if (index < map.size()) {
                // Insertion is not supported except at end of list
                throw new UnsupportedOperationException();
            } else if (index < 0 || index > map.size()) {
                throw new IllegalArgumentException("Index out of range");
            }
            // index == map.size()
            add(element);
        }
    }

    @Override
    public synchronized boolean addAll(
            int index, Collection<? extends V> c) {
        synchronized (map) {
            if (index < map.size()) {
                // Insertion is not supported except at end of list
                throw new UnsupportedOperationException();
            } else if (index < 0 || index > map.size()) {
                throw new IllegalArgumentException("Index out of range");
            }
            // index == map.size()
            for (V val : c) {
                add(val);
            }
            return true;
        }
    }

    @Override
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(int index) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }
}

Don't forget that even with the writer thread synchronization as shown above, you need to be careful not to run into race conditions that might cause you to drop items, if for example you try to iterate through a list in a reader thread while a writer thread is adding to the end of the list.

You can even use ConcurrentSkipListMap as a double-ended list, as long as you don't need the key of each item to represent the actual position within the list (i.e. adding to the beginning of the list will assign items negative keys). (The same race condition caveat applies here, i.e. there should be only one writer thread.)

// Add item after last item in the "list":
map.put(map.isEmpty() ? 0 : map.lastKey() + 1, item);

// Add item before first item in the "list":
map.put(map.isEmpty() ? 0 : map.firstKey() - 1, item);
-1

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).

3
  • 3
    Synchronized locks so only 1 thread can access. Concurrent means multiple thread access with minimum locks. Oct 6, 2020 at 10:00
  • First minimum locks is an arbitrary notion. Within a synchronized block the thread has exclusive access to a certain resource. But observing multiple processes from the outside would yield in the conclusion that multiple threads/'processes' could access the same resource (concurrent list) 'simultaneously' but in a thread safe fashion. e.g. One thread adds 100 elements one by one while another thread access the same list and copies it when the list contains 50 elements. That is called simultaneous or concurrent access of the resource as both threads access the same resource. Oct 10, 2020 at 22:13
  • To let other threads wait while a not thread safe resource is accessed is a fully valid approach to implement concurrency. I do not think this answer should be voted down. Especially with lists in many cases I would prefer to access a very fast ArrayList with locking when I do not have to access a very large list very often than to CopyOnWrite for example which can be very costly. Dec 3, 2021 at 20:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.