Java: Iterate over a list in the reverse order example

In this article you will learn how to iterate over a Java list in the reverse order.

Introduction

A simple approach of iterating a list in the reverse order may consist in simply revert a list using Collections.reverse() and then performing a natural iteration over the elements. Sometimes this approach may not be acceptable. Supposing that our list is holding a considerable number of items that makes the reverse operation itself to impact the overall application performance. It doesn't make sense to spend CPU cycles reversing the list if what we want to do is just to iterate its elements in the reverse order.

This article considers the following software and environment:

JDK 1.7.0.09

The ListIterator interface

The ListIterator interface is a special kind of iterator designed to iterate over lists. It provides functionality that is not available in regular iterators such as iterating a list in either direction. With this in mind we can iterate a list in the reverse order by just using the ListIterator interface:

ListIterator interface

List<String> list = new ArrayList<String>();
list.add("First");
list.add("Second");
list.add("Third");

ListIterator<String> listIterator = list.listIterator(list.size());

while(listIterator.hasPrevious()){
  System.out.println(listIterator.previous());
}

List.listIterator() method returns an iterator that is ready to transverse the list in whatever direction we want. The method may take a parameter that defines the starting index of the iteration. We defined this position to be n because lists are zero-based indexed so the first call to previous() will return the last element in the list. As we can see it's easy to transverse a list in the reverse order, but what about making this reusable?

Making it reusable

Every class that implements the Iterable interface it's declaring itself as iterable so it must provide an Iterator. This way the callers are able to iterate over elements in some data structure provided by the class. With this in mind we can write something like the following:

ReversedIterator class

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

public class ReversedIterator<T> implements Iterable<T> {

  private List<T> list;

  public ReversedIterator(List<T> list){
    this.list = list;
  }

  //Iterator provided to clients of this class
  @Override
  public Iterator<T> iterator() {

    // Every time an iterator is requested we
    // define a new ListIterator that will be used to
    // iterate the list in the reverse order
    final ListIterator<T> iterator = list.listIterator(list.size());

    // The iterator returned to the caller will
    // work based on the ListIterator
    return new Iterator<T>(){

      // hasNext() and next() methods call in fact
      // the reverse operations in ListIterator

      @Override
      public boolean hasNext(){
        return iterator.hasPrevious();
      }

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

      @Override
      public void remove() {
        iterator.remove();
      }

    };

  }
}

Our ReversedIterator class receives the list we want to do reverse iteration in the constructor. The iterator() method builds a new ListIterator when it's called by a client and returns an Iterator that will work based on this ListIterator. When the Iterator methods are called we use the created ListIterator to perform the reverse operations. We made this class generic so it can be used with any data type.

Testing

Let's test it:

Test class

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

public class Main {

  public static void main(String [] args){

    List<String> list = new ArrayList<String>();
    list.add("First");
    list.add("Second");
    list.add("Third");

    ReversedIterator<String> reversedList = 
         new ReversedIterator<String>(list);

    // for-each syntax
    for(String s : reversedList){
      System.out.println(s);
    }

    System.out.println("");

    // iterator syntax
    Iterator<String> iterator = reversedList.iterator();
    while(iterator.hasNext()){
      System.out.println(iterator.next());
    }

  }
}

Output:

Third
Second 
First

Third 
Second 
First