ArrayListクラスの詳細分析【前編】

この記事では、コレクション フレームワークの ArrayList クラスについて詳しく説明します。このクラスは、通常の配列に基づいているため、おそらく最も理解しやすいでしょう。面接ではほぼ確実に、このクラスとその Java での実装について質問されるでしょう。2 番目の部分では、残りのメソッドを分析し、数値の動的配列の独自の実装を作成します。ArrayList クラスは AbstractList クラスを継承し、List、RandomAccess、Cloneable、Serializable のインターフェイスを実装します。 ArrayList クラスの詳細な分析 [パート 2] ArrayList クラスは、必要に応じて拡張できる動的配列をサポートします。その必要性と有効性は、通常の配列が固定長であるという事実によって説明されます。配列は一度作成されると拡大したり縮小したりすることができないため、どの程度の大きさの配列が必要になるかが不明な場合には制限が課せられます。基本的に、ArrayList クラスはオブジェクト参照の可変長リスト配列です。内部配列から要素が削除されても、内部配列のサイズ (セルの数) は自動的に減少しないことを理解することが重要です。実際、size配列内に実際に存在する要素の数を示す変数 の値は減少します。ArrayList クラスの新しいオブジェクトを作成し、それに 5 つの要素を追加するとします。デフォルトでは、10 要素の配列が作成されます。この場合、オブジェクトのいわゆる容量 (サイズ/ボリューム) は 10 になりますが、変数の値はsize5 になります。また、要素を削除すると、 ArrayList クラスの内部配列にアクセスしてその長さを調べることができないsizeため、変数の値が変化することがわかります。サイズは、以下で説明する.length追加の方法を使用して縮小できます。trimToSize()クラスフィールドを見てみましょう。

• 動的配列のデフォルトのボリュームを担当するフィールド:

  private static final int DEFAULT_CAPACITY = 10

  新しいオブジェクト new ArrayList<>() (パラメーターなしのコンストラクター) を作成すると、内部に 10 個の要素の配列が作成されます。

• コレクションのすべての要素が格納されるフィールド:

  transient Object[] elementData

  キーワードでマークtransient- 標準のシリアル化アルゴリズムを使用する場合、フィールドはバイト ストリームに書き込まれません。フィールドがキーワードでマークされていないことに注意してくださいprivate。ただし、これは、ネストされたクラス (SubList など) からこのフィールドにアクセスしやすくするために行われています。

• 実際に配列内の要素の数を格納するカウンター フィールド:

  private int size

  挿入や削除などの操作を行うと、値が増減します。

クラスにはさらに 3 つのフィールドがありますが、基本的には追加的なものであるため、考慮する必要はありません。このクラスには 3 つのコンストラクターがあります。

1. public ArrayList()– 10 個の要素からなる空のリスト配列を作成します。
2. public ArrayList(Collection < ? extends E > c)– 渡されたコレクションの要素で初期化されたリスト配列を作成します (何らかのコレクションに基づいて新しい ArrayList を作成する場合)。
3. public ArrayList(int initialCapacity)– 初期容量を持つリスト配列を作成します。渡されたパラメータinitialCapacityが0より大きい場合、指定されたサイズの配列が作成されます(内部フィールドelementDataには、サイズinitialCapacityのObject型の新しい配列へのリンクが割り当てられます)。パラメーターが 0 の場合、空の配列が作成されます。指定されたパラメータが 0 未満の場合、IllegalArgumentException がスローされます。

オブジェクトの作成

List < String> list = new ArrayList<>();

新しく作成されたオブジェクトには、listプロパティ (フィールド)elementDataと が含まれていますsize。この例では、値ストアはelementData特定の型 (generic – で指定) の配列にすぎません。パラメーターのないコンストラクターが呼び出された場合、デフォルトで Object 型の 10 個の要素の配列が作成されます (もちろん、型へのキャストが行われます)。 要素の追加 リスト配列への要素の追加は古典的に、 のオーバーロードされたバリアントを使用して行われます。 <>String[]add()

