subList() has a different behavior than other similiar Collections methods, once subList is changed

collections, java

Solution

It's already clear that the behaviour is as per documented. But I think your main question is why is the behaviour different for `ArrayList` and `TreeSet`. Well, it has to do with how data is stored internally in both the collections.

An `ArrayList` internally uses an array to store the data, which is re-sized as the size of `ArrayList` dynamically increases. Now, when you create a `subList` of your given list, original list with the specified indices is associated with the `subList`. So, any structural changes (that screws the indexing of the original array), done in the original list, will make the index stored as a part of sublist meaningless. That is why any structural changes is not allowed in case of `ArrayList#subList` method. The subList method returns you an instance of an `inner` class named `SubList` inside the `ArrayList` class, which looks like:

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

As you see, the `SubList` contains a reference to the original list. And the `parentOffset` is nothing but the starting index of the `subList` you are creating. Now modifying the original `list` will possibly change the value at `fromIndex` in original list, but not inside the `SubList`. In that case, `parentOffset` in `SubList` class and `fromIndex` in original list, will point to different array elements. It might also be possible that at some point the original array becomes shorter enough to invalidate index stored in the `SubList` and make it `OutOfRange`. This is certainly not desirable, and the semantics of the subList returned is considered undefined, on such structural changes to original list.

On the other hand, a `TreeSet` stores it's data internally in a `TreeMap`. Now as there is no such concept of indices in a `Map`, there is no issue of indices breaking up. A `Map` is nothing but a mapping of key-value pair. Creating a SubSet involves creating a SubMap which is backed by the original `Map`. Modifying the original `Set` will just require the corresponding key-value mapping being invalidated, thus propagating the changes to the `subMap` created for the `subSet`.

Problem

Can anyone explain why subList() doesn't behave as subSet() method, and throws a ConcurrentModificationException, while subSet not. Both methods created a Backed Collection, so probably the subList() method designers created this method relying on a unmodifiable original list, but wouldn't be better if all Backed Collections had the same behavior (like subSet())? // code ``` public class ConcurrentModificationException { public static void main(String[] args) { String[] array = {"Java","Python","Pearl","Ada","Javascript","Go","Clojure"}; subListEx(array); subSetEx(array); } private static void subListEx(String[] array) { List<String> l = new ArrayList<String>(Arrays.asList(array)); List<String> l2 = l.subList(2, 4); System.out.println(l.getClass().getName()); // l.add("Ruby"); // ConcurrentModificationException // l.remove(2); // ConcurrentModificationException l2.remove("Ada"); // OK for (String s:l) { System.out.print(s+", "); } System.out.println(); for (String s:l2) { System.out.print(s+", "); } } private static void subSetEx(String[] array) { SortedSet<String> s1 = new TreeSet<String>(Arrays.asList(array)); SortedSet<String> s2 = s1.subSet("Java", "Python"); s1.remove("Ada"); for (String s:s1) { System.out.print(s+", "); } System.out.println(); for (String s:s2) { System.out.print(s+", "); } }} ``` Thanks in advance!

Original source