Java: Iterate over a list in the reverse order example
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 tutorial considers the following software and environment:
- Ubuntu 12.04
- 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:
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:
package com.byteslounge.collections;
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:
package com.byteslounge.collections;
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());
}
}
}
The output generated by this test class will be the following:
Second
First
Third
Second
First
The example source code is available at the end of this page.