Inverser une liste en Java - En place et hors place

Dans ce court didacticiel, vous apprendrez à inverser une liste en place et hors de place en Java.

Inversion sur place et hors place

Lors de l'exécution d'opérations sur des listes, vous voudrez peut-être déterminer si les opérations sont effectuées sur place (les modifications sont appliquées à l'objet d'origine) ou si elles ne sont pas à leur place (les modifications sont appliquées à une copie et l'original l'objet est inchangé).

Certains langages et bibliothèques préfèrent différents comportements par défaut. En Java, la plupart des opérations sur les listes inversées seront en place.

Si c'est le comportement que vous souhaitez, c'est parfait ! Sinon, vous voudrez créer une copie de la liste avant d'inverser la copie :

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Remarque: La clone() méthode d'un créer une copie profonde. Création d'une liste à l'aide new ArrayList(list) d'un créer une copie profonde. La création de copies complètes est déconseillée et étonnamment difficile à faire de manière générique (et n'a pas de sens dans certains cas, selon le ou les types de données dans la liste). Cela ne vous empêchera pas de pouvoir inverser list ainsi que ne sauraient avoir les éléments de listCopy étant inversé, cependant.

Collections.reverse()

La Collections.reverse() méthode est la méthode standard pour inverser une collection, et agit comme le "manquant" List.reverse() méthode. Il inverse la liste sur place :

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Collections.reverse(list);

System.out.println(list);     
System.out.println(listCopy); 

Listes de goyave.reverse(list)

Si vous utilisez déjà Google Guava dans votre projet, vous pouvez également tirer parti du Lists classe, qui offre la reverse() méthode, qui ne trie pas la liste d'origine sur place, mais crée une copie et inverse la copie :

List list = new ArrayList(Arrays.asList(1, 2, 3));
List reversedList = Lists.reverse(list);

System.out.println(list);         
System.out.println(reversedList); 

Si vous ne l'avez pas déjà, vous pouvez ajouter Google Guava à votre projet à l'aide de Maven, en incluant sa dépendance dans votre pom.xml fichier:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
</dependency>

Ou via Gradle :

implementation group: 'com.google.guava', name: 'guava'

Remarque: Si vous n'avez pas déjà Google Guava ou si vous n'avez pas l'intention de l'utiliser pour d'autres parties de votre projet, ne l'importez pas uniquement pour cette opération et respectez les Collections.reverse() méthode. La goyave est une grande dépendance, et c'est une surpuissance majeure de l'utiliser uniquement pour cette opération.

List.add() et List.remove()

Si vous souhaitez effectuer des opérations supplémentaires en plus de simplement inverser la liste, vous pouvez parcourir la liste d'origine, supprimer les éléments de la fin, les passer par une méthode arbitraire et les ajouter au début de la liste :

public static int process(int input) {
    return input;
}

List list = new ArrayList(Arrays.asList(1, 2, 3));

for (int i = 0, j = list.size()-1; i <= j; i++) {
    int lastValue = process(list.remove(j));
    list.add(i, lastValue);
}

System.out.println(list);  

référence

Alors, lequel est le plus rapide ? Cela dépend également si vous souhaitez effectuer l'opération sur place ou hors place.

Référence d'inversion en place

Comparons les deux approches sur les trois méthodes, en commençant par hors de propos :

List list = new Random().ints(100, 1, 11)
                .boxed()
                .collect(Collectors.toList());

int runs = 1000;

long start1 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListCollections(list);
}
long end1 = System.currentTimeMillis();
System.out.println(String.format("Collections.reverse() took: %s miliseconds", end1-start1));

long start2 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListGuava(list);
}
long end2 = System.currentTimeMillis();
System.out.println(String.format("Guava's Lists.reverse() took: %s miliseconds", end2-start2));

long start3 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListManually(list);
}
long end3 = System.currentTimeMillis();
System.out.println(String.format("Manually took: %s miliseconds", end3-start3));

System.out.println("Original list: " + list);

Cela se traduit par:

Collections.reverse() took: 3 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 13 miliseconds
Original list: [6, 7, 9, 7, 2, 5, 4, 1, 3, 2, 2, 6, ...

Que se passe-t-il lorsque nous augmentons le nombre d'éléments de 100 à 1000 ?

Collections.reverse() took: 9 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 133 miliseconds
Original list: [10, 2, 2, 6, 2, 4, 7, 3, 9, 2, 7, 5, ...

La goyave conserve la marque des 4 ms ! L'approche manuelle a la pire complexité temporelle, et elle a augmenté de manière linéaire. Collections.reverse() souffrent moins de la mise à l'échelle, mais la mise en œuvre de Guava souffre le moins. Cependant, gardez à l'esprit que nous ne copions pas manuellement la liste pour l'approche Guava. La référence changera-t-elle lorsque nous abandonnerons l'idée d'avoir une liste « originale » et « inversée » ?

Indice de référence d'inversion hors place

Avec 1000 éléments, et chacun fonctionnant sur une copie non inversée de la liste (qui a été exclue des mesures de temps), lorsque nous supprimons la copie manuelle de chaque méthode et réexécutons le code :

Collections.reverse() took: 7 miliseconds
Guava's Lists.reverse() took: 3 miliseconds
Manually took: 131 miliseconds
Original list: [6, 8, 10, 7, 3, 8, 7, 1, 1, 9, 5, ...

Goyave toujours parvient à surpasser constamment les deux Collections.reverse() et l'approche manuelle.

Conclusion

Dans ce petit guide, vous avez appris à inverser une liste en Java, en place et hors place, en préservant la liste d'origine de l'opération. Nous avons utilisé le Collections.reverse() méthode, celle de Google Guava Lists.reverse() méthode et une approche manuelle.