273

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.

14
  • 12
    What's so bad about using an explicit index to iterate over a indexed data structure? At least it shows you what's exactly going on. For iterating backwards I always the following slightly shorter idiom: for (int i = nodes.size(); --i >= 0;)
    – x4u
    Jan 20, 2010 at 16:00
  • 5
    Nothing particularly, I'd just rather program to an interface and not know about what kind of list I'm using. Though I like your short hand greatly. (+1 comment) Jan 20, 2010 at 16:04
  • 1
    @x4u: There's not much in it although Iterator is fail-fast and also allows elements to be easily removed during the iteration.
    – Adamski
    Jan 20, 2010 at 16:37
  • 2
    This class is broken, because the user might want to iterate a second time over the same Iterable, or the list might change between when the iterable is constructed and when it's iterated. I'm sure for your purposes you'll just make sure not to do that, but it wouldn't be too hard to fix the code; or just steal the code from Guava (Apache 2.0 license): code.google.com/p/guava-libraries/source/browse/trunk/src/com/… Jan 20, 2010 at 21:36
  • 1
    Fair enough, but even the Guava one is susceptible to the same thing if I'm reading it right. Were a user to keep a copy of the result from reverse, it'd have the same problem. Jan 21, 2010 at 18:15

18 Answers 18

472

Try this:

// Substitute appropriate type.
ArrayList<...> a = new ArrayList<...>();

// Add elements to list.

// Generate an iterator. Start just after the last element.
ListIterator li = a.listIterator(a.size());

// Iterate in reverse.
while(li.hasPrevious()) {
  System.out.println(li.previous());
}
11
  • 4
    Not bad. Doesn't use the index, but loses the elegance of the for each syntax. +1 anyway. Jan 20, 2010 at 15:35
  • 30
    Calling listIterator() without an index argument will give an Iterator at the beginning of the list and so hasPrevious() will return false on the first call.
    – Adamski
    Jan 20, 2010 at 15:35
  • 2
    You want an index on the listIterator call, I think. Jan 20, 2010 at 15:36
  • 1
    You can write an Iterator that uses a ListIterator in reverse, but that may not be worth it for one loop. Jan 20, 2010 at 15:37
  • 1
    It's not one loop, so I've taken this and wrapped it. pastebin.ca/1759041 so, now I can do for (Node each : new ListReverse<Node>(nodes)) { } Jan 20, 2010 at 15:52
39

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();
26

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.

2
  • 33
    and it also changes in place the list you traverse, which is quite a huge side-effect. (Say you wrap this in a method, each time it is called you traverse the list the other way ^^)
    – jolivier
    Feb 14, 2014 at 19:04
  • 1
    This is the cleanest solution.
    – jfajunior
    Mar 11, 2020 at 16:00
16

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);
}
4
  • 1
    Have thought about it, but there cost of reversing it is prohibitive. Also, it only requires this kind of iteration about half the time. Flipping it would just move the problem to the other half. Jan 20, 2010 at 15:34
  • 3
    + for Deque; typical implementations have descendingIterator().
    – trashgod
    Jan 20, 2010 at 19:01
  • This would perform terrible for linked lists, the OP's variant is better.
    – masterxilo
    May 26, 2014 at 20:06
  • 1
    Using a for each expression is the most idiomatic solution in my opinion. It's nice to realize that this is possible if your List implements Iterable in a way that iterates backwards. I'm going to use this approach and use the ReverseListIterator class from Apache Commons Collections. Jul 21, 2014 at 3:23
12

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...

11

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
1
  • 2
    very nice, just a cosmetic change: int size = list.size(); ListIterator<Integer> it = list.listIterator(size); Stream.generate(it::previous).limit(size).forEach(System.out::println);
    – benez
    Jan 31, 2016 at 22:58
5

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()));
  }
}
2
  • Looks right to me, though exposing it as a static method instead of a public constructor would (in most cases) avoid the need for the client to specify the type parameter. This is how Guava does it.. Jan 20, 2010 at 21:38
  • 2
    This is the best implementation, however ReverseIterator is missing the necessary constructor and the code should use List instead of ArrayList.
    – Andy
    Feb 26, 2014 at 1:28
