Java - Add one element to an immutable list

Question

I need an immutable list where I can get derive a second immutable list preserving all elements of the previous list plus an additional element in Java (without additional libraries).

Note: This question is similar to What is an efficient and elegant way to add a single element to an immutable set? but I need a list and don't have Guava.

What I have tried so far:

var list = List.of(someArrayOfInitialElements);
var newList = Stream.concat(list.stream(), Stream.of(elementToAppend))
        .collect(CollectorsCollectors.toUnmodifiableList());

That would work but creating a stream and copying elements one by one seems inefficient to me. You could basically bulk copy memory given that List.of() stores data in a field-based or array-based data structure.

Is there a more efficient solution than using streams? A better data structure in the Java standard library that I am missing?

Charters

Why do you want to add additional elements into an immutable list? Seems like this is the thorny point moreso than copying things around. – Dowzall

There are a lot of reasons to make certain objects immutable. If you want to add a single element then you get this issue. .NET even has it's own collections for this purpose in System.Collections.Immutable. – Charters

"given that List.of() stores data in a field-based or array-based data structure." — that is an implementation detail that you can't depend on, not part of the spec. The "Immutable List Static Factory Methods" documentation says "Factories are free to create new instances or reuse existing ones" so it can't even necessarily use contiguous memory. – Amanuensis

@Danitechnik: That's all good and dandy, but if you're adding elements to an immutable collection, then I don't know if what you require is an immutable collection. Adding things to a collection that you can't add to to begin with is awkward without further articulation. – Dowzall

@Dowzall It is entirely reasonable to want to add to an immutable collection. Any collection being returned by service or library should generally be immutable. After obtaining such an immutable collection, the calling method may justifiably want to modify that collection before proceeding. – Levina

Answer 1

I would create a new ArrayList append the element and then return that as an unmodifiable list. Something like,

private static <T> List<T> appendOne(List<T> al, T t) {
    List<T> bl = new ArrayList<>(al);
    bl.add(t);
    return Collections.unmodifiableList(bl);
}

And to test it

public static void main(String[] args) {
    List<String> al = appendOne(new ArrayList<>(), "1");
    List<String> bl = appendOne(al, "2");
    System.out.println(bl); 
}

I get (unsurprisingly):

[1, 2]

See this code run at IdeOne.com.

Aboriginal

I'm not sure I see how this is more efficient than using the Streams api. Streams would potentially use threads and makes use of multithreaded processors if available. Constructing one collection from another uses the iterator and guarantees it maintains the iterator order. Thus, would be synchronous. Could you explain? – Elnaelnar

I think you missed we are adding one element. You'd need at least two for potential parallelism. – Aboriginal

Answer 2

The Answer by Frisch is correct, and should be accepted. One further note…

Calling Collections.unmodifiableList produces a collection that is a view onto the original mutable list. So a modification to the original list will "bleed through" to the not-so-immutable second list.

This issue does not apply to the correct code shown in that Answer, because the new ArrayList object deliberately goes out-of-scope. Therefore that new list cannot be accessed for modification. But in other coding scenarios, this issue could be a concern.

List.copyOf

If you want an independent and truly immutable second list, use List.copyOf in Java 10+. This returns an unmodifiable list.

return List.copyOf( bl ) ;

Levina

Answer 3

Both answers are great, I would create a bit more generic solution:

private static <T> List<T> append(final List<T> al, final T... ts) {
    final List<T> bl = new ArrayList<>(al);
    for (final T t : ts) {
        bl.add(t);
    }
    return List.copyOf(bl);
}

It can be used exactly like previous answer:

    List<String> al = append(new ArrayList<>(), "1");
    List<String> bl = append(al, "2");
    System.out.println(bl); 

But also slightly more efficient:

    List<String> bl = append(new ArrayList<>(), "1", "2");
    System.out.println(bl); 

Goulder

Answer 4

I came across this question while looking for an answer to the same problem, and didn't find anything very good. Here is the best I could come up with:

    // starting out with:
    var list = List.of("item1", "item2", "item3");
    String elementToAppend = "item4";

    // copy once into array exactly sized for the additional element
    int size = list.size();
    String[] array = list.toArray(new String[size + 1]);
    array[size] = elementToAppend;
    // wrap as unmodifiable:
    var newList = Collections.unmodifiableList(Arrays.asList(array));

Arrays.asList is chosen because it reuses the single array that is created for this, although it unfortunately does so as a modifiable list, so an extra wrap with unmodifiable is needed.

I would have used one of the other solutions, but it seems like new ArrayList(list) followed by add could cause a resize.

Aa