JavaのArrayListを逆にします

投稿日: 2022-11-09 2022-11-09
タグ: Java Collections, Java List

1. 概要

ArrayList は、Javaでよく使用されるListの実装です。

このチュートリアルでは、ArrayListを逆にする方法について説明します。

2. 問題の紹介

いつものように、例を通して問題を理解しましょう。整数のリストがあるとしましょう。

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));

逆転した後、私たちは結果を期待しています：

List<Integer> EXPECTED = new ArrayList<>(Arrays.asList(7, 6, 5, 4, 3, 2, 1));

したがって、要件は非常に単純に見えます。ただし、問題にはいくつかのバリエーションがある可能性があります。

リストを元に戻す
List を反転し、結果を新しいListオブジェクトとして返します

このチュートリアルでは、両方のケースについて説明します。

Java標準ライブラリは、仕事をするためのヘルパーメソッドを提供しました。この方法を使用して問題をすばやく解決する方法を見ていきます。

さらに、私たちの一部がJavaを学習している可能性があることを考慮して、リストを逆にする2つの興味深いが効率的な実装について説明します。

次に、それらの動作を見てみましょう。

3. 標準のCollections.reverseメソッドの使用

Java標準ライブラリは、指定されたList内の要素の順序を逆にするCollections.reverseメソッドを提供しています。

この便利な方法は、インプレース反転を実行します。これにより、受信した元のリストの順序が逆になります。しかし、最初に、それを理解するための単体テストメソッドを作成しましょう。

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
Collections.reverse(aList);
assertThat(aList).isEqualTo(EXPECTED);

上記のテストを実行すると、合格します。これまで見てきたように、aListオブジェクトをreverseメソッドに渡した後、aListオブジェクトの要素の順序が逆になります。

元のListを変更せず、逆の順序で要素を含む新しい List オブジェクトを取得する予定の場合は、新しいを渡すことができます。 オブジェクトをreverseメソッドにリストします。

List<Integer> originalList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> aNewList = new ArrayList<>(originalList);
Collections.reverse(aNewList);

assertThat(aNewList).isNotEqualTo(originalList).isEqualTo(EXPECTED);

このようにして、 originalList は変更されず、aNewListの要素の順序が逆になります。

上記の2つの例からわかるように、標準の Collections.reverse メソッドは、Listを逆にするのに非常に便利です。

ただし、Javaを学習している場合は、おそらく、「逆」メソッドの実装を自分で練習したいと思います。

次に、いくつかの優れた実装を調べてみましょう。1つは再帰を使用し、もう1つは単純なループを使用します。

4. 再帰を使用してリストを逆にする

まず、 recursion 手法を使用して、独自のリスト反転メソッドを実装しましょう。まず、実装を見てみましょう。

public static <T> void reverseWithRecursion(List<T> list) {
    if (list.size() > 1) {
        T value = list.remove(0);
        reverseWithRecursion(list);
        list.add(value);
    }
}

ご覧のとおり、上記の実装はかなりコンパクトに見えます。それでは、それがどのように機能するかを理解しましょう。

再帰ロジックの停止条件は次のとおりです。 list.size（）<= 1 。つまり、リストオブジェクトが空であるか、要素が1つしかない場合は、再帰を停止します。

各再帰呼び出しで、「 T value = list.remove（0）」を実行し、リストの最初の要素をポップします。これは次のように機能します。

recursion step 0: value = null, list = (1, 2, 3, ... 7)
   |_ recursion step 1: value = 1, list = (2, 3, 4,...7)
      |_ recursion step 2: value = 2, list = (3, 4, 5, 6, 7)
         |_ recursion step 3: value = 3, list = (4, 5, 6, 7)
            |_ ...
               |_ recursion step 6: value = 6, list = (7)

ご覧のとおり、 list オブジェクトに要素が1つしかない場合（7）、再帰を停止してから、 list.add（value）を下から実行し始めます。つまり、最初にリストの最後に6を追加し、次に5を追加し、次に4を追加します。最終的に、リスト内の要素の順序が逆になりました。さらに、このメソッドは線形時間で実行されます。

次に、再帰の実装が期待どおりに機能するかどうかを確認するためのテストを作成しましょう。

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithRecursion(aList);
assertThat(aList).isEqualTo(EXPECTED);

テストを実行すると、合格します。したがって、再帰の実装によって問題が解決されます。

5. 反復を使用してリストを反転する

再帰を使用してリストを逆にしました。または、反復を使用して問題を解決することもできます。

まず、実装を見てみましょう。

public static <T> void reverseWithLoop(List<T> list) {
    for (int i = 0, j = list.size() - 1; i < j; i++) {
        list.add(i, list.remove(j));
    }
}

ご覧のとおり、反復の実装も非常に優れています。ただし、 for ループは1つだけであり、ループ本体には1つのステートメントしかありません。

次に、それがどのように機能するかを理解しましょう。

2つのポインタを定義しました。私と j 、指定されたリストにあります。ポインタjは、常にリストの最後の要素を指します。しかし、ポイントiは0から j-1。

各反復ステップで最後の要素を削除し、 list.add（i、list.remove（j））を使用してi-thの位置に入力します。 iがj-1に達すると、ループが終了し、リストが逆になります。

Iteration step 0: i = j = null, list = (1, 2, 3,...7)
Iteration step 1: i = 0; j = 6 
                  |_ list.add(0, list.remove(6))
                  |_ list = (7, 1, 2, 3, 4, 5, 6)
Iteration step 2: i = 1; j = 6 
                  |_ list.add(1, list.remove(6))
                  |_ list = (7, 6, 1, 2, 3, 4, 5)
...
Iteration step 5: i = 4; j = 6 
                  |_ list.add(4, list.remove(6))
                  |_ list = (7, 6, 5, 4, 3, 1, 2)
Iteration step 6: i = 5; j = 6 
                  |_ list.add(5, list.remove(6))
                  |_ list = (7, 6, 5, 4, 3, 2, 1)

メソッドは線形時間でも実行されます。

最後に、メソッドをテストして、期待どおりに機能するかどうかを確認しましょう。

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithLoop(aList);
assertThat(aList).isEqualTo(EXPECTED);

上記のテストを実行すると、合格です。

6. 結論

この記事では、例を通してArrayListを逆にする方法について説明しました。標準のCollections.reverseメソッドは、この問題を解決するのに非常に便利です。

ただし、独自の反転実装を作成したい場合は、2つの効率的なインプレース反転アプローチを学習しました。

いつものように、この記事の完全なコードはGitHubのにあります。

getdocs

13036