4

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
}
4

Java 21 added a reversed() method to List, which returns a reversed view of the list. This can be used to iterate in reverse order.

for (Node each : nodes.reversed()) {
   ...
}
3

You could use ReverseListIterator from Apache Commons-Collections:

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

2
  • 1
    Your link does not exists anymore
    – AaA
    Jun 29, 2016 at 6:37
  • 1
    Thank you @AaA ; it looks like the ReverseListIterator link does work at this point. (Updated Dec 2020) Dec 22, 2020 at 19:29
2

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) {
  ...
}
2

Create a custom reverseIterable.

7
  • 1
    Don't know why this is getting down voted, I might just make a wrapper for the list that does this. Jan 20, 2010 at 15:36
  • This is no less clean than calling Collections.reverse() IMHO.
    – Adamski
    Jan 20, 2010 at 15:40
  • @Allain: Agreed re. the downvotes although I don't see why you view a call to listIterator(list.size()) as "not clean". Even if you wrap it you're still having to make the same method call somewhere.
    – Adamski
    Jan 20, 2010 at 15:41
  • Suppose not, just not willing to take the performance hit, for cleanliness. Jan 20, 2010 at 15:42
  • 20
    Voted down as I don't think consider this a complete answer. Apr 2, 2014 at 17:46
1

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();
                }
            };
        }
    }
}
5
  • 1
    This has been mentioned elsewhere in the thread, but the listIterator field needs to be inside the Iterator implementation, not the Iterable implementation.
    – Andy
    Feb 26, 2014 at 1:32
  • 1
    Why using an enum type, not a class?
    – Aubin
    Aug 8, 2014 at 9:29
  • 1
    It makes the 'In' class non-instantiable, without having to write a private default constructor. Good for classes that only have static methods.
    – intrepidis
    Aug 10, 2014 at 8:37
  • I would say that abusing enums just to avoid writing a private default constructor is confusing at best. How about using enums for enums and classes for classes? By making a class into an enum it also implicitly gets a name() method, an ordinal() method and a static valueOf() method, for example.
    – JHH
    Mar 5, 2018 at 11:14
  • 1
    Yes you can continue with your opinion and that will work fine too, but I think to the contrary. Classes are for instantiating objects and abusing them by including a private default constructor to inhibit their instantiation is confusing at best. In Java, enums actually are classes, but ones that can never be instantiated by design.
    – intrepidis
    Mar 11, 2018 at 8:23
0

Also found google collections reverse method.

1
  • 1
    Which version of google collection? your link does not exists anymore.
    – AaA
    Jun 29, 2016 at 6:35
0

How about using DeQue:

  var queue = new ArrayDeque<>(list);
  while (!queue.isEmpty()) {
    var first = reversed ? queue.removeLast() : queue.removeFirst();
    var second = reversed ? queue.peekLast() : queue.peekFirst();
    if (second != null) {
      //your code goes here
    }
  }
-1

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);
        }
    }
}
-1
Valid for Java 9+

List<String> strList = List.of("a", "b", "c", "d", "e");

IntStream.iterate(strList.size() - 1, i -> i >= 0, i -> --i)
         .mapToObj(strList::get)
         .forEach(System.out::println);
-11

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) {
  ...
}
3
  • 5
    "Since array list doesnot keep the list in the same order as data has been added to list" umm, yes it does, at least it does in the same manner as a linked list does. Can you provide an example of how they don't?
    – corsiKa
    Jan 3, 2013 at 23:07
  • Yes, ArrayList and LinkedList (The List contract in general) keep items in insertion in order. the Set contract is unordered or ordered by sort (TreeSet). The reverse idea isn't bad but remember that it actually reorders the list which could be slowish.
    – Bill K
    Jan 4, 2013 at 1:29
  • 3
    I downvoted this answer because it erroneously states that ArrayLists do not keep items in insertion order. As @bill-k notes, all Lists are ordered collections by definition. The suggestion to use a LinkedList instead has merit, since it features the descendingIterator() method, but only if performance is a bigger concern than memory and abstraction. Mar 19, 2013 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.