Перевертання списку в 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(list)

Якщо ви вже використовуєте 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() метод. Гуава є великою залежністю, і використовувати її лише для цієї операції буде надмірним.

List.add() і List.remove()

Якщо ви бажаєте виконати додаткові операції, окрім простого перевертання списку, ви можете пройти через вихідний список, видалити елементи з кінця, передати їх через довільний метод і додати їх назад на початку списку:

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() метод і ручний підхід.