Adding and removing items to a Guava ImmutableList

Question

In Guava, is there an efficient way to add or remove items to an ImmutableList (creating new Lists in the process, of course).

The simplest way I can come up with is this:

private ImmutableList<String> foos = ImmutableList.of();

public void addFoo(final String foo) {
    if (this.foos.isEmpty()) {
        foos = ImmutableList.of(foo);
    } else {
        foos = ImmutableList.<String>builder().addAll(foos).add(foo).build();
    }
}

public void removeFoo(final String foo) {
    final int index = this.foos.indexOf(foo);
    if (index > -1) {
        final Builder<String> builder = ImmutableList.<String>builder();
        if (index > 0) builder.addAll(this.foos.subList(0, index));
        final int size = this.foos.size();
        if (index < size - 1) builder.addAll(this.foos.subList(index+1, size));
        this.foos = builder.build();
    }
}

What I would like to avoid doing is this:

public void removeFoo(final String foo) {
    final ArrayList<String> tmpList = Lists.newArrayList(this.foos);
    if(tmpList.remove(foo))this.foos=ImmutableList.copyOf(tmpList);
}

But unfortunately it is so much simpler than any Guava-only method I can think of. Have I missed something?

What higher level problem are you trying to solve? Maybe you shouldn't be dealing with immutable lists if you need to change them. — sjr, Oct 17 '12 at 15:42
I know I can solve the problem easily when resorting to mutable Lists as inbetween data holders but a) I have to create superfluous intermediate collections and b) I have to mix java.util Collections with guava ImmutableCollections, while I'd like to stick to one paradigm. And I would like to use an ImmutableList because I want to hand it out to clients in a `getFoos()` method without losing control or having to create lots of Collections.unmodifiableList wrapper objects. — Sean Patrick Floyd, Oct 17 '12 at 15:50
Then I would use a mutable List as instance field and in getFoos() return ImmutableList.copyOf(list). — Christoph Leiter, Oct 17 '12 at 16:21
@ChristophLeiter yes, but that means a) a full traversal for every single read (I'm thinking of scenarios where reads are a lot more common than calls to add / remove), b) I'd have to synchronize everything in order to avoid ConcurrentModificationExceptions. Of course my examples above aren't synchronized either, but they don't throw ConcurrentModificationExceptions. — Sean Patrick Floyd, Oct 17 '12 at 16:37

Frank Pavageau · Answer 1 · 2012-10-17T17:19:22.807

19

You can remove by filtering, which doesn't create an intermediate ArrayList or builder, and only traverses the list once:

public void removeFoo(final String foo) {
    foos = ImmutableList.copyOf(Collections2.filter(foos,
            Predicates.not(Predicates.equalTo(foo)));
}

For adding, I don't see a better solution.

edited Oct 17 '12 at 17:19

answered Oct 17 '12 at 17:13

Frank Pavageau

11,477
1
43
53

I have thought of this, of course (sorry for not mentioning). The problem is: it removes every occurrence, whereas List.remove() only removes the first occurrence, and I was looking for that functionality. Still: +1 – Sean Patrick Floyd Oct 18 '12 at 07:30
Then I guess either of your current implementations is about as good as it gets (you can remove `if (index > 0)` and `if (index < size - 1)` since you'll get an empty sublist). Depending on the typical size of your list and whether you actually remove something, the second one might generate less garbage since the `ArrayList` will be correctly sized, whereas the one (or equivalent) in the builder is not. But is it actually a hotspot so it matters? You can also combine the two and create a correctly-sized `ArrayList` instead of a builder, if the garbage really matters. – Frank Pavageau Oct 18 '12 at 08:36

score 7 · Accepted Answer · edited May 23 '17 at 12:02

The ConcurrentModificationException isn't really related to concurrency and synchronization. Accessing a mutable List concurrently might corrupt it and/or throw the exception (be prepared to all 3 possibilities). You code can't fail this way, but with multithreading it doesn't work either:

Without synchronization and without foos being volatile, there's no guarantee that another thread will ever see the changes you've made.
Even with volatile, it can happen that some changes get lost, e.g., when two threads add an item to foos, both of them can start with the original value and then the one writing last wins (and only its item gets added).

The code you're trying to avoid is nothing to be avoided.

"I have to create superfluous intermediate collections" - yes, but there's no free lunch:
- determine the size of the result in advance, which means an additional iteration through the whole list
- or allocate a large enough array and copy the needed range in the resulting list
- or allocate a large enough array and use only part of it (saving time and wasting memory)
- or create an immutable view (saving both time and memory, but possibly losing time later)
AFAIK Frank's answer implements the first possibility, which is fine if the predicate is fast.
"I have to mix java.util Collections with guava ImmutableCollections, while I'd like to stick to one paradigm." - yes, but for mutating a collection a mutable collection is needed. The ImmutableList.Builder covers just the most common cases allowing to handle them in a compact way.

You might want to have a look at persistent collections, which are optimized for such operations. However, you shouldn't expect e.g. the persistent list to be as fast as an ArrayList or ImmutableList.

OK, I haven't added synchronization to the above example because it was already complicated enough, but it would be a lot easier to add synchronization than when using e.g. ArrayList. Still: +1 for the persistent collections suggestion. Perhaps Guava is not the right place to look for such functionality. — Sean Patrick Floyd, Oct 18 '12 at 07:36
@SeanPatrickFloyd: The Guava team refuses to duplicate existing things and they say that persistent collection [don't really fit in](https://groups.google.com/d/msg/guava-discuss/G4E_Hg9GGv0/YFfQf3-AD3IJ). — maaartinus, Oct 18 '12 at 11:07
@maaartinus I have one [question](http://stackoverflow.com/questions/41925494/how-to-keep-retrying-block-machine-every-x-interval-until-url-is-executed-succes) in which I am using guava retry and wanted to check with you if my code is thread safe and what I am doing is right way? Haven't got any answer so thought to check with you. — john, Feb 04 '17 at 18:37
There is the alternative of making a `ImmutableListWith implements ImmutableList`, which is constructed from an Immutable list, an index, and a value, and is a thin wrapper around the first immutable list. And a separate wrapper for `ImmutableListWithout`. But that's _far_ more complex and probably more allocations than just doing the obvious copies. — Mooing Duck, Apr 23 '20 at 19:50

Adding and removing items to a Guava ImmutableList

2 Answers2