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?
8 Answers
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
}
-
4I 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.– RolandMay 24, 2017 at 6:38
-
1@Roland definitely NOT nitpicking. There is (now) a difference between "for each" and "enhanced for" in Java. 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. Dec 4, 2018 at 17:24
There is a concurrent list implementation in java.util.concurrent. CopyOnWriteArrayList in particular.
-
101Note it copies the whole list on every insert, so it is often inefficient.– dfrankowMar 28, 2013 at 12:56
-
27@dfrankow But it can more more efficient if you're iterating much more than you're updating.– arkonJul 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/…– devsshMar 26, 2018 at 10:01
-
1This 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.– KaanJul 13, 2022 at 19:52
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>());
-
86The 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.– user166390Aug 2, 2011 at 18:02 -
6IMO, asing a
Vector
is more straightforward rather thanCollections.synchronizedList(new ArrayList<Object>())
.– StephanNov 21, 2013 at 16:05
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.
-
8Joachim, 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. Oct 8, 2013 at 12:12
-
2Very 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.zhFeb 5, 2018 at 21:51
You have these options:
Collections.synchronizedList()
: you can wrap anyList
implementation (ArrayList
,LinkedList
or a 3rd-party list). Access to every method (reading and writing) will be protected usingsynchronized
. When usingiterator()
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 eachhasNext
andnext
calls, but thenConcurrentModificationException
is possible.CopyOnWriteArrayList
: it's expensive to modify, but wait-free to read. Iterators never throwConcurrentModificationException
, 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 likeaddAll
are preferred for updates - the internal array is copied less many times.Vector
: very much likesynchronizedList(new ArrayList<>())
, but iteration is synchronized too. However, iterators can throwConcurrentModificationException
if the vector is modified by another thread while iterating.
Other options:
Queue
orDeque
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 anyList
can provide. Look at "All Known Implementing Classes" in the Queue javadoc, those implementations that are in thejava.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-modifiableList.of
&List.copyOf
: Another non-modifiable list in Java 9 and later.
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();
}
}
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);
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).
-
3Synchronized 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
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.locked
/closed
/ previous comment