public boolean add(E элемент)

さて、追加しましょう: list.add("0"); このメソッド内では、メソッドのオーバーロードされたバージョンがadd()呼び出され、 としてマークprivateされます。このメソッドは、追加される要素、内部配列、およびそのサイズという 3 つのパラメーターを入力として受け取ります。プライベート メソッドでは、チェックが行われます。渡されたサイズ パラメーターが内部配列の長さに等しい (つまり、配列がいっぱいである) 場合、配列にはメソッドの結果grow(int minCapacity)(フィールドの現在の値)が割り当てられます。追加される要素を考慮する必要があるため、サイズ + 1 がメソッドに渡されます)。この中で、配列の内部には、元の配列の要素をコピーして取得された、新しく作成された配列へのリンクが割り当てられます。

Arrays.copyOf(elementData, newCapacity(minCapacity))

メソッドの 2 番目のパラメーターとして、新しい配列サイズが計算されるcopyOfメソッドの結果を示します。newCapacity(int minCapacity)これは次の式を使用して計算されます。 int newCapacity = oldCapacity + (oldCapacity >> 1) デフォルト サイズの配列の場合、次のことが当てはまります: >> 1– ビット単位で 1 ずつ右にシフトします (数値を半分に減らす演算子)。本質的に、これは 2 の 1 乗を意味します。10 を 2 で割って、10 を加算することがわかります。合計すると、配列の新しい容量は 15 ですが、11 番目の要素を追加しているため、15 + 1 となります。 = 16. リストに戻り、すでに 10 個の要素を追加していると仮定して、11 個の要素を追加してみます。チェックにより、配列内にスペースがないことがわかります。したがって、新しい配列が作成されて呼び出されArrays.copyOf、内部でシステム メソッドが使用されますSystem.arraycopy()。 または、JavaRush に関する記事からの明確な例を次に示します。 これらのチェックをすべて行って、必要に応じて配列のサイズを増やした後、プライベート メソッドでadd()新しい要素が配列の末尾に追加され、現在のパラメーターがsize1 つ増加します。 。古い配列はその後、ガベージ コレクターによって処理されます。これが動的配列の仕組みです。要素を追加するときに、そこにまだ空きがあるかどうかを確認します。スペースがある場合は、要素を配列の末尾に追加するだけです。末尾は配列内の最後のセルを意味するのではなく、 value に対応するセルを意味しますsize。最初の要素を配列に追加しました。この要素はインデックス [0] のセルに配置されます。フィールド値はsize1 つ増加し、= 1 となります。次の要素を追加します。これに応じてsize = 1、要素をインデックス [1] のセルに配置します。このメソッドには 2 つのパラメーターを備えたオーバーロードされたバージョンがあります。

public void add(int index, E element)

要素を追加するセルの位置 (インデックス) を指定できます。まず、指定されたインデックス値が正しいかどうかがチェックされます。これは、間違ったインデックスが指定され、何もないセル、または単に存在しないセルを指す可能性があるためです。インデックスのチェック: index > size || index < 0– 指定されたインデックスが配列の現在のサイズより大きいか、0 より小さい場合、例外がスローされますIndexOutOfBoundsException。次に、必要に応じて、上記の例と同様に、配列のサイズが増加します。おそらく、配列の追加/削除操作中に、何かがどこか (右または左) にシフトされるという話を聞いたことがあるでしょう。したがって、シフトは配列をコピーすることによって実行されます。 System.arraycopy(elementData, index, elementData, index + 1, s - index); 指定されたインデックスの右側にあるすべての要素が 1 つ右にシフトされます (インデックス + 1)。その後のみ、新しい要素が内部配列の指定されたインデックスに追加されます。配列の一部を右に 1 つシフトしたので (新しい配列は作成されません)、必要なセルは書き込み用に空きます。古い配列へのリンクは消去され、将来的にはガベージ コレクターによって引き継がれます。すでに占有されているセル [3] に「maserati」を貼り付けます。 したがって、要素がインデックスに挿入され、配列に空きスペースがない場合、呼び出しはSystem.arraycopy()2 回発生します。1 回目は でgrow()、2 回目はメソッド自体でadd(index, value)、これは明らかに加算操作全体の速度に影響します。その結果、別の要素を内部配列に書き込む必要があるが、そこにスペースがない場合、ArrayList 内で次のことが起こります。

