How to efficiently merge two lists in Java?

Question

There are several ways to merge lists in Java

• You can call to ArrayList(Collection<? extends E> c)
• You can use the stream API, like Stream.concat() or Stream.of(listA, listB).forEach()
• and more...

What would be the most memory and performance efficient way to merge two random access lists into a new random access list?

Answer 1

Try this to create an immutable list containing all the elements, by performing a shallow copy. Beware that changes to the source lists will be reflected in the resulting list (so the immutability in reality depends on the immutability / access to the input lists).

public class MergedList<T> extends AbstractList<T> {

    private final List<T>[] lists;
    private final int size;

    @SafeVarargs
    MergedList(List<T>... lists) {
        this.lists = lists.clone();
        this.size = Arrays.stream(lists).mapToInt(list -> list.size()).sum();
    }

    @Override
    public T get(int index) {
        for (List<T> list : lists)
            if (index < list.size())
                return list.get(index);
            else
                index -= list.size();
        throw new IndexOutOfBoundsException("index");
    }

    @Override
    public int size() {
        return size;
    }

}

and

List<Integer> a = List.of(1, 2, 3, 4);
List<Integer> b = List.of(5, 6, 7);
List<Integer> c = new MergedList<>(a, b);
System.out.println(c);

output

[1, 2, 3, 4, 5, 6, 7]

Considering that the original list is updated, it might be better to remove the field size and do this:

    @Override
    public int size() {
        return Arrays.stream(lists).mapToInt(list -> list.size()).sum();
    }

Answer 2

You have not defined what "merge" means in your context. This answer assumes it means "combine into one list".

To reduce the amount of memory and processing used, create a List whose size is exactly right, then add each list in turn to it.

List<E> result = new ArrayList<>(list1.size() + list2.size());
result.addAll(list1);
result.addAll(list2);

This eliminates possible redundant memory allocation and object creation that may occur during list1.addAll(list2).

Answer 3

you can use Apache commons library-

ListUtils.union(listA, listB);

Using parallel Java8 Streams could be is better instead of just streams for large datasets.

Stream.concat(list1.parallelStream(), list1.parallelStream())
      .collect(Collectors.toList());