CopyOnWriteList

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

It is more efficient than alternatives i.e. Vector and synchronizedList (java.util. Collections.synchronizedList()) when traversal operations large number mutations.

It is useful when we don't want to synchronize traversals, yet need to prevent the interference among concurrent threads.

The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException.

The iterator will not reflect additions, removals, or changes to the list since the iterator was created.

Element-changing operations on iterators themselves remove, set, and add are not supported. These methods throw UnsupportedOperationException.

    private static class COWSubListIterator<E> implements ListIterator<E> {

        private final ListIterator<E> it;

        private final int offset;

        private final int size;

        COWSubListIterator(List<E> l, int index, int offset, int size) {

            this.offset = offset;

            this.size = size;

            it = l.listIterator(index+offset);

        }

        public boolean hasNext() {

            return nextIndex() < size;

        }

        public E next() {

            if (hasNext())

                return it.next();

            else

                throw new NoSuchElementException();

        }

        public boolean hasPrevious() {

            return previousIndex() >= 0;

        }

        public E previous() {

            if (hasPrevious())

                return it.previous();

            else

                throw new NoSuchElementException();

        }

        public int nextIndex() {

            return it.nextIndex() - offset;

        }

        public int previousIndex() {

            return it.previousIndex() - offset;

        }

        public void remove() {

            throw new UnsupportedOperationException();

        }

        public void set(E e) {

            throw new UnsupportedOperationException();

        }

        public void add(E e) {

            throw new UnsupportedOperationException();

        }

    }

All elements are permitted, including null.

Unlike ConcurrentHashMap, write operations that write or access multiple elements in the list (such as addAll(), retainAll()) will be atomic. During a write operation, the array must be locked completely against other writes.

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

/** Creates an empty list.*/

public CopyOnWriteArrayList() {

    setArray(new Object[0]);

}

/**

 * Creates a list containing the elements of the specified collection,

 * in the order they are returned by the collection's iterator.

 * @throws NullPointerException if the specified collection is null

 */

public CopyOnWriteArrayList(Collection<? extends E> c) {

    Object[] elements;

    if (c.getClass() == CopyOnWriteArrayList.class) {

        elements = ((CopyOnWriteArrayList<?>)c).getArray();

    } else {

        elements = c.toArray();

        // c.toArray might (incorrectly) not return Object[] (see 6260652)

        if (elements.getClass() != Object[].class) {

            elements=Arrays.copyOf(elements, elements.length,Object[].class);

        }

    }

    setArray(elements);

}

/**

 * Creates a list holding a copy of the given array.

 * @throws NullPointerException if the specified array is null

 */

public CopyOnWriteArrayList(E[] toCopyIn) {

    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));

}

/**

 * Returns a shallow copy of this list. 

 * @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();

    }

}

public E get(int index) {

    return get(getArray(), index);

}

// Positional Access Operations

@SuppressWarnings("unchecked")

private E get(Object[] a, int index) {

    return (E) a[index];

}

/**

 * Replaces the element at the specified position in this list

 * with the specified element.

 * @throws IndexOutOfBoundsException

 */

public E set(int index, E element) {

    final ReentrantLock lock = this.lock;

    lock.lock();

    try {

        Object[] elements = getArray();

        E oldValue = get(elements, index);

        if (oldValue != element) {

            int len = elements.length;

            Object[] newElements = Arrays.copyOf(elements, len);

            newElements[index] = element;

            setArray(newElements);

        } else {

            // Not quite a no-op; ensures volatile write semantics

            setArray(elements);

        }

        return oldValue;

    } finally {

        lock.unlock();

    }

}

/**

 * Appends the specified element to the end of this list.

 * @param e element to be appended to this list

 */

public boolean add(E e) {

    final ReentrantLock lock = this.lock;

    lock.lock();

    try {

        Object[] elements = getArray();

        int len = elements.length;

        Object[] newElements = Arrays.copyOf(elements, len + 1);

        newElements[len] = e;

        setArray(newElements);

        return true;

    } finally {

        lock.unlock();

    }

}

/**

 * Inserts the specified element at the specified position in this list.

 * Shifts the element currently at that position (if any) and any subsequent

 * elements to the right (adds one to their indices)

 * @throws IndexOutOfBoundsException

 */

public void add(int index, E element) {

    final ReentrantLock lock = this.lock;

    lock.lock();

    try {

        Object[] elements = getArray();

        int len = elements.length;

        if (index > len || index < 0)

            throw new IndexOutOfBoundsException("Index:"+index+",Size:"+len);

        Object[] newElements;

        int numMoved = len - index;

        if (numMoved == 0)

            newElements = Arrays.copyOf(elements, len + 1);

        else {

            newElements = new Object[len + 1];

            System.arraycopy(elements, 0, newElements, 0, index);

            System.arraycopy(elements, index, newElements, index + 1,

                             numMoved);

        }

        newElements[index] = element;

        setArray(newElements);

    } finally {

        lock.unlock();

    }

}

/**

 * Removes the element at the specified position in this list.

 * Shifts any subsequent elements to the left

 * Returns the element that was removed from the list.

 */

public E remove(int index) {

    final ReentrantLock lock = this.lock;

    lock.lock();

    try {

        Object[] elements = getArray();

        int len = elements.length;

        E oldValue = get(elements, index);

        int numMoved = len - index - 1;

        if (numMoved == 0)

            setArray(Arrays.copyOf(elements, len - 1));

        else {

            Object[] newElements = new Object[len - 1];

            System.arraycopy(elements, 0, newElements, 0, index);

            System.arraycopy(elements, index + 1, newElements, index,

                             numMoved);

            setArray(newElements);

        }

        return oldValue;

    } finally {

        lock.unlock();

    }

}

/**

 * Removes the first occurrence of the specified element from this list,

 * If it is present.

 * If this list does not contain the element, it is unchanged.

 * Returns true if this list contained the specified element.

 * @param o element to be removed from this list, if present

 * @return true if this list contained the specified element

 */

public boolean remove(Object o) {

    Object[] snapshot = getArray();

    int index = indexOf(o, snapshot, 0, snapshot.length);

    return (index < 0) ? false : remove(o, snapshot, index);

}

/**

 * Removes from this list all of the elements whose index is between

 * fromIndex, inclusive, and toIndex, exclusive.

 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range

 * fromIndex < 0 || toIndex > size() || toIndex < fromIndex

 */

void removeRange(int fromIndex, int toIndex) {

    final ReentrantLock lock = this.lock;

    lock.lock();

    try {

        Object[] elements = getArray();

        int len = elements.length;

        if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)

            throw new IndexOutOfBoundsException();

        int newlen = len - (toIndex - fromIndex);

        int numMoved = len - toIndex;

        if (numMoved == 0)

            setArray(Arrays.copyOf(elements, newlen));

        else {

            Object[] newElements = new Object[newlen];

            System.arraycopy(elements, 0, newElements, 0, fromIndex);

            System.arraycopy(elements, toIndex, newElements,

                             fromIndex, numMoved);

            setArray(newElements);

        }

    } finally {

        lock.unlock();

    }

}