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

1. 序章

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

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

読みやすくするために、テストではカスタム 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は不正になります。したがって、例外が発生します。

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

値を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));

コードがどのように機能するかを段階的に分析してみましょう。

i = 0
- elementとlist.get（i）はどちらも3行目で 1 と等しいため、Javaはifステートメントの本体に入ります。、
- インデックス0の要素を削除します。
- したがって、 list には、 1 、 2 、および3が含まれるようになりました。
i = 1
- list.get（i）は 2 を返します。これは、リストから要素を削除すると、後続のすべての要素がより小さなインデックスにシフトするためです

したがって、 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++;
        }
    }
}

後者では、2行目のステートメント i++を削除したことに注意してください。

どちらのソリューションも期待どおりに機能します。

// 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 のインデックスで要素にアクセスするということは、インデックスが見つかるまで要素を1つずつトラバースすることを意味します。

4. for-eachループの使用

Java 5以降、for-eachループを使用してListを反復処理できます。これを使用して要素を削除しましょう。

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を使用して要素をトラバースします。でも、リストを変更すると、イテレータは一貫性のない状態になります。したがって、ConcurrentModificationExceptionをスローします。

教訓は次のとおりです。for-eachループでその要素にアクセスしている間は、Listを変更しないでください。

5. イテレータの使用

Iterator を直接使用して、Listをトラバースおよび変更できます。

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

毎回リストクラスは独自のものを提供できますイテレータ実装、私たちは安全に仮定することができます、可能な限り最も効率的な方法で要素のトラバースと削除を実装します。

ただし、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));

現在反復しているListを変更しないため、for-eachループを使用できることに注意してください。

削除がないため、要素をシフトする必要はありません。したがって、この実装は、ArrayList。を使用するとうまく機能します。

この実装は、以前の実装とはいくつかの点で異なる動作をします。

元のリストは変更されませんが、は新しいリストを返します
メソッドは、返されるリストの実装が何であるかを決定します、元のリストとは異なる場合があります

また、実装を変更して古い動作を取得することもできます。元のリストをクリアし、収集した要素をそれに追加します。

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

リストを継続的に変更しないため、位置によって要素にアクセスしたり、要素をシフトしたりする必要はありません。また、可能な配列の再割り当ては2つだけです。 List.clear（）と List.addAll（）を呼び出す場合です。

7. StreamAPIの使用

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を使用する

ラムダと機能インターフェースを使用して、Java8はいくつかの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));