Удалить все вхождения определенного значения из списка

Автор оригинала: Attila Fejér.

1. введение

В Java легко удалить определенное значение из List с помощью List.remove() . Однако эффективно удалить все вхождения значения гораздо сложнее.

В этом уроке мы увидим несколько решений этой проблемы, описывая плюсы и минусы.

Для удобства чтения мы используем пользовательский list(int…) метод в тестах, который возвращает ArrayList , содержащий элементы, которые мы передали.

2. Использование цикла while

Поскольку мы знаем, как удалить один элемент, делать это несколько раз в цикле выглядит достаточно просто:

void removeAll(List list, int element) {
    while (list.contains(element)) {
        list.remove(element);
    }
}

Однако это работает не так, как ожидалось:

// given
List list = list(1, 2, 3);
int valueToRemove = 1;

// when
assertThatThrownBy(() -> removeAll(list, valueToRemove))
  .isInstanceOf(IndexOutOfBoundsException.class);

Проблема в 3-й строке: мы вызываем List.remove(int), который рассматривает свой аргумент как индекс, а не значение, которое мы хотим удалить.

В приведенном выше тесте мы всегда вызываем list.remove(1) , но индекс элемента, который мы хотим удалить, равен 0. Вызов List.remove() сдвигает все элементы после удаленного на меньшие индексы.

В этом сценарии это означает, что мы удаляем все элементы, кроме первого.

Когда остается только первый, индекс 1 это будет незаконно. Следовательно, мы получаем Исключение .

Обратите внимание, что мы сталкиваемся с этой проблемой только в том случае, если вызываем List.remove() с примитивным byte , short, char или int аргументом, так как первое, что делает компилятор, когда он пытается найти соответствующий перегруженный метод, – это расширение.

Мы можем исправить это, передав значение как Integer:

void removeAll(List list, Integer element) {
    while (list.contains(element)) {
        list.remove(element);
    }
}

Теперь код работает так, как и ожидалось:

// given
List list = list(1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Поскольку List.contains() и List.remove() оба должны найти первое вхождение элемента, этот код вызывает ненужный обход элемента.

Мы можем сделать лучше, если сохраним индекс первого вхождения:

void removeAll(List list, Integer element) {
    int index;
    while ((index = list.indexOf(element)) >= 0) {
        list.remove(index);
    }
}

Мы можем убедиться, что это работает:

// given
List list = list(1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

В то время как эти решения производят короткий и чистый код, они все еще имеют низкую производительность : поскольку мы не отслеживаем прогресс, List.remove() должен найти первое вхождение предоставленного значения, чтобы удалить его.

Кроме того, когда мы используем ArrayList , смещение элементов может привести к многократному копированию ссылок, даже к перераспределению резервного массива несколько раз.

3. Удаление До тех пор, пока список не изменится

List.remove(E element) имеет функцию, о которой мы еще не упоминали: он возвращает логическое значение, которое является true если List изменился из-за операции, следовательно, он содержал элемент .

Обратите внимание, что List.remove(int index) возвращает void, потому что если предоставленный индекс действителен, то List всегда удаляет его. В противном случае он выбрасывает IndexOutOfBoundsException .

С помощью этого мы можем выполнять удаления до тех пор, пока Список не изменится:

void removeAll(List list, int element) {
    while (list.remove(element));
}

Он работает как и ожидалось:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

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

3. Использование цикла for

Мы можем отслеживать наш прогресс, проходя через элементы с помощью цикла for и удаляя текущий, если он совпадает:

void removeAll(List list, int element) {
    for (int i = 0; i < list.size(); i++) {
        if (Objects.equals(element, list.get(i))) {
            list.remove(i);
        }
    }
}

Он работает как и ожидалось:

// given
List list = list(1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Однако, если мы попробуем его с другим входом, он даст неправильный выход:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(1, 2, 3));

Давайте проанализируем, как работает код, шаг за шагом:

• i
  • элемент и list.get(i) равны 1 в строке 3, таким образом, Java входит в тело оператора if ,
  • мы удаляем элемент по индексу 0 ,
  • итак, список теперь содержит 1 , 2 и 3
• i
  • list.get(i) возвращает 2 потому что когда мы удаляем элемент из списка , он перемещает все исходящие элементы в меньшие индексы

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

Уменьшая его, когда мы удаляем элемент:

void removeAll(List list, int element) {
    for (int i = 0; i < list.size(); i++) {
        if (Objects.equals(element, list.get(i))) {
            list.remove(i);
            i--;
        }
    }
}

Увеличивая его только тогда, когда мы не удаляем элемент:

void removeAll(List list, int element) {
    for (int i = 0; i < list.size();) {
        if (Objects.equals(element, list.get(i))) {
            list.remove(i);
        } else {
            i++;
        }
    }
}

Обратите внимание, что в последнем случае мы удалили оператор i++ в строке 2.

Оба решения работают как и ожидалось:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Эта реализация кажется правильной на первый взгляд. Однако у него все еще есть серьезные проблемы с производительностью :

• удаление элемента из ArrayList сдвигает все элементы после него
• доступ к элементам по индексу в Связанном списке означает прохождение элементов один за другим, пока мы не найдем индекс

4. Использование цикла for-each

Начиная с Java 5, мы можем использовать цикл for-each для итерации по списку . Давайте используем его для удаления элементов:

void removeAll(List list, int element) {
    for (Integer number : list) {
        if (Objects.equals(number, element)) {
            list.remove(number);
        }
    }
}

Обратите внимание, что мы используем Integer в качестве типа переменной цикла. Поэтому мы не получим NullPointerException .

Кроме того, таким образом мы вызываем List.remove(E element) , который ожидает значение, которое мы хотим удалить, а не индекс.

Как бы чисто это ни выглядело, к сожалению, это не работает:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove))
  .isInstanceOf(ConcurrentModificationException.class);

