Why is Collections.synchronizedList(list) internally using the instanceof check?

Question

I am checking out the source code for Collections class. I came across the method Collections.synchronizedList(list)

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

I fail to undestand why are we checking if list is of RandomAccess type. I understand that ArrayList implements this interface and LinkedList does not.

Also, SynchronizedRandomAccessList inherits SynchronizedList. Then what is the point of this check? Please explain

Answer 1

You're almost there. Collections.synchronizedList(list) checks for RandomAccess because some lists implement RandomAccess while others don't.

This RandomAccess is a marker interface, just like Serializable. It tells whether we can randomly access the items in the list. I.e. from an ArrayList we can retrieve any item with the same computational costs. On the other hand, we need to walk through a LinkedList to get to the nth element.

So, what's happening in Collections.synchronizedList(list)? It wraps the RandomAccess List-s into a RandomAccess synchronized list, while it wraps the non-RandomAccess lists into a non-RandomAccess synchronized lists. Otherwise those lists are identical. Below is the code of SynchronizedRandomAccessList. This is a good example for programming by difference. The two classes are almost identical.

static class SynchronizedRandomAccessList<E>
    extends SynchronizedList<E>
    implements RandomAccess {

    SynchronizedRandomAccessList(List<E> list) {
        super(list);
    }

    SynchronizedRandomAccessList(List<E> list, Object mutex) {
        super(list, mutex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        synchronized (mutex) {
            return new SynchronizedRandomAccessList<>(
                list.subList(fromIndex, toIndex), mutex);
        }
    }

    private static final long serialVersionUID = 1530674583602358482L;

    /**
     * Allows instances to be deserialized in pre-1.4 JREs (which do
     * not have SynchronizedRandomAccessList).  SynchronizedList has
     * a readResolve method that inverts this transformation upon
     * deserialization.
     */
    private Object writeReplace() {
        return new SynchronizedList<>(list);
    }
}

You might ask, what's the point for RandomAccess interface? As Holger pointed out, Collections.binarySearch() makes decisions based on this interface. Another example is Collections.reverse().

Answer 2

You have to recall the original purpose of the RandomAccess marker interface. If you pass a List to another method, it should be able to choose an algorithm suitable for random access or sequential lists. Choosing the right algorithm requires testing for the marker interface via list instanceof RandomAccess.

To show one example

public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
 }

(See also reverse, shuffle, copy, and fill)

Now, if you just wrap the list into another object implementing the List interface, all such methods see, is the wrapper object, so this information is lost. However, wrappers like the synchronized list do not change the time complexity of random access methods like get. Hence, it is desired that if the wrapped list is a random access list, the wrapper should implement RandomAccess too, so that methods receiving such a wrapper are still able to detect whether fast random access is available or not.

If you look at the implementation of SynchronizedRandomAccessList, you will see that all it does, is extending SynchronizedList and implementing RandomAccess, to inherit the behavior and marking itself as having fast random access. The only method it overrides, is subList, for exactly the same reason. If the list has efficient random access, its sub lists have as well, so they should implement RandomAccess too.

static class SynchronizedRandomAccessList<E>
    extends SynchronizedList<E>
    implements RandomAccess {

    SynchronizedRandomAccessList(List<E> list) {
        super(list);
    }

    SynchronizedRandomAccessList(List<E> list, Object mutex) {
        super(list, mutex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        synchronized (mutex) {
            return new SynchronizedRandomAccessList<>(
                list.subList(fromIndex, toIndex), mutex);
        }
    }

Note that other wrapper factories like checkedList follow the same pattern. So this even works when combining the factories:

System.out.println(
    Collections.synchronizedList(Collections.checkedList(new ArrayList<>(), String.class))
    instanceof RandomAccess);

→ true

System.out.println(
    Collections.synchronizedList(Collections.checkedList(new LinkedList<>(), String.class))
    instanceof RandomAccess);

→ false