«1. Введение
В Java просто удалить конкретное значение из списка с помощью List.remove(). Однако эффективно удалить все вхождения значения намного сложнее.
В этом уроке мы увидим несколько решений этой проблемы с описанием плюсов и минусов.
Ради удобочитаемости мы используем в тестах пользовательский метод list(int…), который возвращает ArrayList, содержащий переданные нами элементы.
2. Использование цикла while
Поскольку мы знаем, как удалить один элемент, повторяющееся выполнение этого действия в цикле выглядит достаточно просто:
void removeAll(List<Integer> list, int element) {
while (list.contains(element)) {
list.remove(element);
}
}Однако это не работает должным образом: ~~ ~
// given
List<Integer> 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<Integer> list, Integer element) {
while (list.contains(element)) {
list.remove(element);
}
}Теперь код работает так, как ожидалось:
// given
List<Integer> 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<Integer> list, Integer element) {
int index;
while ((index = list.indexOf(element)) >= 0) {
list.remove(index);
}
}Мы можем убедиться, что это работает:
// given
List<Integer> 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(int index) возвращает void, потому что, если предоставленный индекс действителен, List всегда удаляет его. В противном случае выдается исключение IndexOutOfBoundsException.
Таким образом, мы можем выполнять удаления до тех пор, пока список не изменится:
Работает так, как ожидалось:
Несмотря на свою краткость, эта реализация страдает от тех же проблем, которые мы описали в предыдущем разделе.
void removeAll(List<Integer> list, int element) {
while (list.remove(element));
}3. Использование цикла for
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));Мы можем отслеживать наш прогресс, просматривая элементы с помощью цикла for и удаляя текущий элемент, если он соответствует:
Это работает так, как ожидалось: ~~ ~
Однако, если мы попробуем это с другим вводом, он выдаст неверный вывод:
void removeAll(List<Integer> list, int element) {
for (int i = 0; i < list.size(); i++) {
if (Objects.equals(element, list.get(i))) {
list.remove(i);
}
}
}Давайте проанализируем, как работает код, шаг за шагом:
// given
List<Integer> list = list(1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));i = 0 элемент и список. get(i) равны 1 в строке 3, поэтому Java входит в тело оператора if, мы удаляем элемент с индексом 0, поэтому list теперь содержит 1, 2 и 3 i = 1 list.get(i) возвращает 2, потому что когда мы удаляем элемент из списка, он сдвигает все последующие элементы на меньшие индексы
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(1, 2, 3));Таким образом, мы сталкиваемся с этой проблемой, когда у нас есть два соседних значения, которые мы хотим удалить. Чтобы решить эту проблему, мы должны сохранить переменную цикла.
-
Уменьшение, когда мы удаляем элемент:
Увеличиваем, только когда мы не удаляем элемент:
Обратите внимание, что в последнем случае мы удалили оператор i++ в строке 2 .
void removeAll(List<Integer> 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<Integer> list, int element) {
for (int i = 0; i < list.size();) {
if (Objects.equals(element, list.get(i))) {
list.remove(i);
} else {
i++;
}
}
}Эта реализация кажется правильной на первый взгляд. Тем не менее, он по-прежнему имеет серьезные проблемы с производительностью:
удаление элемента из ArrayList сдвигает все элементы после него. Доступ к элементам по индексу в LinkedList означает обход элементов один за другим, пока мы не найдем индекс
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));4 , Использование цикла for-each
-
«Начиная с Java 5 мы можем использовать цикл for-each для перебора списка. Давайте используем его для удаления элементов:
Обратите внимание, что мы используем Integer в качестве типа переменной цикла. Поэтому мы не получим исключение NullPointerException.
Кроме того, таким образом мы вызываем List.remove(E element), который ожидает значение, которое мы хотим удалить, а не индекс.
void removeAll(List<Integer> list, int element) {
for (Integer number : list) {
if (Objects.equals(number, element)) {
list.remove(number);
}
}
}Как бы чисто это ни выглядело, к сожалению, это не работает:
Цикл for-each использует итератор для обхода элементов. Однако, когда мы изменяем список, итератор переходит в несогласованное состояние. Следовательно, он генерирует исключение ConcurrentModificationException.
Урок таков: мы не должны изменять список, пока обращаемся к его элементам в цикле for-each.
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove))
.isInstanceOf(ConcurrentModificationException.class);5. Использование итератора
Мы можем использовать итератор напрямую для обхода и изменения списка с его помощью:
Таким образом, итератор может отслеживать состояние списка (поскольку он делает модификацию ). В результате приведенный выше код работает так, как ожидалось:
Поскольку каждый класс List может предоставить свою собственную реализацию Iterator, мы можем с уверенностью предположить, что он реализует обход и удаление элементов наиболее эффективным способом.
void removeAll(List<Integer> list, int element) {
for (Iterator<Integer> i = list.iterator(); i.hasNext();) {
Integer number = i.next();
if (Objects.equals(number, element)) {
i.remove();
}
}
}Однако использование ArrayList по-прежнему означает большое смещение элементов (и, возможно, перераспределение массива). Кроме того, приведенный выше код немного сложнее читать, поскольку он отличается от стандартного цикла for, с которым знакомо большинство разработчиков.
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));6. Сбор
До этого мы модифицировали исходный объект List, удаляя ненужные элементы. Вместо этого мы можем создать новый список и собрать элементы, которые хотим сохранить:
Поскольку мы предоставляем результат в новом объекте списка, мы должны вернуть его из метода. Поэтому нам нужно использовать метод по-другому:
Обратите внимание, что теперь мы можем использовать цикл for-each, так как мы не модифицируем список, который мы в данный момент итерируем.
List<Integer> removeAll(List<Integer> list, int element) {
List<Integer> remainingElements = new ArrayList<>();
for (Integer number : list) {
if (!Objects.equals(number, element)) {
remainingElements.add(number);
}
}
return remainingElements;
}Поскольку нет никаких удалений, нет необходимости сдвигать элементы. Поэтому эта реализация хорошо работает, когда мы используем ArrayList.
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
List<Integer> result = removeAll(list, valueToRemove);
// then
assertThat(result).isEqualTo(list(2, 3));Эта реализация в некоторых отношениях ведет себя иначе, чем предыдущие:
она не изменяет исходный список, а возвращает новый метод решает, какова реализация возвращенного списка, она может отличаться от реализации original
Кроме того, мы можем изменить нашу реализацию, чтобы получить старое поведение; мы очищаем исходный список и добавляем в него собранные элементы:
-
Он работает так же, как и предыдущие:
Поскольку мы не изменяем список постоянно, нам не нужно доступ к элементам по положению или сдвиг их. Кроме того, есть только два возможных перераспределения массива: когда мы вызываем List.clear() и List.addAll().
void removeAll(List<Integer> list, int element) {
List<Integer> remainingElements = new ArrayList<>();
for (Integer number : list) {
if (!Objects.equals(number, element)) {
remainingElements.add(number);
}
}
list.clear();
list.addAll(remainingElements);
}7. Использование Stream API
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));В Java 8 появились лямбда-выражения и потоковый API. Благодаря этим мощным функциям мы можем решить нашу проблему с очень чистым кодом:
Это решение работает так же, как когда мы собирали оставшиеся элементы.
В результате он имеет те же характеристики, и мы должны использовать его для возврата результата: оригинальная реализация «сбора».
List<Integer> removeAll(List<Integer> list, int element) {
return list.stream()
.filter(e -> !Objects.equals(e, element))
.collect(Collectors.toList());
}8. Использование removeIf
Вместе с лямбда-выражениями и функциональными интерфейсами в Java 8 также появились некоторые расширения API. Например, метод List.removeIf(), реализующий то, что мы видели в предыдущем разделе.
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
List<Integer> result = removeAll(list, valueToRemove);
// then
assertThat(result).isEqualTo(list(2, 3));Ожидается предикат, который должен возвращать true, когда мы хотим удалить элемент, в отличие от предыдущего примера, где нам приходилось возвращать true, когда мы хотели сохранить элемент:
Это работает как другие решения выше:
В связи с тем, что сам список реализует этот метод, мы можем с уверенностью предположить, что он имеет наилучшую доступную производительность. Кроме того, это решение обеспечивает самый чистый код из всех.
9. Заключение
void removeAll(List<Integer> list, int element) {
list.removeIf(n -> Objects.equals(n, element));
}В этой статье мы увидели много способов решения простой задачи, в том числе и некорректных. Мы проанализировали их, чтобы найти лучшее решение для каждого сценария.
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));Как обычно, примеры доступны на GitHub.
«
In this article, we saw many ways to solve a simple problem, including incorrect ones. We analyzed them to find the best solution for every scenario.
As usual, the examples are available over on GitHub.