5

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?

Elliott Frisch
  • 198,278
  • 20
  • 158
  • 249
Danitechnik
  • 398
  • 1
  • 3
  • 10
  • 1
    Why do you want to add additional elements into an immutable list? Seems like this is the thorny point moreso than copying things around. – Makoto Jul 21 '21 at 21:59
  • 1
    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`. – Danitechnik Jul 21 '21 at 22:11
  • 1
    _"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. – Stephen P Jul 21 '21 at 22:12
  • @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. – Makoto Jul 21 '21 at 22:54
  • @Makoto 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. – Basil Bourque Jul 21 '21 at 23:39

3 Answers3

10

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.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
Elliott Frisch
  • 198,278
  • 20
  • 158
  • 249
  • 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? – M The Developer Oct 31 '22 at 22:12
  • 2
    I think you missed we are adding **one element**. You'd need at least two for potential parallelism. – Elliott Frisch Nov 01 '22 at 01:58
5

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 ) ;
Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
1

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);
Rob Audenaerde
  • 19,195
  • 10
  • 76
  • 121