[java] Iterating through a list in reverse order in java

I'm migrating a piece of code to make use of generics. One argument for doing so is that the for loop is much cleaner than keeping track of indexes, or using an explicit iterator.

In about half the cases, the list (an ArrayList) is being iterated in reverse order by using an index today.

Can someone suggest a cleaner way of doing this (since I dislike the indexed for loop when working with collections), though it does work?

 for (int i = nodes.size() - 1; i >= 0; i--) {
    final Node each = (Node) nodes.get(i);
    ...
 }

Note: I can't add any new dependencies outside the JDK.

This is an old question, but it's lacking a java8-friendly answer. Here are some ways of reverse-iterating the list, with the help of the Streaming API:

List<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 3, 3, 7, 5));
list.stream().forEach(System.out::println); // 1 3 3 7 5

int size = list.size();

ListIterator<Integer> it = list.listIterator(size);
Stream.generate(it::previous).limit(size)
    .forEach(System.out::println); // 5 7 3 3 1

ListIterator<Integer> it2 = list.listIterator(size);
Stream.iterate(it2.previous(), i -> it2.previous()).limit(size)
    .forEach(System.out::println); // 5 7 3 3 1

// If list is RandomAccess (i.e. an ArrayList)
IntStream.range(0, size).map(i -> size - i - 1).map(list::get)
    .forEach(System.out::println); // 5 7 3 3 1

// If list is RandomAccess (i.e. an ArrayList), less efficient due to sorting
IntStream.range(0, size).boxed().sorted(Comparator.reverseOrder())
    .map(list::get).forEach(System.out::println); // 5 7 3 3 1

I don't think it's possible using the for loop syntax. The only thing I can suggest is to do something like:

Collections.reverse(list);
for (Object o : list) {
  ...
}

... but I wouldn't say this is "cleaner" given that it's going to be less efficient.

Guava offers Lists#reverse(List) and ImmutableList#reverse(). As in most cases for Guava, the former delegates to the latter if the argument is an ImmutableList, so you can use the former in all cases. These do not create new copies of the list but just "reversed views" of it.

Example

List reversed = ImmutableList.copyOf(myList).reverse();

Here is an (untested) implementation of a ReverseIterable. When iterator() is called it creates and returns a private ReverseIterator implementation, which simply maps calls to hasNext() to hasPrevious() and calls to next() are mapped to previous(). It means you could iterate over an ArrayList in reverse as follows:

ArrayList<String> l = ...
for (String s : new ReverseIterable(l)) {
  System.err.println(s);
}

Class Definition

public class ReverseIterable<T> implements Iterable<T> {
  private static class ReverseIterator<T> implements Iterator {
    private final ListIterator<T> it;

    public boolean hasNext() {
      return it.hasPrevious();
    }

    public T next() {
      return it.previous();
    }

    public void remove() {
      it.remove();
    }
  }

  private final ArrayList<T> l;

  public ReverseIterable(ArrayList<T> l) {
    this.l = l;
  }

  public Iterator<T> iterator() {
    return new ReverseIterator(l.listIterator(l.size()));
  }
}

To have code which looks like this:

List<Item> items;
...
for (Item item : In.reverse(items))
{
    ...
}

Put this code into a file called "In.java":

import java.util.*;

public enum In {;
    public static final <T> Iterable<T> reverse(final List<T> list) {
        return new ListReverseIterable<T>(list);
    }

    class ListReverseIterable<T> implements Iterable<T> {
        private final List<T> mList;

        public ListReverseIterable(final List<T> list) {
            mList = list;
        }

        public Iterator<T> iterator() {
            return new Iterator<T>() {
                final ListIterator<T> it = mList.listIterator(mList.size());

                public boolean hasNext() {
                    return it.hasPrevious();
                }
                public T next() {
                    return it.previous();
                }
                public void remove() {
                    it.remove();
                }
            };
        }
    }
}

You could use ReverseListIterator from Apache Commons-Collections:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/iterators/ReverseListIterator.html

