descendingIterator for java.util.List

Question

LinkedList can be iterated using ascending or descending iterator like this:

LinkedList<Object> list = new LinkedList<Object>();
   ...
StringJoiner sJ1 = new StringJoiner(" ");
list.iterator().forEachRemaining(a -> sJ1.add(a.toString()));
System.out.println("averse: \n" + sJ1.toString());

StringJoiner sJ2 = new StringJoiner(" ");
list.descendingIterator().forEachRemaining(a -> sJ2.add(a.toString()));
System.out.println("reverse: \n" + sJ2.toString());

averse: 
Hello 2 Chocolate 10
reverse: 
10 Chocolate 2 Hello

But descendingIterator isn't available for List and ArrayList. Are there any workaround or at list explanation, why descendingIterator is absent in List?

Question is similar to Can one do a for each loop in java in reverse order?. But all the answers recommend ad hoc solutions or 3rd party libraries.

May be there is this is possible using streams streams? (Unfortunately my googling gives only absence standard reverse for stream Java 8 stream reverse order)

As I've mentioned my questions is related to that about streams, but:

Using of stream is only an option, question is about java.util.Iterator and java.util.List
Answers to that question solved only partial case, but showed absence of convenient general reverse. If I'm not missing the term List is ordered collection, sorting of Comparable items, to achieve order decreases the scope.

Possible duplicate of [Java 8 stream reverse order](http://stackoverflow.com/questions/24010109/java-8-stream-reverse-order) — Andremoniy, Feb 14 '17 at 21:54
Maybe you just want to use an `ArrayDeque` instead of `ArrayList`? — Holger, Feb 15 '17 at 15:32
@Holger ArrayDeque really solved my problem. But the need of such a solution looks awkward to me. Because ArrayDeque seems rarer and less well-known tool than descending for loop and it doesn't implement List. — user9999, Aug 22 '20 at 11:31

score 7 · Answer 1 · edited Apr 08 '20 at 15:22

There's no really good reason why List couldn't have a descending iterator. Every List is required to support a ListIterator which can be iterated in reverse order using the hasPrevious() and previous() methods. This seems to be a fairly uncommon use case, though.

Here's a little utility method that adapts an Iterable to a ListIterator iterating in reverse order:

static <T> Iterable<T> descendingIterable(List<? extends T> list) {
    return () -> {
        ListIterator<? extends T> li = list.listIterator(list.size());
        return new Iterator<T>() {
            public boolean hasNext() { return li.hasPrevious(); }
            public T next() { return li.previous(); }
        };
    };
}

You could use it to implement your example:

List<String> list = Arrays.asList("Hello", "2", "Chocolate", "10");
StringJoiner sj = new StringJoiner(" ");
descendingIterable(list).iterator().forEachRemaining(sj::add);
System.out.println(sj);

10 Chocolate 2 Hello

Or you could use it in an enhanced-for loop:

for (String s : descendingIterable(list)) {
    System.out.println(s);
}

10
Chocolate
2
Hello

I initially had this create an Iterator instead of an Iterable, but the latter is more useful since it can be used in an enhanced-for loop.

Note also there is a small wrinkle here which is that there is a race condition if the List can be concurrently modified. This occurs at the code here:

list.listIterator(list.size())

If this is a possibility, you either have to use external synchronization on the list, or if the list is a CopyOnWriteArrayList, you have to clone it first. See this answer for further information on the latter.

Magnus · Answer 2 · 2017-02-14T23:27:38.273

is there an explanation as to why descendingIterator is absent in List?

The efficiency of iterating a List is highly dependant on the implementation of that list.
When designing an interface you generally want the interface to be appropriate for any conceivable implementations of it.

A Java linked list is a doubly linked list, meaning that each element is linked to the element preceding and succeeding it, as such it is possible to write efficient ascending and descending iterators.

If you used a singly linked list, it would be horribly inefficient to descending iterate it, you would need to traverse the entire list up until the current index for every iteration.

I suspect it is for this reason that the language designers decided to omit a descending iterator from the List interface.

An efficient ArrayList descending iterator can be implemented fairly easily with an index based approach, using an index approach on a LinkedList would be much slower than its preferred implementation.

Some examples of descending iteration approaches:

for(int i=list.size() -1; i >= 0; i--){
    System.out.println(list.get(i));
}

IntStream.range(0, list.size())
        .map(i-> list.size() - 1 - i)
        .mapToObj(list::get)
        .forEach(System.out::println);

descendingIterator for java.util.List

2 Answers2

Linked