Удаление элементов в списке при повторении через него

Мне понадобился способ удаления элементов в List во время итерации через него.

Предположительно что-то вроде этого (незаконный код) :

List<Integer> nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
...
nums.add(10);

System.out.println("BEFORE REMOVE: " + nums);

for (Integer integer : nums) {
    if (integer < 3) {
        //not allowed
        nums.remove(integer);
    }
}

Но мы все знаем, что вышеуказанный код не разрешен.

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

List

Я знаю, что это не очень долго, но есть ли лучший способ сделать это?

Есть ли какой-нибудь API, который я могу использовать?

39 голосов | спросил lxcky 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 27 Sep 2014 10:20:22 +0400 2014, 10:20:22

5 ответов


55

Есть несколько способов сделать это. Давайте посмотрим на альтернативы:

Итерация над копией, удаление из оригинала

Это простое решение для основной проблемы вашего первого кода: A ConcurrentModificationException вызывается из-за того, что вы перебираете список и удаляете его одновременно.

Простое решение - создать копию списка и перебрать его.

for (Integer integer : new ArrayList<>(nums)) {
    if (integer < 3) {
        nums.remove(integer);
    }
}

Нижние стороны этого подхода:

  • Создает копию исходного списка, для которого требуется память и операция, производительность которой зависит от типа списка (ArrayList, LinkedList и т. д.).
  • Кроме того, nums.remove(value) является операцией \ $ O (n) \ $. Выполнение этого цикла в целом \ $ O (n ^ 2) \ $

Потоки Java 8

List<Integer> filteredList = nums.stream().filter(i -> i >= 3).collect(Collectors.toList());

Вниз стороны:

  • Фактически не изменяет существующий список, поэтому, если ссылки на список распределены вокруг разных переменных, у вас все еще есть некоторые старые элементы, которые просто не должны быть в этом списке.
  • Создает различные связанные с потоком объекты, которые могут быть не самыми эффективными.

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

Если вы не используете Java 8:

List<Object> originalList;
List<Object> newList = new YourFavoriteListType<>();
for (Object obj : originalList) {
    if (shouldKeep(obj)) {
        newList.add(obj);
    }
}

Iterator.remove ()

Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    Integer integer = it.next();
    if (integer < 3) {
        it.remove();
    }
}

Единственная нижняя сторона этого подхода заключается в том, что вам нужно переключить for-each на while. Однако этот подход является наиболее эффективным, особенно для LinkedList, где это \ $ O (n) \ $ (это \ $ O (n ^ 2) \ $ для ArrayList, потому что он должен копировать данные массива при каждом вызове remove(index)). Это подход, который я бы рекомендовал в большинстве случаев.

Примечание. Вместо использования цикла while он также может быть записан как:

for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    Integer integer = it.next();
    ...

См. также

«Когда использовать LinkedList над ArrayList?» при переполнении стека

ответил Simon Forsberg 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 27 Sep 2014 17:46:06 +0400 2014, 17:46:06
17

Просто нужно было сделать что-то очень похожее (следовательно, почему я здесь), в итоге использовал Java8 'Collection.removeIf(Predicate<? super E> filter)

С вашим кодом это будет выглядеть так:

nums.removeIf((Integer i)->{return i<3;});

И если вы хотите собрать удаляет:

List<Integer> removed = new ArrayList<>();
nums.removeIf(
    (Integer i)->{
        boolean remove = i<3;
        if (remove) {
            removed.add(i);
        }
        return remove;
    });
ответил Bob Davies 5 J0000006Europe/Moscow 2015, 19:22:03
6

Из других представленных решений все, кроме тех, которые используют Java 8, выглядят как O(n**2), т.е. слишком медленны, когда список (*) становится немного больше.

Самое простое быстрое решение - создать пустой список и добавить все элементы не менее трех.

Если вам нужно изменить исходный список, тогда очистите, если потом, и добавьте все элементы из вспомогательного списка.


(*) Если это не LinkedList, который отличается здесь. Но его производительность во всех других сценариях настолько ужасна, что ее практически не использовать.

ответил maaartinus 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 27 Sep 2014 19:54:11 +0400 2014, 19:54:11
3

Добавив к ответу @ SimonAndre, вы можете использовать обратный цикл for, чтобы пройти через ваш массив, чтобы удалить ненужные элементы. Он остается операцией O (n ^ 2) из-за метода remove. Таким образом, этот подход не лучше, но это другой способ сделать это.

for(int index = array.size() - 1; index >= 0; index--) {
    if(array.get(index) < 3){
        array.remove(index);
    }
}
ответил IEatBagels 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 27 Sep 2014 20:19:38 +0400 2014, 20:19:38
3

Другим, возможно, интересным вариантом является использование CopyOnWriteArrayList:

@Test
public void testCanRemoveFromCopyOnWriteArrayList() {
    List<Integer> nums = new CopyOnWriteArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    for (Integer num : nums) {
        if (num < 3) {
            nums.remove(num);
        }
    }
    assertEquals(Arrays.asList(3, 4, 5), nums);
}

Недостаток очевидный: от имени класса: он копирует основной список перед каждой операцией записи. Этот класс предназначен для списков наблюдателей , которые редко изменяются и часто пересекаются. Я не уверен, что это относится к вашему делу (если удаление из списка будет частым или нет), но я думал, что упомянул об этом на всякий случай.

ответил janos 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 27 Sep 2014 23:57:36 +0400 2014, 23:57:36

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132