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

User · Answer

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.

User · Answer

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 lt  gt      but iteration is synchronized too  However  iterators can throw ConcurrentModificationException if the vector is modified by another thread while iterating    Other options   Collections unmodifiableList    lock-free  thread-safe  but non-modifiable List of  amp  List copyOf  Another non-modifiable list in Java 9 and later  Queue or Deque might be an alternative if you only add remove at the ends of the list and iterate the list  There s no access by index and no adding removing at arbitrary places  They have multiple concurrent implementations with better performance and better concurrent access  but it s beyond the scope of this question  You can also have a look at JCTools  they contain more performant queue implementations specialized for single consumer or single producer

User · Answer

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 lt String gt  globalQueue   new ConcurrentLinkedQueue lt String gt        Multiple threads can safely call globalQueue add       for  String href   globalQueue          do something with href

User · Answer

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 lt Integer  T gt  in place of ArrayList lt T gt   e g  NavigableMap lt Integer  T gt  map   new ConcurrentSkipListMap lt  gt      This will allow you to add items to the end of the  quot list quot  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  quot list quot   map put map size    item    You can also obviously modify the value of any item in the  quot list quot   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  quot list quot  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 lt V gt  implements List lt V gt        private NavigableMap lt Integer  V gt  map   new ConcurrentSkipListMap lt  gt           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 lt V gt  iterator             return map values   iterator                Override     public Object   toArray             return map values   toArray                Override     public  lt T gt  T   toArray T   a            return map values   toArray a               Override     public V get int index            return map get index               Override     public boolean containsAll Collection lt   gt  c            return map values   containsAll c               Override     public int indexOf Object o            for  Entry lt Integer  V gt  ent   map entrySet                  if  Objects equals ent getValue    o                     return ent getKey                                    return -1              Override     public int lastIndexOf Object o            for  Entry lt Integer  V gt  ent   map descendingMap   entrySet                  if  Objects equals ent getValue    o                     return ent getKey                                    return -1              Override     public ListIterator lt V gt  listIterator int index            return new ListIterator lt V gt                  private int currIdx   0                Override             public boolean hasNext                     return currIdx  lt  map size                                Override             public V next                     if  currIdx  gt   map size                          throw new IllegalArgumentException                               quot next   called at end of list quot                                      return map get currIdx                                 Override             public boolean hasPrevious                     return currIdx  gt  0                              Override             public V previous                     if  currIdx  lt   0                        throw new IllegalArgumentException                               quot previous   called at beginning of list quot                                      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  lt  map size                              throw new UnsupportedOperationException                                              map put currIdx    e                                                          Override     public ListIterator lt V gt  listIterator             return listIterator 0               Override     public List lt V gt  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 lt   extends V gt  c            synchronized  map                for  V val   c                    add val                             return true                        Override     public V set int index  V element            synchronized  map                if  index  lt  0    index  gt  map size                      throw new IllegalArgumentException  quot Index out of range quot                              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  lt  map size                         Insertion is not supported except at end of list                 throw new UnsupportedOperationException                  else if  index  lt  0    index  gt  map size                      throw new IllegalArgumentException  quot Index out of range quot                                 index    map size               add element                         Override     public synchronized boolean addAll              int index  Collection lt   extends V gt  c            synchronized  map                if  index  lt  map size                         Insertion is not supported except at end of list                 throw new UnsupportedOperationException                  else if  index  lt  0    index  gt  map size                      throw new IllegalArgumentException  quot Index out of range quot                                 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 lt   gt  c            throw new UnsupportedOperationException                Override     public boolean retainAll Collection lt   gt  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  quot list quot   map put map isEmpty     0   map lastKey     1  item       Add item before first item in the  quot list quot   map put map isEmpty     0   map firstKey   - 1  item

User · Answer

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

User · Answer

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 lt E gt      implements List lt E gt   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 lt E gt  clone                        CopyOnWriteArrayList lt E gt   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

User · Answer

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 lt MyType gt  myConcurrentList   new ArrayList lt  gt       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

User · Answer

You can very well use Collections synchronizedList List  if all you need is simple invocation synchronization    List lt Object gt  objList   Collections synchronizedList new ArrayList lt Object gt

[java] Is there a concurrent List in Java's JDK?

Examples related to java

Examples related to list

Examples related to concurrency