• 新しい配列は、元の配列の 1.5 倍のサイズと 1 つの要素を加えて作成されます。
• 古い配列のすべての要素が新しい配列にコピーされます
• 新しい配列は ArrayList オブジェクトの内部変数に格納され、古い配列はガベージとして宣言されます。

ArrayList タイプのオブジェクトの容量は、次の方法を使用して手動で増やすことができます。

public void ensureCapacity(int minCapacity)

アレイの容量を事前に増やすことで、後で RAM を追加で再配分することを回避できます。このメソッドは、 に渡される要素の数に合わせて内部配列のサイズを増やしますminCapacity。このメソッドはensureCapacity()フィールドには影響しませんが、内部配列 (のサイズ)sizeに影響します。両方が異なるものであり、混同しないことが非常に重要であることcapacityをもう一度強調します。ArrayList の構築元となる基になる配列のサイズを、実際に格納されている現在の要素数まで縮小したい場合は、 を呼び出す必要があります。コレクションから要素を削除すると、実際に存在する要素の数が表示され、減少しません。100 個の要素を入力し、最初の 50 個を削除すると、要素は 50 になり、100 のままになります。 と を減らすには、全体の容量を現在のサイズに調整するメソッドを使用する必要があります。どのようにフィットしますか? 空のセルが残らないように配列をコピーします (新しい配列の長さは単に size フィールドと等しくなります)。 sizecapacitytrimToSize()size()capacitysizecapacitycapacitytrimToSize() を使用してコレクションに要素を追加することもできますaddAll。

public boolean addAll(Collection< ? extends E> c)
public boolean addAll(int index, Collection< ? extends E> collection);

最初のオプションでは、メソッド パラメーターで指定されたコレクション (別のシートなど) のすべての要素を、メソッド呼び出しが行われた元のコレクション (最後に挿入) に追加できます。渡されたコレクション (セットの場合もあります) は、 を使用して配列に変換されますtoArray()。当然、追加操作もコピーを用いて行われる。2 つ目は、collectionインデックスから始まるすべての要素をリストに追加することですindex。この場合、すべての要素はリスト内の要素の数だけ右にシフトしますcollection。要素の削除 まず、ArrayList から要素を削除するための従来のオプションを見てみましょう。

public E remove(int index)

インデックスによる削除を実行し、後続の (指定されたインデックスの要素の後) 要素をすべて左にシフトして、「穴」を閉じます。また、削除された要素 (E) も返します。この要素は、削除前に追加の変数に書き込まれており、その値はメソッド呼び出しの結果として取得されます。E が何であるかを理解するには、いわゆるジェネリック型についてよく知る必要があります。E という表記は、メソッドが ArrayList オブジェクトの作成時に指定されたデータ型を返すことを示します (覚えておいてください。List <String> listしたがって、この場合、 E は「置換」されますString)。一般的な理解のために、ジェネリック型についてよく理解しておくことを強くお勧めします。入力されたインデックスの正確性がチェックされ、メソッド内で要素は完全に削除されませんが、プライベート メソッドが呼び出されfastRemove(Object[] es, int i)、削除がすでに行われます。配列と指定されたインデックスを入力としてメソッドに渡します。要素は を使用してコピーされSystem.arraycopy()、配列のサイズが縮小されてから、最後の要素に null を割り当てます。新しい配列が作成されないことに注意してください。 System.arraycopy(es, i + 1, es, i, size - 1 - i); 指定されたインデックス (i+1) の下の位置の右側にある部分が元の配列 (es) にコピーされ、その位置から開始して配置されます。 (i) 削除対象の要素が配置されていた場所。したがって、左へのシフトを実行して要素を消去しました。 以下の配列からインデックス 3 の要素を削除してみます。 このメソッドの 2 番目のバージョンを考えてみましょう。