Цикл for-each использует Итератор для перемещения по элементам. Однако/| когда мы изменяем Список , Итератор переходит в несогласованное состояние. Следовательно, он выбрасывает ConcurrentModificationException .

Урок таков: мы не должны изменять List , пока мы обращаемся к его элементам в цикле for-each .

5. Использование итератора

Мы можем использовать Итератор непосредственно для обхода и изменения списка с его помощью:

void removeAll(List list, int element) {
    for (Iterator i = list.iterator(); i.hasNext();) {
        Integer number = i.next();
        if (Objects.equals(number, element)) {
            i.remove();
        }
    }
}

Таким образом, Итератор может отслеживать состояние списка (потому что он вносит изменения). В результате приведенный выше код работает так, как и ожидалось:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Поскольку каждый класс List может предоставить свою собственную реализацию Iterator , мы можем с уверенностью предположить, что он реализует обход и удаление элементов наиболее эффективным способом.

Однако использование ArrayList по-прежнему означает большое смещение элементов (и, возможно, перераспределение массива). Кроме того, приведенный выше код немного сложнее читать, потому что он отличается от стандартного цикла for , с которым знакомы большинство разработчиков.

6. Коллекционирование

До этого мы модифицировали исходный объект List , удалив ненужные нам элементы. Скорее, мы можем создать новый Список и собрать элементы, которые мы хотим сохранить :

List removeAll(List list, int element) {
    List remainingElements = new ArrayList<>();
    for (Integer number : list) {
        if (!Objects.equals(number, element)) {
            remainingElements.add(number);
        }
    }
    return remainingElements;
}

Поскольку мы предоставляем результат в новом объекте List , мы должны вернуть его из метода. Поэтому нам нужно использовать этот метод по-другому:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
List result = removeAll(list, valueToRemove);

// then
assertThat(result).isEqualTo(list(2, 3));

Обратите внимание, что теперь мы можем использовать цикл for-each , так как мы не изменяем список , который мы сейчас перебираем.

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

Эта реализация ведет себя в некоторых отношениях иначе, чем предыдущие:

• он не изменяет исходный список , но возвращает новый
• метод решает , что такое возвращаемая реализация List , она может отличаться от исходной

Кроме того, мы можем изменить нашу реализацию, чтобы получить старое поведение ; мы очищаем исходный список и добавляем в него собранные элементы:

void removeAll(List list, int element) {
    List remainingElements = new ArrayList<>();
    for (Integer number : list) {
        if (!Objects.equals(number, element)) {
            remainingElements.add(number);
        }
    }

    list.clear();
    list.addAll(remainingElements);
}

Он работает так же, как и предыдущие:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

Поскольку мы не изменяем List постоянно, нам не нужно обращаться к элементам по позиции или сдвигать их. Кроме того, существует только два возможных перераспределения массивов: когда мы вызываем List.clear() и List.addAll() .

7. Использование Stream API

Java 8 представила лямбда-выражения и потоковый API. С помощью этих мощных функций мы можем решить нашу проблему с очень чистым кодом:

List removeAll(List list, int element) {
    return list.stream()
      .filter(e -> !Objects.equals(e, element))
      .collect(Collectors.toList());
}

Это решение работает так же, как и тогда, когда мы собирали оставшиеся элементы.

В результате он имеет те же характеристики , и мы должны использовать его для возврата результата:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
List result = removeAll(list, valueToRemove);

// then
assertThat(result).isEqualTo(list(2, 3));

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

8. Использование remove If

С помощью лямбд и функциональных интерфейсов Java 8 также представила некоторые расширения API. Например, метод List.removeIf () , реализующий то, что мы видели в предыдущем разделе .

Он ожидает Предикат , который должен возвращать true , когда мы хотим удалить элемент, в отличие от предыдущего примера, где мы должны были возвращать true , когда мы хотели сохранить элемент:

void removeAll(List list, int element) {
    list.removeIf(n -> Objects.equals(n, element));
}

Он работает так же, как и другие решения выше:

// given
List list = list(1, 1, 2, 3);
int valueToRemove = 1;

// when
removeAll(list, valueToRemove);

// then
assertThat(list).isEqualTo(list(2, 3));

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

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

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

Как обычно, примеры доступны на GitHub .