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

If your List is a random access list, you may simply use

int num=list.size()-1;
IntStream.rangeClosed(0, num).mapToObj(i->list.get(num-i))

to create a Stream which has the characteristics ORDERED | SIZED | SUBSIZED and offers full splitting support.

For a non-random access list like LinkedList it would be a performance disaster, however, who uses LinkedList anyway?

You may also check via list instanceofRandomAccess first…

Answer 2

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.

Answer 3

Google's Guava library provides a reverse view of a list (Lists#reverse(List)). There's a ReverseListIterator in the Apache Commons Collection library, too.

Answer 4

I found this solution quite recently.

public <T> Stream<T> toReverseStream(List<T> list) {
    ListIterator<T> listIterator = list.listIterator(list.size());
    return Stream.generate(listIterator::previous)
            .limit(list.size());
}

Answer 5

I tend to like @teppic's answer of using a third-party library to do this. However, it's an interesting exercise to try to come up with a solution using only the Java 8 APIs. Delegating to a ListIterator is the cleanest thing I could come up with, but it's not really much cleaner than implementing your own Iterator from scratch.

public static void main(String[] args){
    List<String> l = Arrays.asList("first", "second", "third");

    StreamSupport.stream(Spliterators.spliterator(revit(l), l.size(), 0), false)
                 .forEachOrdered(System.out::println);
}

private static final <T> Iterator<T> revit(List<T> l){
    ListIterator<T> li = l.listIterator(l.size());

    return new Iterator<T>(){
        @Override
        public boolean hasNext(){
            return li.hasPrevious();
        }

        @Override
        public T next(){
            return li.previous();
        }
    };
}

Answer 6

Starting with the upcoming Java 21, the reversed() method can be used to return a reversed view on the list, which can then be streamed over:

Stream<Object> reversedStream = list.reversed().stream();

As requested, this doesn't buffer or copy the data, as this is merely a reversed view of the original list.