Реверсирование списка в Java — на месте и вне места

В этом кратком руководстве вы узнаете, как инвертировать список на месте и вне места в Java.

Реверсирование на месте и не на месте

Выполняя операции со списками, вы можете подумать, выполняются ли операции на месте (изменения вносятся в исходный объект) или неуместно (изменения вносятся в копию, а исходный объект не изменился).

Некоторые языки и библиотеки предпочитают другое поведение по умолчанию. В Java большинство операций по обращению списков будут на месте.

Если это желаемое поведение — отлично! Если нет, вам нужно создать копию списка, прежде чем отменить копию:

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

Примечание: Ассоциация clone() метод не создать глубокую копию. Создание списка с помощью new ArrayList(list) не создать глубокую копию. Создание глубоких копий не рекомендуется и на удивление сложно сделать общим способом (и в некоторых случаях не имеет смысла, в зависимости от типа(ов) данных в списке). Это не помешает вам изменить list и не иметь элементы listCopy хотя переворачивается.

Collections.reverse ()

Ассоциация Collections.reverse() метод является стандартным методом обращения коллекции и действует как «отсутствующий» List.reverse() метод. Он переворачивает список на месте:

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

Списки Гуавы.reverse(список)

Если вы уже используете Google Guava в своем проекте, вы также можете использовать Lists класс, который предлагает reverse() метод, который не сортирует исходный список на месте, а создает копию и переворачивает копию:

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

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

Если у вас его еще нет, вы можете добавить Google Guava в свой проект с помощью Maven, включив его зависимость в свой pom.xml файл:

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

Или через Gradle:

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

Примечание: Если у вас еще нет Google Guava или вы не собираетесь использовать его для других частей вашего проекта, не импортируйте его только для этой операции и придерживайтесь Collections.reverse() метод. Guava - это большая зависимость, и использовать ее только для этой операции - это серьезное излишество.

Список.добавить() и Список.удалить()

Если вы хотите выполнить дополнительные операции, помимо простого переворота списка — вы можете перебрать исходный список, удалить элементы из конца, передать их произвольным методом и добавить обратно в начало списка:

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

эталонный тест

Итак, какой из них самый быстрый? Это также зависит от того, хотите ли вы выполнить операцию на месте или вне ее.

Контрольный показатель разворота на месте

Давайте сравним оба подхода по всем трем методам, начиная с неуместного:

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

Это приводит к:

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, ...

Что произойдет, если мы увеличим количество элементов со 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, ...

Гуава сохраняет отметку 4 мс! Ручной подход имеет наихудшую временную сложность, и она росла линейно. Collections.reverse() меньше страдают от масштабирования, но меньше всего страдает реализация Guava. Однако имейте в виду, что мы не копируем список вручную для подхода Guava. Изменится ли контрольный показатель, когда мы откажемся от идеи наличия «исходного» и «обратного» списка?

Индикатор неуместного разворота

С 1000 элементами, каждый из которых работает с неинвертированной копией списка (которая была исключена из измерений времени), когда мы удаляем ручную копию из каждого метода и перезапускаем код:

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, ...

Гуава все еще удается последовательно превосходить оба Collections.reverse() и ручной подход.

Заключение

В этом кратком руководстве вы узнали, как инвертировать список в Java, на месте и вне места, сохраняя исходный список из операции. Мы использовали Collections.reverse() метод Google Guava Lists.reverse() метод и ручной подход.