Durchlaufen einer Liste in umgekehrter Reihenfolge in Java

251

Ich migriere einen Code, um Generika zu verwenden. Ein Argument dafür ist, dass die for-Schleife viel sauberer ist als das Verfolgen von Indizes oder die Verwendung eines expliziten Iterators.

In etwa der Hälfte der Fälle wird die Liste (eine ArrayList) heute mithilfe eines Index in umgekehrter Reihenfolge iteriert.

Kann jemand einen saubereren Weg vorschlagen, dies zu tun (da ich das indexed for loopbei der Arbeit mit Sammlungen nicht mag), obwohl es funktioniert?

 for (int i = nodes.size() - 1; i >= 0; i--) {
    final Node each = (Node) nodes.get(i);
    ...
 }

Hinweis: Ich kann keine neuen Abhängigkeiten außerhalb des JDK hinzufügen.

Allain Lalonde
quelle
10
Was ist so schlimm daran, einen expliziten Index zu verwenden, um über eine indizierte Datenstruktur zu iterieren? Zumindest zeigt es Ihnen, was genau los ist. Um rückwärts zu iterieren, habe ich immer die folgende etwas kürzere Redewendung:for (int i = nodes.size(); --i >= 0;)
x4u
4
Nichts Besonderes, ich würde lieber auf eine Schnittstelle programmieren und nicht wissen, welche Art von Liste ich verwende. Obwohl ich deine kurze Hand sehr mag. (+1 Kommentar)
Allain Lalonde
1
@ x4u: Es ist nicht viel drin, obwohl Iterator ausfallsicher ist und es auch ermöglicht, Elemente während der Iteration leicht zu entfernen.
Adamski
2
Diese Klasse ist fehlerhaft, da der Benutzer möglicherweise ein zweites Mal über dieselbe Iterable iterieren möchte oder die Liste zwischen der Erstellung der Iterable und der Iteration wechseln kann. Ich bin mir sicher, dass Sie für Ihre Zwecke nur darauf achten werden, dies nicht zu tun, aber es wäre nicht zu schwierig, den Code zu reparieren. oder stehlen Sie einfach den Code von Guava (Apache 2.0-Lizenz): code.google.com/p/guava-libraries/source/browse/trunk/src/com/…
Kevin Bourrillion
1
Fair genug, aber selbst die Guave ist anfällig für dasselbe, wenn ich es richtig lese. Wenn ein Benutzer eine Kopie des Ergebnisses von der Rückseite fernhalten würde, hätte dies das gleiche Problem.
Allain Lalonde

Antworten:

446

Versuche dies:

// 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());
}
John Feminella
quelle
4
Nicht schlecht. Verwendet den Index nicht, verliert aber die Eleganz von für jede Syntax. +1 sowieso.
Allain Lalonde
26
Wenn Sie listIterator () ohne Indexargument aufrufen, wird am Anfang der Liste ein Iterator angezeigt, und hasPrevious () gibt beim ersten Aufruf false zurück.
Adamski
2
Sie wollen einen Index für den listIteratorAnruf, denke ich.
Tom Hawtin - Tackline
1
Sie können eine schreiben Iterator, die eine ListIteratorUmkehrung verwendet, die sich jedoch für eine Schleife möglicherweise nicht lohnt.
Tom Hawtin - Tackline
1
Es ist keine einzige Schleife, also habe ich diese genommen und eingewickelt. pastebin.ca/1759041 also, jetzt kann ich tunfor (Node each : new ListReverse<Node>(nodes)) { }
Allain Lalonde
35

Guave bietet Lists#reverse(List)und ImmutableList#reverse(). Wie in den meisten Fällen für Guave delegiert der erstere an den letzteren, wenn das Argument ein ist ImmutableList, sodass Sie den ersteren in allen Fällen verwenden können. Diese erstellen keine neuen Kopien der Liste, sondern nur "umgekehrte Ansichten" davon.

Beispiel

List reversed = ImmutableList.copyOf(myList).reverse();
Geoffrey Zheng
quelle
23

Ich denke nicht, dass es möglich ist, die for-Schleifensyntax zu verwenden. Das einzige, was ich vorschlagen kann, ist etwas zu tun wie:

Collections.reverse(list);
for (Object o : list) {
  ...
}

... aber ich würde nicht sagen, dass dies "sauberer" ist, da es weniger effizient sein wird.

Adamski
quelle
26
und es ändert auch an Ort und Stelle die Liste, die Sie durchlaufen, was ein ziemlich großer Nebeneffekt ist. (Angenommen, Sie wickeln dies in eine Methode ein, jedes Mal, wenn sie aufgerufen wird, durchlaufen Sie die Liste in die andere Richtung ^^)
jolivier
Dies ist die sauberste Lösung.
11.
14

