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 будет недопустимым. Следовательно, мы получаем Exception .
Обратите внимание, что мы сталкиваемся с этой проблемой только в том случае, если мы вызываем 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(E element) есть функция, о которой мы еще не упоминали: она возвращает логическое значение, которое верно , если список был изменен из-за операции, поэтому он содержит элемент .
Обратите внимание, что List.remove(int index) возвращает void, потому что, если предоставленный индекс действителен, List всегда удаляет его. В противном случае выбрасывается IndexOutOfBoundsException .
При этом мы можем выполнять удаления до тех пор, пока список не изменится:
void removeAll(List<Integer> list, int element) {
while (list.remove(element));
}
Он работает так, как ожидалось:
// given
List<Integer> 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<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));
Однако, если мы попробуем это с другим вводом, он выдаст неверный вывод:
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(1, 2, 3));
Давайте проанализируем, как работает код, шаг за шагом:
я = 0elementиlist.get(i)равны1в строке 3, поэтому Java входит в тело оператораif,мы удаляем элемент с индексом
0,поэтому
списоктеперь содержит1,2и3я = 1list.get(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++;
}
}
}
Обратите внимание, что в последнем мы удалили оператор i++ в строке 2.
Оба решения работают так, как ожидалось:
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));
Эта реализация кажется правильной на первый взгляд. Тем не менее, у него все еще есть серьезные проблемы с производительностью :
- удаление элемента из
ArrayListсдвигает все элементы после него - доступ к элементам по индексу в
LinkedListозначает обход элементов один за другим, пока мы не найдем индекс
4. Использование цикла for-each
Начиная с Java 5 мы можем использовать цикл for-each для перебора списка . Давайте используем его для удаления элементов:
void removeAll(List<Integer> list, int element) {
for (Integer number : list) {
if (Objects.equals(number, element)) {
list.remove(number);
}
}
}
Обратите внимание, что мы используем Integer в качестве типа переменной цикла. Поэтому мы не получим NullPointerException .
Кроме того, таким образом мы вызываем List.remove(E element) , который ожидает значение, которое мы хотим удалить, а не индекс.
Как бы чисто это ни выглядело, к сожалению, это не работает:
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove))
.isInstanceOf(ConcurrentModificationException.class);
Цикл for-each использует Iterator для обхода элементов. Однако, когда мы изменяем List , Iterator переходит в несогласованное состояние. Следовательно, он выдает ConcurrentModificationException .
Урок таков: мы не должны изменять List , пока мы обращаемся к его элементам в цикле for-each .
5. Использование итератора
Мы можем использовать итератор напрямую для обхода и изменения списка с его помощью:
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();
}
}
}
Таким образом, итератор может отслеживать состояние списка (поскольку он вносит изменения). В результате приведенный выше код работает так, как ожидалось:
// given
List<Integer> 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<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;
}
Поскольку мы предоставляем результат в новом объекте List , мы должны вернуть его из метода. Поэтому нам нужно использовать метод по-другому:
// 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));
Обратите внимание, что теперь мы можем использовать цикл for-each , так как мы не изменяем список , который сейчас просматриваем.
Поскольку нет никаких удалений, нет необходимости перемещать элементы. Поэтому эта реализация хорошо работает, когда мы используем ArrayList.
Эта реализация ведет себя иначе, чем предыдущие:
- он не изменяет исходный
список, а возвращает новый - метод решает, какова реализация возвращаемого списка
,она может отличаться от исходной.
Кроме того, мы можем изменить нашу реализацию, чтобы получить старое поведение ; очищаем исходный List и добавляем в него собранные элементы:
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);
}
Он работает так же, как и предыдущие:
// given
List<Integer> list = list(1, 1, 2, 3);
int valueToRemove = 1;
// when
removeAll(list, valueToRemove);
// then
assertThat(list).isEqualTo(list(2, 3));
Поскольку мы не изменяем список постоянно, нам не нужно обращаться к элементам по положению или сдвигать их. Кроме того, есть только два возможных перераспределения массива: когда мы вызываем List.clear() и List.addAll() .
7. Использование потокового API
В Java 8 появились лямбда-выражения и потоковый API. Благодаря этим мощным функциям мы можем решить нашу проблему с помощью очень чистого кода:
List<Integer> removeAll(List<Integer> list, int element) {
return list.stream()
.filter(e -> !Objects.equals(e, element))
.collect(Collectors.toList());
}
Это решение работает так же, как когда мы собирали оставшиеся элементы.
В итоге он имеет такие же характеристики , и мы должны использовать его для возврата результата:
// 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));
Обратите внимание, что мы можем преобразовать его для работы, как и другие решения, с тем же подходом, который мы использовали с исходной реализацией «сбора».
8. Использование removeIf
Вместе с лямбда-выражениями и функциональными интерфейсами в Java 8 также появились некоторые расширения API. Например, метод List.removeIf() , реализующий то, что мы видели в предыдущем разделе .
Он ожидает Predicate , который должен возвращать true , когда мы хотим удалить элемент, в отличие от предыдущего примера, где нам приходилось возвращать true , когда мы хотели сохранить элемент:
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));
В связи с тем, что сам список реализует этот метод, можно смело предположить, что он обладает наилучшей доступной производительностью. Кроме того, это решение обеспечивает самый чистый код из всех.
9. Заключение
В этой статье мы увидели множество способов решения простой задачи, в том числе и некорректных. Мы проанализировали их, чтобы найти лучшее решение для каждого сценария.
Как обычно, примеры доступны на GitHub .