Java: Why does calling `remove()` on a List throw UnsupportedOperation exception?

Question

For some reason, I'm getting an UnsupportedOpeationException with the following code. Examining it in the debugger, it looks like the object I'm calling remove() on is a list.

// to optimize, remove totalSize. After taking an item from lowest, if lowest is empty, remove it from `lists`
// lists are sorted to begin with
public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
 List<T> result = new ArrayList<T>();
 HashMap<List<T>, Integer> location = new HashMap<List<T>, Integer>();

 int totalSize = 0; // every element in the set
 for (List<T> l : lists) {
  location.put(l, 0);
  totalSize += l.size();
 }

 boolean first;
 List<T> lowest = lists.iterator().next(); // the list with the lowest item to add
 int index;

 while (result.size() < totalSize) { // while we still have something to add
  first = true;

  for (List<T> l : lists) {
   if (! l.isEmpty()) {
    if (first) {
     lowest = l;
    }
    else if (l.get(location.get(l)).compareTo(lowest.get(location.get(lowest))) <= 0) {
     lowest = l;
    }
   }
  }
  index = location.get(lowest);
  result.add(lowest.get(index));
  lowest.remove(index); //problem here
 }
 return result;
}

The exception:

Exception in thread "main" java.lang.UnsupportedOperationException
    at java.util.AbstractList.remove(Unknown Source)
    at interview.questions.MergeLists.merge(MergeLists.java:72)
    at interview.questions.MergeLists.main(MergeLists.java:32)

Why is this happening?

Answer 1

It's quite possible the underlying implementation of List you received is fixed-length, such as one created by Arrays#asList.

Answer 2

Could it be that the Lists you pass in the set are derived from AbstractList and do not implement (support) the remove() method?

Also, it seems that location always maps to 0 for all list object that are mapped in the location HashMap?

Answer 3

If you look at the API docs for the List interface you will see that a number of them are "optional operations". That means that a concrete class is permitted to throw the UnsupportedOperationException.

If, for example, the List was converted to an unmodifiable list it could not allow the remove operation to actually remove something (or the list would be modified).

So for the Set< List<>> part of the code one or mnre of the lists does not allow you to remove from it.

Answer 4

It is optional for a class implementing the Collection interface to allow objects to be removed (see Collection#remove() which is an optional operation). As stated in the javadoc, it throws

UnsupportedOperationException - if the remove operation is not supported by this collection

You are likely in that case (e.g. if your set contains a list returned by Arrays.asList as pointed out by Jeffrey).

Answer 5

The remove() method in the Collection interface is explicitly specified as an optional operation:

remove(Object o)
          Removes a single instance of the specified element from this collection, if it is present (optional operation).

Lists do not have to support in. In fact, there is no clear semantics for it. Lists are not meant for that sort of random-access. Rather than provide some default implementation that may be inefficient or inaccurate, you get the exception.

You can write your own utility method with a for-each loop to do this if it is critical.

Answer 6

If you are going to be removing items from a List, then rather than use a for-each loop to iterate through the list, you should be using a ListIterator, which supports remove() in a safe manner (i.e. without leaving holes in the list or an index pointing to nowhere).