Why do I get an UnsupportedOperationException when trying to remove an element from a List?

Question

I have this code:

public static String SelectRandomFromTemplate(String template,int count) {
   String[] split = template.split("|");
   List<String> list=Arrays.asList(split);
   Random r = new Random();
   while( list.size() > count ) {
      list.remove(r.nextInt(list.size()));
   }
   return StringUtils.join(list, ", ");
}

I get this:

06-03 15:05:29.614: ERROR/AndroidRuntime(7737): java.lang.UnsupportedOperationException
06-03 15:05:29.614: ERROR/AndroidRuntime(7737):     at java.util.AbstractList.remove(AbstractList.java:645)

How would be this the correct way? Java.15

Solution 1

Quite a few problems with your code:

On Arrays.asList returning a fixed-size list

From the API:

Arrays.asList: Returns a fixed-size list backed by the specified array.

You can't add to it; you can't remove from it. You can't structurally modify the List.

Fix

Create a LinkedList, which supports faster remove.

List<String> list = new LinkedList<String>(Arrays.asList(split));

---

On split taking regex

From the API:

String.split(String regex): Splits this string around matches of the given regular expression.

| is a regex metacharacter; if you want to split on a literal |, you must escape it to \|, which as a Java string literal is "\\|".

Fix:

template.split("\\|")

---

On better algorithm

Instead of calling remove one at a time with random indices, it's better to generate enough random numbers in the range, and then traversing the List once with a listIterator(), calling remove() at appropriate indices. There are questions on stackoverflow on how to generate random but distinct numbers in a given range.

With this, your algorithm would be O(N).

Solution 2

This one has burned me many times. Arrays.asList creates an unmodifiable list. From the Javadoc: Returns a fixed-size list backed by the specified array.

Create a new list with the same content:

newList.addAll(Arrays.asList(newArray));

This will create a little extra garbage, but you will be able to mutate it.

Solution 3

Probably because you're working with unmodifiable wrapper.

Change this line:

List<String> list = Arrays.asList(split);

to this line:

List<String> list = new LinkedList<>(Arrays.asList(split));

Solution 4

The list returned by Arrays.asList() might be immutable. Could you try

List<String> list = new ArrayList<>(Arrays.asList(split));

Solution 5

I think that replacing:

List<String> list = Arrays.asList(split);

with

List<String> list = new ArrayList<String>(Arrays.asList(split));

resolves the problem.

View more solutions

Comments

[Roman]

he's deleting, ArrayList is not the best data structure for deleting its values. LinkedList feets much more for his problem.

[Jack Leow]

Minor point, but you aren't "wrapping" the original list, you are creating a completely new list (which is why it works).

[Dimitris Andreou]

Arrays.asList() is not an unmodifiable wrapper.

[Pentium10]

Thanks, I have only limited elements in the string <10 so won't be an optimization problem.

[Dimitris Andreou]

Wrong regarding the LinkedList. He is accessing by index, so LinkedList would spend as much time to find an element through iteration. See my answer for a better approach, using an ArrayList.

[Roman]

@polygenelubricants: it seems you mix up unmodifiable and immutable. unmodifiable means exactly "modifiable, but not structurally".

[polygenelubricants]

@Pentium: one more thing: you shouldn't be creating a new instance of Random everytime. Make it a static field and seed it only once.

[polygenelubricants]

I just tried creating an unmodifiableList wrapper and trying a set; it throws UnsupportedOperationException. I'm quite certain Collections.unmodifiable* really means full immutability, not just structural.

[polygenelubricants]

+1 for the algorithm, though OP says that there's only 10 elements. And nice way of using the random numbers with ArrayList. Much simpler than my suggestion. I think it would result in reordering of the elements though.

[gengkev]

Is LinkedList really faster? Both LinkedList and ArrayList have O(n) remove here :\ It's almost always better to just use an ArrayList

[torno]

LinkedList vs ArrayList -->There is a performance test graph from Ryan. LinkedList is faster in removing.

[Alexander]

LinkedList only really faster at removal when the node to be removed is already known. If you're trying to remove an element, the list must be traversed, with each element being compared until the correct one is found. If you're trying to remove by index, n traversals must be done. These traversals are super expensive, and the worst case for CPU caching: many jumps around memory in unpredictable ways. See: youtube.com/watch?v=YQs6IC-vgmo

[cs94njw]

Yup, I used Arrays.asList() in my JUnit test case, which then was stored inside my map. Changed my code to copy the list passed in, into my own ArrayList.

[SMBiggs]

Your solution doesn't work in my situation, but thanks for the explanation. The knowledge you provided led to my solution.

[Nathan Ripert]

Reading those comments 7 years later I allow myself to indicate this link: stackoverflow.com/questions/8892350/… likely to fix the difference between immutable and unmodifiable, discussed here.

[6rchid]

@Alexander Yes, you can say the same for an array. The first step to removing an element is by traversing n times until you find the element, you can't skip this unless it's a map or a table. However, the removing process is O(1) in a linked list because once you remove the node. Its referencing node only changes its reference to the next exiting node. Whereas in an array, you need to shift every element n times after an element is removed from the array.

[Alexander]

@NocTurn I'm aware. However, array shifting is a significantly faster operation than the arbitrary pointer chasing of linked list traversal. In total, it's still rarely better. I encourage you to watch the video I linked.

[drmrbrewer]

When I use the suggested List<String> list = new LinkedList(Arrays.asList(split)); how do I avoid the annoying lint warning "raw use of parameterised class LinkedList"... usually warnings are there for a reason so I'd rather not just suppress it...

[Paŭlo Ebermann]

@drmrbrewer You need to use the type parameter of the class. Either new LinkedList<String>(...) or new LinkedList<>(...) (which lets the compiler find out the type parameter). Just new LinkedList(...) creates a "raw" (unparameterized) linked list, which should be avoided.

[Paŭlo Ebermann]

Yeah, Array.asList is not an unmodifiable wrapper, and "modifiable, but not structurally" certainly is not the same as "unmodifiable".

[drmrbrewer]

@PaŭloEbermann perfect, thanks... new LinkedList<>(...) is what I used because specifying the type explicitly produces a lint warning of its own.

[Dervillers Mattéo]

10 years and 8 months later.. it's already usefull !

[Donald Duck]

It also works to do new ArrayList<>(Arrays.asList(...)).