public boolean remove(Object o)

このメソッドは、渡された要素を list から削除しますo。より正確には、指定されたリンクにあるオブジェクトを削除します。リストに要素が存在する場合、その要素は削除され、すべての要素が左にシフトされます。要素がリストに存在し、正常に削除された場合、メソッドは true を返し、それ以外の場合は false を返します。インデックスによる削除のオプションと同様に、このメソッドは と呼ばれfastRemove()、まったく同じアクションが発生します。違いは、メソッドがObject クラスのremove(Object o)メソッドを通じて目的のオブジェクトをさらに検索することです。equals()値によって削除する場合、ループは一致が見つかるまでリストのすべての要素を調べます。最初に見つかった要素のみが削除されます。要約しましょう: 動的配列から要素を削除する場合、通常の配列のように穴は残りません (削除されたセルは空になりません)。後続の要素 (インデックスの右側にある要素) はすべて、1 つ左にシフトされます。さまざまな程度でリストから要素を削除するために使用できる追加のメソッドがいくつかあります。それらを簡単に見てみましょう。コレクションの整理:

public void clear()

単純なループは、for配列のすべての要素を反復処理し、各要素に null を割り当てます。次のように、別の転送されたコレクションに含まれる要素をコレクションから削除できます。

public boolean removeAll(Collection< ?> c)

複数の要素を削除する必要がある場合は、おそらく条件ループ内で削除するべきではありません。 メソッドを使用する方が便利で安全ですremoveAll()。リストから削除される要素のコレクションを受け入れます。コレクションには、ターゲット リストに格納されているものと同じタイプの要素が含まれている必要があります。それ以外の場合は廃棄されますClassCastException。メソッド呼び出しの結果としてリストが変更された場合、メソッドは true を返します。 渡されたコレクションに属さない要素を削除します。

public boolean retainAll(Collection< ?> c)

コレクションがあるとします。

List< String> listFirst = new ArrayList<>();
listFirst.add("White");
listFirst.add("Black");
listFirst.add("Red");

そして2番目:

List< String> listSecond = new ArrayList<>();
listSecond.add("Green");
listSecond.add("Red");
listSecond.add("White");

その後、listSecond.retainAll(listFirst)in の後には次のlistSecondように残ります。

"White"
"Red"

「Green」が削除されたため、 にはありませんlistFirst。しかし、その後はlistSecond.removeAll(listFirst)次のようlistSecondになります。

"Green"
Удалorсь все элементы, которые есть в listFirst.

渡されたコレクションに属さない - 渡されたコレクションにない要素がある場合、(メソッドが適用される) 最初のコレクションから要素を削除する必要があることを意味します。転送されたコレクションに属します。したがって、最初と 2 番目の (転送された) コレクションの両方に要素が存在する場合、最初のコレクションの重複は破棄されます。

protected void removeRange(int fromIndex, int toIndex)

指定された開始インデックス (両端を含む) と指定された終了インデックス (両端を含まない) の間にあるすべての要素をリストから削除します。このメソッドは ArrayList オブジェクト上で直接呼び出すことができないことに注意してください。これを使用するには、 から継承する必要がありますAbstractList/ArrayList。このメソッドは別のメソッド (subList、後述) によっても使用されます。

public boolean removeIf(Predicate< ? super E> filter)