Create a custom reverseIterable.

Very simple Example:

List<String> list = new ArrayList<String>();

list.add("ravi");

list.add("kant");

list.add("soni");

// Iterate to disply : result will be as ---     ravi kant soni

for (String name : list) {
  ...
}

//Now call this method

Collections.reverse(list);

// iterate and print index wise : result will be as ---     soni kant ravi

for (String name : list) {
  ...
}

Reason : "Don't know why there is no descendingIterator with ArrayList..."

Since array list doesnot keep the list in the same order as data has been added to list. So, never use Arraylist .

Linked list will keep the data in same order of ADD to list.

So , above in my example, i used ArrayList() in order to make user to twist their mind and make them to workout something from their side.

Instead of this

List<String> list = new ArrayList<String>();

USE:

List<String> list = new LinkedList<String>();

list.add("ravi");

list.add("kant");

list.add("soni");

// Iterate to disply : result will be as ---     ravi kant soni

for (String name : list) {
  ...
}

//Now call this method

Collections.reverse(list);

// iterate and print index wise : result will be as ---     soni kant ravi

for (String name : list) {
  ...
}

If the lists are fairly small so that performance is not a real issue, one can use the reverse-metod of the Lists-class in Google Guava. Yields pretty for-each-code, and the original list stays the same. Also, the reversed list is backed by the original list, so any change to the original list will be reflected in the reversed one.

import com.google.common.collect.Lists;

[...]

final List<String> myList = Lists.newArrayList("one", "two", "three");
final List<String> myReverseList = Lists.reverse(myList);

System.out.println(myList);
System.out.println(myReverseList);

myList.add("four");

System.out.println(myList);
System.out.println(myReverseList);

Yields the following result:

[one, two, three]
[three, two, one]
[one, two, three, four]
[four, three, two, one]

Which means that reverse iteration of myList can be written as:

for (final String someString : Lists.reverse(myList)) {
    //do something
}

Option 1: Have you thought about reversing the List with Collections#reverse() and then using foreach?

Of course, you may also want to refactor your code such that the list is ordered correctly so you don't have to reverse it, which uses extra space/time.

EDIT:

Option 2: Alternatively, could you use a Deque instead of an ArrayList? It will allow you to iterate forwards and backwards

EDIT:

Option 3: As others have suggested, you could write an Iterator that will go through the list in reverse, here is an example:

import java.util.Iterator;
import java.util.List;

public class ReverseIterator<T> implements Iterator<T>, Iterable<T> {

    private final List<T> list;
    private int position;

    public ReverseIterator(List<T> list) {
        this.list = list;
        this.position = list.size() - 1;
    }

    @Override
    public Iterator<T> iterator() {
        return this;
    }

    @Override
    public boolean hasNext() {
        return position >= 0;
    }

    @Override
    public T next() {
        return list.get(position--);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}


List<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");

for (String s : new ReverseIterator<String>(list)) {
    System.out.println(s);
}

Also found google collections reverse method.

As has been suggested at least twice, you can use descendingIterator with a Deque, in particular with a LinkedList. If you want to use the for-each loop (i.e., have an Iterable), you can construct and use a wraper like this:

import java.util.*;

public class Main {

    public static class ReverseIterating<T> implements Iterable<T> {
        private final LinkedList<T> list;

        public ReverseIterating(LinkedList<T> list) {
            this.list = list;
        }

        @Override
        public Iterator<T> iterator() {
            return list.descendingIterator();
        }
    }

    public static void main(String... args) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");

        for (String s : new ReverseIterating<String>(list)) {
            System.out.println(s);
        }
    }
}

You could use the concrete class LinkedList instead of the general interface List. Then you have a descendingIterator for iterating with the reverse direction.

LinkedList<String > linkedList;
for( Iterator<String > it = linkedList.descendingIterator(); it.hasNext(); ) {
    String text = it.next();
}

Don't know why there is no descendingIterator with ArrayList...