リストから特定の値のすべてのオカレンスを削除します

1.はじめに

Javaでは、List.remove()を使用してリストから特定の値を削除するのは簡単です。ただし、値の出現をすべて効率的に削除することははるかに困難です。

このチュートリアルでは、この問題に対する複数の解決策を見て、長所と短所を説明します。

読みやすくするために、テストではカスタムlist(int…)メソッドを使用します。このメソッドは、渡した要素を含むArrayListを返します。

2.使用している間ループを

単一の要素削除する方法を知っているので、ループ内で繰り返し実行するのは簡単に見えます。

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は違法になります。したがって、例外が発生します

この問題に直面するのは、プリミティブのbyteshort、char、またはint引数を指定してList.remove()を呼び出す場合のみです。これは、コンパイラが一致するオーバーロードされたメソッドを見つけようとするときに最初に行うことは拡大しているためです。

値を整数として渡すことで修正できます

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.remove(int index)はvoidを返すことに注意してください。指定されたインデックスが有効な場合、リストは常にそれを削除するためです。それ以外の場合は、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ループを使用して要素をトラバースし、一致する場合は現在の要素を削除することで、進行状況を追跡できます。

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 = 0
    • element and list.get(i) are both equal to 1 at line 3, so Java enters the body of the if statement,
    • we remove the element at index 0,
    • so list now contains 1, 2 and 3
  • i = 1
    • list.get(i) returns 2 because when we remove an element from a List, it shifts all proceeding elements to smaller indices

So we face this problem when we have two adjacent values, which we want to remove. To solve this, we should maintain the loop variable.

Decreasing it when we remove the element:

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--; } } }

Increasing it only when we don't remove the element:

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++; } } }

Note, that in the latter, we removed the statement i++ at line 2.

Both solutions work as expected:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

This implementation seems right for the first sight. However, it still has serious performance problems:

  • removing an element from an ArrayList, shifts all items after it
  • accessing elements by index in a LinkedList means traversing through the elements one-by-one until we find the index

4. Using a for-each Loop

Since Java 5 we can use the for-each loop to iterate through a List. Let's use it to remove elements:

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

Note, that we use Integer as the loop variable's type. Therefore we won't get a NullPointerException.

Also, this way we invoke List.remove(E element), which expects the value we want to remove, not the index.

As clean as it looks, unfortunately, it doesn't work:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when assertThatThrownBy(() -> removeWithForEachLoop(list, valueToRemove)) .isInstanceOf(ConcurrentModificationException.class);

The for-each loop uses Iterator to traverse through the elements. However, when we modify the List, the Iterator gets into an inconsistent state. Hence it throws ConcurrentModificationException.

The lesson is: we shouldn't modify a List, while we're accessing its elements in a for-each loop.

5. Using an Iterator

We can use the Iterator directly to traverse and modify the List with it:

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

This way, the Iterator can track the state of the List (because it makes the modification). As a result, the code above works as expected:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Since every List class can provide their own Iterator implementation, we can safely assume, that it implements element traversing and removal the most efficient way possible.

However, using ArrayList still means lots of element shifting (and maybe array reallocating). Also, the code above is slightly harder to read, because it differs from the standard for loop, that most developers are familiar with.

6. Collecting

Until this, we modified the original List object by removing the items we didn't need. Rather, we can create a new List and collect the items we want to keep:

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

Since we provide the result in a new List object, we have to return it from the method. Therefore we need to use the method in another way:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when List result = removeAll(list, valueToRemove); // then assertThat(result).isEqualTo(list(2, 3));

Note, that now we can use the for-each loop since we don't modify the List we're currently iterating through.

Because there aren't any removals, there's no need to shift the elements. Therefore this implementation performs well when we use an ArrayList.

This implementation behaves differently in some ways than the earlier ones:

  • it doesn't modify the original List but returns a new one
  • the method decides what the returned List‘s implementation is, it may be different than the original

Also, we can modify our implementation to get the old behavior; we clear the original List and add the collected elements to it:

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); }

It works the same way the ones before:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

Since we don't modify the List continually, we don't have to access elements by position or shift them. Also, there're only two possible array reallocations: when we call List.clear() and List.addAll().

7. Using the Stream API

Java 8 introduced lambda expressions and stream API. With these powerful features, we can solve our problem with a very clean code:

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

This solution works the same way, like when we were collecting the remaining elements.

As a result, it has the same characteristics, and we should use it to return the result:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when List result = removeAll(list, valueToRemove); // then assertThat(result).isEqualTo(list(2, 3));

Note, that we can convert it to work like the other solutions with the same approach we did with the original ‘collecting' implementation.

8. Using removeIf

With lambdas and functional interfaces, Java 8 introduced some API extensions, too. For example, the List.removeIf() method, which implements what we saw in the last section.

It expects a Predicate, which should return true when we want to remove the element, in contrast to the previous example, where we had to return true when we wanted to keep the element:

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

It works like the other solutions above:

// given List list = list(1, 1, 2, 3); int valueToRemove = 1; // when removeAll(list, valueToRemove); // then assertThat(list).isEqualTo(list(2, 3));

事実による、というリスト自体は、このメソッドを実装して、我々は安全にそれが可能な最高のパフォーマンスを持っている、と仮定することができます。その上、このソリューションはすべての中で最もクリーンなコードを提供します。

9.結論

この記事では、間違った問題を含め、単純な問題を解決するための多くの方法を見てきました。それらを分析して、すべてのシナリオに最適なソリューションを見つけました。

いつものように、例はGitHubで入手できます。