指定された述語に基づいてコレクションから要素を削除します。述語自体は、特定の関数/アルゴリズム/条件に基づいて、特定の条件に対応する 1 つ以上の要素が削除されます。Predicate— 関数型インターフェイス (メソッドが 1 つだけ含まれているため、ラムダとして使用できます)、「1 つのパラメーターを受け取り、ブール値を返す」という原則に基づいて機能します。基本的に、このメソッドはインターフェイスからの実装をオーバーライドしCollection、次の「戦略」を実装します。要素をループして、Predicate; に一致する要素をマークします。次に、最初の反復でマークされた要素を削除 (およびシフト) するために 2 回目の実行が実行されます。Predicate2 つのオブジェクトが等しい場合に true を返す インターフェイスを実装してみましょう。

class SamplePredicate< T> implements Predicate< T>{
  T varc1;
  public boolean test(T varc){
     if(varc1.equals(varc)){
       return true;
  }
  return false;
  }
}

別のクラスで、 から ArrayList を作成しString、 を実装するクラスのオブジェクトを作成しましょうPredicate。

ArrayList< String> color_list = new ArrayList<> ();
SamplePredicate< String> filter = new SamplePredicate<> ();

varc1値「White」を 変数に書き込んでみましょう。

filter.varc1 = "White";

リストに数行を追加してみましょう。

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

list に対してメソッドを実行しましょうremoveIf。このメソッドに条件付きのオブジェクトを渡します。

color_list.removeIf(filter);

その結果、「述語」がそれらの行が等しいかどうかを比較するため、値「White」を持つすべての行がリストから削除されます。最終リスト: [黒、赤、黄]。 要素の置き換え

public E set(int index, E element)

指定された位置にある要素を、index渡された要素に置き換えますelement。また、インデックスは 0 より大きく、最後の要素のインデックスより小さい必要があります。そうでない場合は、例外がスローされますIndexOutOfBoundsException。内部配列のコピーは発生しません。単純に、指定されたインデックスの要素の代わりに、新しい要素が挿入されます。値を上書きします。

public void replaceAll(UnaryOperator<e> operator)

コレクションのすべての要素を変更します (条件付きで可能)。ほとんどの場合、インターフェイスを実装してそのメソッドを定義するラムダまたは匿名クラスと組み合わせて使用​​されます(ただし、わかりやすくするために、この例では単にインターフェイスを実装するクラスを使用します) UnaryOperator。インターフェースを実装してみましょう。

class MyOperator< T> implements UnaryOperator< T>{
   T varc1;
   public T apply(T varc){
     return varc1;
  }
}

別のクラスで、 から ArrayList を作成しString、 を実装するクラスのオブジェクトを作成しましょうUnaryOperator。

ArrayList< String> color_list = new ArrayList<> ();
MyOperator< String> operator = new MyOperator<> ();

varc1値「White」を 変数に書き込んでみましょう。

operator.varc1 = "White";

リストに数行を追加してみましょう。

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

replaceAllオブジェクトを渡す リストに対してメソッドを実行しましょうoperator。

color_list.replaceAll(operator);

その結果、リスト内のすべての値が「白」に置き換えられました: [白、白、白、白、白、白]。たとえば、次のようにして、コレクション内の文字列からすべてのスペースを削除できます。

ArrayList< String> list = new ArrayList<>(Arrays.asList("A   ", "  B  ", "C"));
list.replaceAll(String::trim);

その他の方法: 次のメソッドを使用して、ArrayList リスト配列を通常の配列に変換できます。

public Object[] toArray()

または

public < T> T[] toArray(T[] a)

- ここでは、返される配列の型が決定されますruntime 。このメソッドでは次のことが可能になります。

1. 一部の操作を高速化します。
2. コレクションを直接受け入れるためにオーバーロードされていないメソッドに配列をパラメーターとして渡します。
3. 新しいコレクションベースのコードとコレクションを認識しない従来のコードを統合します。

配列のコピー オブジェクトを返します。

public Object clone()

このメソッドはclone()オブジェクト型を返すため、メソッドを呼び出した後、必要なクラスにキャストする必要があることに注意してください。クローンを作成すると、新しい独立したオブジェクトが作成されます。コレクションにオブジェクトが存在するかどうかを確認します。