Option 1: Haben Sie darüber nachgedacht, die Liste mit Collections # reverse () umzukehren und dann foreach zu verwenden?

Natürlich möchten Sie Ihren Code möglicherweise auch so umgestalten, dass die Liste korrekt sortiert ist, damit Sie sie nicht umkehren müssen, was zusätzlichen Platz / Zeit beansprucht.


BEARBEITEN:

Option 2: Könnten Sie alternativ eine Deque anstelle einer ArrayList verwenden? Damit können Sie vorwärts und rückwärts iterieren


BEARBEITEN:

Option 3: Wie andere vorgeschlagen haben, können Sie einen Iterator schreiben, der die Liste in umgekehrter Reihenfolge durchläuft. Hier ein Beispiel:

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);
}
Kevin
quelle
1
Habe darüber nachgedacht, aber die Kosten für die Umkehrung sind unerschwinglich. Außerdem ist diese Art der Iteration nur etwa die Hälfte der Zeit erforderlich. Das Umdrehen würde das Problem nur auf die andere Hälfte verschieben.
Allain Lalonde
3
+ für Deque; typische Implementierungen haben descendingIterator().
Trashgod
Dies würde für verknüpfte Listen schrecklich funktionieren, die OP-Variante ist besser.
Masterxilo
1
Die Verwendung eines for eachAusdrucks ist meiner Meinung nach die idiomatischste Lösung. Es ist schön zu erkennen, dass dies möglich ist, wenn Ihre Liste Iterable so implementiert, dass es rückwärts iteriert. Ich werde diesen Ansatz verwenden und die ReverseListIterator-Klasse aus Apache Commons Collections verwenden.
David Groomes
11

Sie können die konkrete Klasse LinkedListanstelle der allgemeinen Schnittstelle verwenden List. Dann haben Sie eine descendingIteratorzum Iterieren mit der umgekehrten Richtung.

LinkedList<String > linkedList;
for( Iterator<String > it = linkedList.descendingIterator(); it.hasNext(); ) {
    String text = it.next();
}

Weiß nicht warum es keine gibt descendingIteratormit ArrayList...

Tangens
quelle
9

Dies ist eine alte Frage, aber es fehlt eine Java8-freundliche Antwort. Hier sind einige Möglichkeiten, die Liste mithilfe der Streaming-API rückgängig zu machen:

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
Federico Peralta Schaffner
quelle
2
sehr schön, nur eine kosmetische Änderung: int size = list.size (); ListIterator <Integer> it = list.listIterator (Größe); Stream.generate (it :: previous) .limit (size) .forEach (System.out :: println);
Benez
5

Hier ist eine (ungetestete) Implementierung von a ReverseIterable. Wenn iterator()es aufgerufen wird, wird eine private ReverseIteratorImplementierung erstellt und zurückgegeben , die einfach Aufrufe hasNext()an hasPrevious()und Aufrufe an next()zuordnet previous(). Dies bedeutet, dass Sie ArrayListwie folgt über eine Umkehrung iterieren können :

ArrayList<String> l = ...
for (String s : new ReverseIterable(l)) {
  System.err.println(s);
}

Klassendefinition

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()));
  }
}
Adamski
quelle
Sieht für mich richtig aus, obwohl die Bereitstellung als statische Methode anstelle eines öffentlichen Konstruktors (in den meisten Fällen) die Angabe des Typparameters durch den Client vermeiden würde. So macht es Guava ..
Kevin Bourrillion
2
Dies ist die beste Implementierung, ReverseIteratores fehlt jedoch der erforderliche Konstruktor und der Code sollte Liststattdessen verwendet werden ArrayList.
Andy
5

Wenn die Listen ziemlich klein sind, so dass die Leistung kein echtes Problem darstellt, kann man das reverse-metod der Lists-class in verwenden Google Guava. Ergibt hübschen for-eachCode und die ursprüngliche Liste bleibt gleich. Außerdem wird die umgekehrte Liste von der ursprünglichen Liste unterstützt, sodass jede Änderung an der ursprünglichen Liste in der umgekehrten Liste berücksichtigt wird.

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

Ergibt folgendes Ergebnis:

[one, two, three]
[three, two, one]
[one, two, three, four]
[four, three, two, one]

Dies bedeutet, dass die umgekehrte Iteration von myList wie folgt geschrieben werden kann:

for (final String someString : Lists.reverse(myList)) {
    //do something
}
Tobb
quelle
5

Erstellen Sie eine benutzerdefinierte reverseIterable.

