Get multiple elements from list by indices in constant time

Question

What is the best way to get multiple elements from a list by their indices in constant time?

If I've an array:

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");

And I've an list/array with indices:

List<Integer> indices = new ArrayList<>();
indices.add(0);
indices.add(2);
indices.add(3);

How can I get a,c,d in constant time? I need something like this:

List<String> filtered = list.filterByIndex(indices);
filtered.stream().forEach(x -> System.out.print(x));
// output:"acd"

UPDATE: The printing of the items doesn't have to be in constant time of course, only the collecting of items. The code above of printing the elements is just for demonstrating purposes only.

Answer 1

I suggest:

    List<String> filtered = indices.stream()
            .map(list::get)
            .collect(Collectors.toList());

The result is the desired:

[a, c, d]

Assuming the list has constant-time access (as an ArrayList has), this runs in time that is linear in the number of elements requested (length of indices), but does not increase with the length of the list list. As has been discussed in comments, this is the best we can do.

Edit: Honestly I don’t know whether the collecting step above is in linear time in the number of collected elements. Possibly extensions of list capacity cost time, and probably this doesn’t take more than linear time. If we need to be sure, we need to collect this way instead:

            .collect(Collectors.toCollection(() -> new ArrayList<>(indices.size())));

This makes sure a list with appropriate capacity is allocated from the outset so no extensions will be needed.