making a list that maintains a reverse order by its own

Question

I've been tasked with the following question: create a collection ReverseList that would implement List. by iterating over an object list of type ReverseList with a for loop (for(E e:list)) we would get the items in an order reversed of what they were entered. implement the following class while extending from ArrayList

so essentially I need to create a collection that doesnt follow the natural ordering of insertion let me clarify that i am not looking to reverse the list after its creation and adding items with something like Collections.reverse() but rather have the list maintain its own order

what I've tried so far is making a custom Iterator. however for some reason when trying to iterate over the list im getting thrown out with an IndexOutOfBoundsException (even though the list isnt empty) my code:

public class ReverseList<E> extends ArrayList<E> implements List<E>{    
private class ReverseIterator<E> extends ReverseList<E> implements Iterator<E> 
{
    private int pos;
    public ReverseIterator()
    {
        pos = super.size()-1;
    }
    public ReverseIterator(ReverseList<E> r)
    {
        pos = r.size()-1;
    }
    
    @Override
    public boolean hasNext() {          
        return pos >= 0;
    }

    @Override
    public E next() {
        return super.get(pos--);
    }
    
}
@Override
public Iterator<E> iterator() {
    // TODO Auto-generated method stub
    return new ReverseIterator<E>(this);
}

public static void main(String[] args)
{
    ReverseList<Integer> r = new ReverseList<>();
    r.add(new Integer(1));
    r.add(new Integer(2));
    r.add(new Integer(3));
    r.add(new Integer(4));
    
    for(Integer i:r)
    {
        System.out.println(i);
    }
}
}

error thrown: Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 0 ( thrown at the for loop )

why is the list at length 0?

is my approach even possible? is there a better way to do it?

Answer 1

Your ReverseIterator is a subclass of ReverseList. This means, it is a list on its own. Then, you are mixing up the state of these two lists. In the ReverseIterator(ReverseList<E> r), you use r’s size to initialize pos, in next() you use super.get(pos--), accessing the other list’s content. This other list is always empty.

An iterator should never be a collection. When you implement an iterator as an inner class, you can access the outer collection’s state implicitly.

Besides that, your list clearly violates the contract of the List interface and will cause a lot of other problems in the future, as its iterator() is inconsistent with other List features, like all index based operations or listIterator().

You should not change the fundamentals of a class, just for the sake of a single operation (i.e. iterate backwards). Rather, implement this single operation as a distinct operation.

For example:

public class ReversibleList<T> extends ArrayList<T> {
    private class ReverseIterator implements Iterator<T> {
        private int pos = size() - 1;
  
        @Override
        public boolean hasNext() {          
            return pos >= 0;
        }
  
        @Override
        public T next() {
            return get(pos--);
        }      
    }
  
    public Iterable<T> reverse() {
        return () -> new ReverseIterator();
    }
  
    public static void main(String[] args) {
        ReversibleList<Integer> r = new ReversibleList<>();
        r.add(1);
        r.add(2);
        r.add(3);
        r.add(4);
  
        for(Integer i: r.reverse()) {
            System.out.println(i);
        }
    }
}

The reverse() view has no storage of its own but always reflects the current contents of the list, in reverse order. The original List keeps fulfilling its contract.

Note that it is possible to create reversed view to a list supporting other operations of the List interface beyond iterator():

public class ReversibleList<T> extends ArrayList<T> {
    private class ReversedList extends AbstractList<T> implements RandomAccess {
      @Override
      public T get(int index) {
        return ReversibleList.this.get(size() - index - 1);
      }

      @Override
      public int size() {
        return ReversibleList.this.size();
      }
    }

    public List<T> reverse() {
        return new ReversedList();
    }

    public static void main(String[] args) {
        ReversibleList<Integer> r = new ReversibleList<>();
        r.add(1);
        r.add(2);
        r.add(3);
        r.add(4);

        r.reverse().subList(1, 4).stream().forEach(System.out::println);
    }
}