Nanda
quelle
Ich weiß nicht, warum dies abgelehnt wird. Ich könnte einfach einen Wrapper für die Liste erstellen, die dies tut.
Allain Lalonde
Dies ist nicht weniger sauber als das Aufrufen von Collections.reverse () IMHO.
Adamski
@ Allain: Einverstanden bezüglich. die Downvotes, obwohl ich nicht verstehe, warum Sie einen Aufruf von listIterator (list.size ()) als "nicht sauber" ansehen. Selbst wenn Sie es einpacken, müssen Sie irgendwo denselben Methodenaufruf ausführen.
Adamski
Nehmen wir nicht an, nur nicht bereit, den Leistungseinbruch für die Sauberkeit zu nehmen.
Allain Lalonde
18
Abgestimmt, da ich dies nicht für eine vollständige Antwort halte.
Maarten Bodewes
3

Sehr einfaches Beispiel:

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) {
  ...
}
Ravi Kant Soni
quelle
2

Auch gefunden Google Sammlungen umgekehrte Methode.

Allain Lalonde
quelle
Welche Version der Google-Sammlung? Ihr Link existiert nicht mehr.
AaA
1

Um Code zu haben, der so aussieht:

List<Item> items;
...
for (Item item : In.reverse(items))
{
    ...
}

Fügen Sie diesen Code in eine Datei mit dem Namen "In.java" ein:

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();
                }
            };
        }
    }
}
unerschrocken
quelle
1
Dies wurde an anderer Stelle im Thread erwähnt, aber das listIteratorFeld muss sich innerhalb der IteratorImplementierung befinden, nicht in der IterableImplementierung.
Andy
1
Warum einen Aufzählungstyp verwenden, keine Klasse?
Aubin
1
Dadurch ist die 'In'-Klasse nicht instanziierbar, ohne dass ein privater Standardkonstruktor geschrieben werden muss. Gut für Klassen, die nur statische Methoden haben.
intrepidis
Ich würde sagen, dass der Missbrauch von Aufzählungen, nur um das Schreiben eines privaten Standardkonstruktors zu vermeiden, bestenfalls verwirrend ist. Wie wäre es mit Enums für Enums und Klassen für Klassen? Indem eine Klasse zu einer Aufzählung gemacht wird, erhält sie beispielsweise implizit auch eine name()Methode, eine ordinal()Methode und eine static valueOf()Methode.
JHH
1
Ja, Sie können mit Ihrer Meinung fortfahren und das wird auch gut funktionieren, aber ich denke das Gegenteil. Klassen dienen zum Instanziieren von Objekten, und der Missbrauch durch Einbeziehen eines privaten Standardkonstruktors, um deren Instanziierung zu verhindern, ist bestenfalls verwirrend. In Java sind Aufzählungen tatsächlich Klassen, aber solche, die vom Design her niemals instanziiert werden können.
Intrepidis
0

Wie mindestens zweimal vorgeschlagen wurde, können Sie descendingIteratormit a Deque, insbesondere mit a, verwenden LinkedList. Wenn Sie die for-each-Schleife verwenden möchten (dh eine haben Iterable), können Sie einen Wraper wie folgt erstellen und verwenden:

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);
        }
    }
}
masterxilo
quelle
-10

Grund: "Weiß nicht, warum es mit ArrayList keinen absteigenden Iterator gibt ..."

Da die Array-Liste die Liste nicht in derselben Reihenfolge hält, in der Daten zur Liste hinzugefügt wurden. Verwenden Sie also niemals Arraylist.

Die verknüpfte Liste hält die Daten in derselben Reihenfolge wie ADD to list.

Also habe ich oben in meinem Beispiel ArrayList () verwendet, um den Benutzer dazu zu bringen, seinen Verstand zu verdrehen und ihn dazu zu bringen, etwas von seiner Seite zu trainieren.

An Stelle von

List<String> list = new ArrayList<String>();

VERWENDEN:

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) {
  ...
}
Ravi Kant Soni
quelle
4
"Da die Array-Liste die Liste nicht in der Reihenfolge hält, in der Daten zur Liste hinzugefügt wurden" umm, ja, zumindest auf die gleiche Weise wie eine verknüpfte Liste. Können Sie ein Beispiel dafür geben, wie sie es nicht tun?
CorsiKa
Ja, ArrayList und LinkedList (The List-Vertrag im Allgemeinen) halten Elemente beim Einfügen in der richtigen Reihenfolge. Der Set-Vertrag ist ungeordnet oder sortiert (TreeSet). Die umgekehrte Idee ist nicht schlecht, aber denken Sie daran, dass sie die Liste tatsächlich neu ordnet, was langsam sein könnte.
Bill K
2
Ich habe diese Antwort abgelehnt, weil sie fälschlicherweise besagt, dass ArrayLists Elemente nicht in der Einfügereihenfolge halten. Wie @ bill-k vermerkt, sind alle Listen per Definition geordnete Sammlungen. Der Vorschlag, stattdessen eine LinkedList zu verwenden, hat seine Berechtigung, da er die Methode descendingIterator () enthält, jedoch nur, wenn die Leistung ein größeres Problem darstellt als Speicher und Abstraktion.
Michael Scheper