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

は違法になります。そのため、

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

が変更されるまでの削除


  • List.remove(E element)

    ** はまだ言及していない機能を持っています:それは

    boolean

    値を返します。


List.remove(int index)

はvoidを返すことに注意してください。指定されたインデックスが有効であれば、

List

は常にそれを削除します。それ以外の場合は、

IndexOutOfBoundsException

がスローされます。

これにより、

List

が変更されるまで削除を実行できます。

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

    を返します。


List

、すべての後続要素を小さいインデックスにシフト

そのため、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

を使用して要素を通過します。

ただし、


List

を変更すると、

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

このようにして、

Iterator



List

** の状態を追跡できます(それが変更を加えるためです)。その結果、上記のコードは期待通りに動作します。

----//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

を作成して、保持したいアイテムを収集することができます。

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を使用すると、この実装はうまく機能します。

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

  • 元の

    List

    は変更されませんが、

    新しい

    が返されます


  • このメソッドは、返された

    List

    の実装が何であるかを判断します。

元のものとは異なる場合があります

また、実装を変更して** 古い動作を取得することもできます。元の

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

は継続的に変更されないので、位置によって要素にアクセスしたり要素を移動したりする必要はありません。また、配列の再割り当ては2つしかありません:

List.clear()



List.addAll()

を呼び出す場合。

7. Stream 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()

メソッドは、最後のセクションで見たものを実装しています

要素を削除したいときは**

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


List

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

9.まとめ

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

いつものように、例はhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[over on GitHub]から入手できます。