Обратный ArrayList в Java

1. Обзор

ArrayList — это часто используемая реализация List в Java.

В этом руководстве мы рассмотрим, как реверсировать ArrayList .

2. Введение в проблему

Как обычно, давайте разберемся в проблеме на примере. Допустим, у нас есть список целых чисел :

​List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));

После реверсирования мы ожидаем получить результат:

List<Integer> EXPECTED = new ArrayList<>(Arrays.asList(7, 6, 5, 4, 3, 2, 1));

Таким образом, требование выглядит довольно простым. Однако проблема может иметь несколько вариантов:

• Реверсирование списка на месте
• Обращение списка и возврат результата в виде нового объекта списка

В этом уроке мы рассмотрим оба случая.

Стандартная библиотека Java предоставила вспомогательный метод для выполнения этой работы. Посмотрим, как мы можем быстро решить проблему, используя этот метод.

Кроме того, учитывая, что некоторые из нас могут изучать Java, мы рассмотрим две интересные, но эффективные реализации реверсирования List .

Далее давайте посмотрим на них в действии.

3. Использование стандартного метода Collections.reverse

Стандартная библиотека Java предоставляет метод Collections.reverse для изменения порядка элементов в заданном List .

Этот удобный метод выполняет реверсирование на месте, которое меняет порядок в исходном списке, который он получил. Но сначала давайте создадим метод модульного тестирования, чтобы понять это:

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
Collections.reverse(aList);
assertThat(aList).isEqualTo(EXPECTED);

Когда мы выполняем тест выше, он проходит. Как мы видели, мы передали объект aList обратному методу, после чего порядок элементов в объекте aList меняется на противоположный.

Если мы не хотим изменять исходный List и ожидаем получить новый объект List , содержащий элементы в обратном порядке, мы можем передать новый объект List обратному методу:

List<Integer> originalList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> aNewList = new ArrayList<>(originalList);
Collections.reverse(aNewList);

assertThat(aNewList).isNotEqualTo(originalList).isEqualTo(EXPECTED);

Таким образом, мы сохраняем исходный список нетронутым, а порядок элементов в новом списке меняется на противоположный.

Как видно из двух приведенных выше примеров, стандартный метод Collections.reverse довольно удобен для реверсирования List .

Однако, если мы изучаем Java, возможно, мы хотим сами попрактиковаться в реализации «обратного» метода.

Далее давайте рассмотрим пару хороших реализаций: одну с использованием рекурсии, а другую с использованием простого цикла.

4. Реверсирование списка с помощью рекурсии

Во-первых, давайте реализуем наш собственный метод обратного списка, используя метод рекурсии . Во-первых, давайте посмотрим на реализацию:

public static <T> void reverseWithRecursion(List<T> list) {
    if (list.size() > 1) {
        T value = list.remove(0);
        reverseWithRecursion(list);
        list.add(value);
    }
}

Как мы видим, реализация выше выглядит довольно компактно. Теперь давайте разберемся, как это работает.

Условием остановки в нашей логике рекурсии является list.size() <=1 . Другими словами, если объект списка пуст или содержит только один элемент, мы останавливаем рекурсию .

В каждом вызове рекурсии мы выполняем « T value = list.remove(0) », извлекая первый элемент из списка. Это работает следующим образом:

recursion step 0: value = null, list = (1, 2, 3, ... 7)
   |_ recursion step 1: value = 1, list = (2, 3, 4,...7)
      |_ recursion step 2: value = 2, list = (3, 4, 5, 6, 7)
         |_ recursion step 3: value = 3, list = (4, 5, 6, 7)
            |_ ...
               |_ recursion step 6: value = 6, list = (7)

Как мы видим, когда объект списка содержит только один элемент (7), мы останавливаем рекурсию и начинаем выполнять list.add(value) снизу. То есть сначала добавляем в конец списка 6, потом 5, потом 4 и так далее. В конце концов, порядок элементов в списке был изменен на противоположный. Кроме того, этот метод работает за линейное время .

Затем давайте создадим тест, чтобы проверить, работает ли наша реализация рекурсии должным образом:

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithRecursion(aList);
assertThat(aList).isEqualTo(EXPECTED);

Если мы запустим тест, он пройдет. Итак, наша реализация рекурсии решает проблему.

5. Обращение списка с помощью итерации

Мы только что перевернули список, используя рекурсию. В качестве альтернативы мы можем решить проблему с помощью итерации.

Во-первых, давайте посмотрим на реализацию:

public static <T> void reverseWithLoop(List<T> list) {
    for (int i = 0, j = list.size() - 1; i < j; i++) {
        list.add(i, list.remove(j));
    }
}

Как мы видим, реализация итерации также довольно аккуратна. Однако у нас есть только один цикл for , и в теле цикла у нас есть только один единственный оператор.

Далее давайте разберемся, как это работает.

Мы определили два указателя i и j на заданный список. Указатель j всегда указывает на последний элемент в списке. Но точка i увеличивается от 0 до j-1 .

Мы удаляем последний элемент на каждом шаге итерации и заполняем его до i-й позиции, используя list.add(i, list.remove(j)) . Когда i достигает j-1 , цикл завершается, и мы переворачиваем список:

Iteration step 0: i = j = null, list = (1, 2, 3,...7)
Iteration step 1: i = 0; j = 6 
                  |_ list.add(0, list.remove(6))
                  |_ list = (7, 1, 2, 3, 4, 5, 6)
Iteration step 2: i = 1; j = 6 
                  |_ list.add(1, list.remove(6))
                  |_ list = (7, 6, 1, 2, 3, 4, 5)
...
Iteration step 5: i = 4; j = 6 
                  |_ list.add(4, list.remove(6))
                  |_ list = (7, 6, 5, 4, 3, 1, 2)
Iteration step 6: i = 5; j = 6 
                  |_ list.add(5, list.remove(6))
                  |_ list = (7, 6, 5, 4, 3, 2, 1)

Метод также работает в линейном времени.

Наконец, давайте проверим наш метод и посмотрим, работает ли он так, как ожидалось:

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithLoop(aList);
assertThat(aList).isEqualTo(EXPECTED);

Когда мы запускаем тест выше, он проходит.

6. Заключение

В этой статье мы рассмотрели, как реверсировать ArrayList на примерах. Стандартный метод Collections.reverse очень удобен для решения этой проблемы.

Однако, если мы хотим создать свои собственные реализации реверсирования, мы изучили два эффективных подхода к реверсированию на месте.

Как обычно, полный код этой статьи можно найти на GitHub .