How to get ordered stream from a list in reverse order in Java 8

Question

Is there a sane way to get an ordered stream from a list (array list specifically, but it shouldn't matter) that streams elements in reverse of how they are in the original list?

I'm looking for a solution that doesn't involve buffering data in anything (collector, another list, array, etc, because they copy the container which is wasteful), or uses Collections.reverse (because it modifies the list).

So far, the cleanest ways that I see here is to implement my own version of Spliterator that's ORDERED and advances through the list in reverse, or implement an Iterator that iterates in reverse, and use Spliterators.spliteratorUnknownSize(iterator,ORDERED) on it.

Note this question is different from Java 8 stream reverse order : that other question asks on how to reverse a stream (which is impossible in general case), and answers offer to reverse the source somehow (which I don't want to do), and then stream that reversed source. The cost of reversing the source is O(N), and I want to avoid it at all if possible.

Answer 1

NOTE: If you have an ArrayList or other list that allows random-access retrieval by index (get(i)) then Holger's approach is preferable. The approach below is only necessary if you have a data structure that allows reverse traversal but not indexed access.

---

Unfortunately there doesn't seem to be a really simple (i.e., a one-liner) way to do this. But getting a reversed stream using AbstractSpliterator isn't too difficult, given that List already has the ability to iterate in reverse. Here's a utility method to do that:

static <T> Stream<T> reversedStream(List<? extends T> input) {
    ListIterator<? extends T> li = input.listIterator(input.size());
    return StreamSupport.stream(
        new Spliterators.AbstractSpliterator<T>(input.size(), Spliterator.ORDERED) {
            @Override public boolean tryAdvance(Consumer<? super T> action) {
                if (li.hasPrevious()) {
                    action.accept(li.previous());
                    return true;
                } else {
                    return false;
                }
            }
        },
        false);
}

(I suppose the Spliterator could be SIZED, but that's mostly pointless because this is an unsplittable spliterator.)

As it stands, this can afford a limited degree of parallelism, as AbstractSpliterator will call tryAdvance multiple times and batch up work to hand off to fork-join tasks. But it's not as efficient as being able to split.

If parallel efficiency is a great concern, one could write a spliterator that can actually split, where the splits are traversed in reverse order.