List view of concatenated lists

Question

I want to create a list view that consists of the concatenation of a number of other lists.

Example:

List<Integer> l1 = Lists.newArrayList(1);
List<Integer> l2 = Lists.newArrayList(2);
List<Integer> l3 = Lists.newArrayList(3);

// This call should not copy any of the argument lists content
List<Integer> concatenation = new ConcatenationListView(l1, l2, l3);

System.out.println(concatenation); // Prints [1, 2, 3]
l3.add(4);
System.out.println(concatenation); // Prints [1, 2, 3, 4]

What kind of technique and or pattern can I use in Java to fulfill these requirements?

Details

• I want the concatenation to be lazy. (That's the meaning of "view" in this context.)
• I want change to the component lists the reflect on the concatenation. (Also the meaning of "view").
• The view need not to be modifiable.
• This is kind of the opposite of the List.subList method.
• It is similar to what the Guava Iterables.concat method do, but I need a list as the result, not an iterable.
• My question is similar to this one, but I need a List as the resulting concatenation, where the poster of the other question is content with an Iterable as the result.

Answer 1

The following is an implementation of a class that acts as a view of the concatenation of a number of lists.

It didn't take many lines to do it:

/**
 * A list which acts as view of the concatenation of a number of lists.
 */
public class ListConcatenationView<E> extends AbstractList<E> {
    private final List<E>[] lists;
    
    @SafeVarargs
    public ListConcatenationView(List<E>... lists) {
        this.lists = lists;
    }
    
    @Override
    public E get(int ix) {
        if (ix < 0) throw new IndexOutOfBoundsException("Index negative: " + ix); 
        int localIx = ix;
        for (List<E> l : lists) {
            if (localIx < l.size()) return l.get(localIx);
            localIx -= l.size();
        }

        throw new IndexOutOfBoundsException("Index too large: " + ix);
    }

    @Override
    public int size() {
        int size = 0;
        for (List<E> l : lists) {
            size += l.size();
        }
        return size;
    }
}

Answer 2

Java class library does not have a composition class like that, so you would need to code it yourself.

Since you want the class to allow modifications to underlying lists, you wouldn't get better efficiency than O(L), where L is the number of lists managed by the view, because index translation would require you to walk the list of lists each time you need to read or insert at a specific index.

On the other hand, this makes implementation very straightforward - the code that translates the index would look as follows:

class ListView : List<T> {
    private List<List<T>> lists = ...
    public T get(int index) {
        int i = 0;
        while (i != lists.size() && index > lists.get(i).size()) {
            index -= lists.get(i++).size();
        }
        if (i == lists.size()) {
            throw new IndexOutOfBoundsException();
        }
        return lists.get(i).get(index);
    }
    ...
}

Answer 3

You could use the Java8 Stream-API for this one.

Stream.of(l1, l2, l3)
    .flatMap(List::stream)
    .forEach(System.out::println);

This creates a Stream of the three lists, then concatenates all items from each list together by converting every list into a stream itself (List::stream) and flatMap-ing them together. After all it outputs every single element on the console.

Plus: Streams are lazy by default, meaning that

computation on the source data is only performed when the terminal operation is initiated, and source elements are consumed only as needed.

Source