How to get a reversed list view on a list in Java?

Question

I want to have a reversed list view on a list (in a similar way than List#sublist provides a sublist view on a list). Is there some function which provides this functionality?

I don't want to make any sort of copy of the list nor modify the list.

It would be enough if I could get at least a reverse iterator on a list in this case though.

---

Also, I know how to implement this myself. I'm just asking if Java already provides something like this.

Demo implementation:

static <T> Iterable<T> iterableReverseList(final List<T> l) {
    return new Iterable<T>() {
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                ListIterator<T> listIter = l.listIterator(l.size());                    
                public boolean hasNext() { return listIter.hasPrevious(); }
                public T next() { return listIter.previous(); }
                public void remove() { listIter.remove(); }                 
            };
        }
    };
}

---

I just have found out that some List implementations have descendingIterator() which is what I need. Though there is no general such implementation for List. Which is kind of strange because the implementation I have seen in LinkedList is general enough to work with any List.

Solution 1

Guava provides this: Lists.reverse(List)

List<String> letters = ImmutableList.of("a", "b", "c");
List<String> reverseView = Lists.reverse(letters); 
System.out.println(reverseView); // [c, b, a]

Unlike Collections.reverse, this is purely a view... it doesn't alter the ordering of elements in the original list. Additionally, with an original list that is modifiable, changes to both the original list and the view are reflected in the other.

Solution 2

Use the .clone() method on your List. It will return a shallow copy, meaning that it will contain pointers to the same objects, so you won't have to copy the list. Then just use Collections.

Ergo,

Collections.reverse(list.clone());

If you are using a List and don't have access to clone() you can use subList():

List<?> shallowCopy = list.subList(0, list.size());
Collections.reverse(shallowCopy);

Solution 3

If i have understood correct then it is one line of code .It worked for me .

 Collections.reverse(yourList);

Solution 4

Its not exactly elegant, but if you use List.listIterator(int index) you can get a bi-directional ListIterator to the end of the list:

//Assume List<String> foo;
ListIterator li = foo.listIterator(foo.size());

while (li.hasPrevious()) {
   String curr = li.previous();
}

Solution 5

I use this:

public class ReversedView<E> extends AbstractList<E>{

    public static <E> List<E> of(List<E> list) {
        return new ReversedView<>(list);
    }

    private final List<E> backingList;

    private ReversedView(List<E> backingList){
        this.backingList = backingList;
    }

    @Override
    public E get(int i) {
        return backingList.get(backingList.size()-i-1);
    }

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

}

like this:

ReversedView.of(backingList) // is a fully-fledged generic (but read-only) list

View more solutions

Comments

[Tony Ennis]

Can you build the list in the reverse order to begin with?

[TofuBeer]

Yes it does - java.uitl.List.listIterator(int) download.oracle.com/javase/6/docs/api/java/util/…

[ZhaoGang]

If you visit this link to find the answer how to reverse(modify) the list, this is the answer: Collections.reverse(list)

[Albert]

clone() normally would create a copy of the list. Anyway, List#clone() also does not exist.

[jcalvert]

You are technically right, the List interface itself doesn't provide the clone() method. But ArrayList, LinkedList and Vector all do.

[jcalvert]

Clone is a shallow copy of the list. It will not copy the members. But I think I understand where you're going with this now, in reference to a "view", as any structural change to the 'view' from subList() alters the original as well. I don't think you have any way to do what you want without creating a class as you did in your demo.

[Albert]

I just looked up the implementation of clone(). It indeed does a full copy of the list (it only does not clone each single object in the list but that was never what I was talking about).

[Dmitry Zaytsev]

Your code have a one problem - you can put any List to it, but it'll always return you ArrayList (as List). And what if I need LinkedList? It's better to modify myList, and return void.

[Albert]

Note that this is not really what I was asking for. I was asking for some sort of proxy/view, not a copy.

[Albert]

That is not a list view. A view is the opposite of a copy.

[Albert]

That is not a list view. That modifies the list.

[user12722]

Note that Collections.reverse returns void, so you would lose the clone reference. You need to assign the clone to a variable first, then sort it.

[Filipe Brito]

The problem is that Guava is a very large library. See the discussion: github.com/google/guava/issues/1954 and code.google.com/p/guava-libraries/issues/detail?id=605

[ColinD]

@Filipe de Lima Brito: ProGuard is still the best solution for library size, though there are likely improvements we can make. In any case, I don't think library size is relevant in any way to this answer.

[Filipe Brito]

Yes, the library size isn’t relevant to this answer, but is relevant to be informed for the programmers (therefore, I commented)! Thank you very much for this great library and for your suggestion @ColinD!

[AaA]

@ColinD, yup, it was my mistake. A colleague added google-collections which also have same namespace and class (List) but without reverse method. removing it made guava available again.

[ShellFish]

The reverse list of an empty list is null??

[djangofan]

If you didn't want to use built-in descndingIterator() method, it seems like using a ConcurrentLinkedDeque would be the best to reverse a very large list? Basically just copy from one deck to the new deck using poll then offer ? Sorta like just having a deck of cards and taking each off the top into a new pile, in order.

[Roland]

subList doesn't copy, it just provides a view on the underlying list, therefore reversing this view will reverse the underlying list.

[Jonathan Benn]

This is the best answer, since (1) it does not require a library, and (2) it does not modify the original list, as the OP requested

[Jonathan Benn]

You're just repeating the answer someone else wrote 6 years ago

[Jonathan Benn]

Developers don't always have control over what libraries they can use, and adding a whole new library for something so simple seems like overkill--especially given that the problem can be solved with ListIterator.previous()

[Jason S]

...and not a view. this mutates the list.

[Olivier Grégoire]

@JonathanBenn the problem is that the problem is not so simple. You have so many implementations of List that reversing it appropriately entirely depends on the context (do you use a List for its index, do you use it for the ordered property, etc.) This answer is the best at mixing all those.

[Brain]

Agree, the response of jcalvert is way better, because it uses the standard library. Guava just cause problems with other frameworks. You can say "it pollutes" your code.

[Florent]

ArrayList.clone returns Object which is not accepted by Collections.reverse()