SkipList and CopyOnWrite Collections

SkipList classes, ConcurrentSkipListSet and ConcurrentSkipListMap, are concurrent versions of their sorted counterparts, TreeSet and TreeMap, respectively. They maintain their elements or keys in the natural ordering of their elements.

CopyOnWrite collections (CopyOnWriteArrayList and CopyOnWriteArraySet) copy all of their elements to a new underlying structure anytime an element is added or removed from the collection. It means that the reference in the collection is changed. Modifying the actual contents of the collection will not cause a new structure to be allocated.

Although the data is copied to a new underlying structure, reference to the object does not change. This is particularly useful in multi-threaded environments that need to iterate the collection. Any  iterator established prior to a modification will not see the changes, but instead it will iterate over the original elements prior to the modification. See example below :

public class CopyOnWriteArrayListExample {
    public static void main(String[] args) {
        List<Integer> list = new CopyOnWriteArrayList<>(Arrays.asList(4,3,52));
        for (Integer item : list) {
            System.out.print(item + " ");

        System.out.println("List contents: " + list);

The output will be :

4 3 52
List contents: [4, 3, 52, 9, 9, 9]

Despite adding elements to the array while iterating over it, only those elements in the collection at the time the for() loop was created were accessed. If using regular ArrayList object, a ConcurrentModificationException will occur at runtime. With either class, though, infinite loop, in which elements are constantly added to the array when iterating, is avoided.

The CopyOnWrite classes can use a lot of memory, since a new collection structure needs be allocated anytime the collection is modified. They are commonly used in multi-threaded environment situations where reads are far more common than writes.

Leave a Reply

Your email address will not be published. Required fields are marked *