public boolean contains(Object o)

リスト内のオブジェクトの存在を確認し (内部的に Object クラスの equals メソッドを使用、つまり参照を比較します)、結果に応じて true/false を返します。通常のループに加えて、以下を使用してコレクションを反復処理する (各要素にアクセスし、アクションを実行する) ことができます。

public void forEach(Consumer< ? super E> action)

リストを表示するには次のようにします。

List< Integer> numbers = new ArrayList<>(Arrays.asList(10, 20, 50, 100, -5));
numbers.forEach((number)-> System.out.println(number));

ラムダを使用しない場合は、匿名クラスを使用してacceptインターフェイスメソッドをオーバーライドする必要がありますConsumer。

numbers.forEach(new Consumer< Integer>() {
  @Override
   public void accept(Integer integer) {
      System.out.println(integer);
          }
});

インデックスによって要素を取得します。

public E get(int index)

コレクション要素へのランダム アクセスに使用されます。リスト内の指定されたインデックスにある要素を返します。index < 0または がindex >=リスト内の要素の最大数である場合、例外がスローされますIndexOutOfBoundsException。これはリストから要素を取得する基本的な方法であり、特定の配列セルにアクセスするため、インデックスによって要素を取得する時間は ArrayList のサイズに関係なく常に同じになります。指定されたオブジェクトのインデックスを検索します。

public int indexOf(Object o);
public int lastIndexOf(Object o);

これらのメソッドは、リスト内の最初の要素 (指定されたオブジェクトが最初に検出されたとき) または最後に出現した要素 (指定されたオブジェクトが最後に検出されたとき) のインデックスを返します。要素がリストに存在しない場合、メソッドは -1 を返します。 コレクションの要素を確認します。

public boolean isEmpty();

このメソッドは、リストが空の場合 (フィールドが等しいかどうかを調べますsize 0)、 true を返し、それ以外の場合は false を返します。リストに null 要素のみが含まれている場合、メソッドは false を返します。つまり、このメソッドでは null 要素も考慮されます。リスト内の要素の数を確認します。

public int size();

リスト内の要素の数 (サイズ フィールドの値) を返します。要素数はリストの容量(capacity)と異なる場合があります。リストのイテレータを取得します。

public Iterator< E> iterator();

後でループまたはその他の処理で使用できるように、リストのイテレータを返します。イテレータはフェイルファスト動作を実装します。コレクションを実行して、コレクションへの変更 (イテレーター メソッドを使用して取得されたものではない) に気付いた場合、すぐに例外をスローしますConcurrentModificationException。イテレータには と呼ばれるものがありますmodification count。イテレータは、各 の後でコレクションを反復処理するときにnext/hasNext/remove、このカウンタをチェックします。イテレータが予期した内容と一致しない場合は、例外がスローされます。ここではイテレータについては詳しく説明しません。

public ListIterator< E> listIterator() и public ListIterator< E> listIterator(int index)

後でループまたはその他の処理で使用できるように、リストのリスト反復子を返します。このインターフェイスは、リストの双方向のトラバースとその要素の変更のためにListIteratorインターフェイスを拡張します。Iteratorオーバーロードされたバージョンでは、「トラバーサル」が開始されるインデックスを渡すことができます。この場合のインデックスは、メソッドが作業を開始する最初の要素を示しnext()、メソッドが呼び出されると、previous()「渡されたインデックス - 1」というインデックスの下の要素から走査が開始されます。

public Spliterator <E> spliterator()

Java 8 では、デリミタ反復子と呼ばれる新しいタイプの遅延バインディングおよびフェイルファスト反復子が導入されています。区切り反復子を使用すると、一連の要素を反復処理できますが、使用方法は異なります。Spliteratorインターフェイスの最も重要な機能は、一連の要素の個々の部分の並列反復、つまり並列プログラミングをサポートする機能です。