I. ArrayListの概要

1.1 ArrayListの紹介

ArrayListはよく使われるので、今日はそのソースコードを少し探ってみましょう。
出てくるなりトップに大きなコメントの羅列があり、トップのコメントで参照しているのは このブログの記事 以下のように読み取れます。

可変長配列のための List インターフェイスの実装です。オプションのリスト操作をすべて実装し、NULLを含むすべての要素を許可します。List インターフェースの実装に加えて、このクラスは、リストを格納するために内部で使用する配列のサイズを操作するためのメソッドも提供します。(このクラスは Vector クラスとほぼ同じですが、このクラスは同期ではありません)。
size, isEmpty, get, set, iterator, listIteratorの各操作はすべて固定時間で実行されます。add操作は割り当てられた固定時間、つまりn個の要素を追加するのにO(n)時間かかります。他のすべての操作は、（大まかに言えば）線形時間で実行されます。この実装は、LinkedListの実装に使われる定数係数と比較して、低い定数係数を持っています。
各ArrayListインスタンスには容量があります。この容量は、リストの要素を格納するために使用される配列のサイズです。これは常に、少なくともリストのサイズと同じです。要素がArrayListに追加されると、その容量は自動的に大きくなります。単にリストに要素を追加して固定時間のオーバーヘッドを分散させるほど単純ではないため、成長戦略の詳細は指定されていません。
大量の要素を追加する前に、アプリケーションは ensureCapacity オペレーションを使用して、ArrayList インスタンスの容量を増やすことができます。これにより、インクリメンタルな再割り当ての量を減らすことができます。
この実装は同期的ではないことに注意してください。複数のスレッドが同時に ArrayList インスタンスにアクセスし、そのうちの少なくとも 1 つがリストを構造的に変更する場合、外部同期を維持する必要があります。(構造的な変更とは、1つまたは複数の要素を追加または削除したり、基礎となる配列のサイズを明示的に変更したりする操作のことで、単に要素の値を設定することは構造的な変更ではありません)。これは通常、リストを自然にカプセル化するオブジェクトに対して同期操作を行うことで達成されます。そのようなオブジェクトが存在しない場合は、Collections.synchronizedListメソッドを使用して、リストをラップする必要があります。これは、リストへの偶発的な非同期アクセスを防止するために、作成時に行うのが最適です。
リスト list = Collections.synchronizedList(new ArrayList(...))。
このクラスの iterator と listIterator メソッドは、高速に失敗するイテレータを返します。イテレータの生成後、イテレータ自身の remove メソッドや add メソッドによってリストが構造的に変更されない限り、リストがいつでも何らかの形で変更されると ConcurrentModificationException をスローします。したがって、イテレータは、将来の不確定な時点で任意の不確定な動作をするリスクを冒すのではなく、同時並行的な変更に直面してすぐに完全に失敗することになります。
一般に、非同期の同時変更が発生するかどうかを厳密に保証することはできないため、イテレータの高速失敗の動作は保証されないことに注意してください。高速失敗イテレータは ConcurrentModificationException をスローするよう最善を尽くします。したがって、このようなイテレータの正しさを向上させるためにこの例外に依存するプログラムを書くことは間違ったアプローチです。
このクラスは、Java Collections Frameworkのメンバーです。

冒頭のコメントから、いくつかの重要な情報を得ることができます。ArrayList は List インターフェースのメンバである。 サイズ可変の配列 実装; ArrayList nullを許可する 要素で、ArrayListの 容量が自動的に大きくなる を使用すると、ArrayList は同期ではありません ArrayList の iterator と listIterator メソッドは、以下のようなイテレータを返します。 フェイルファスト の

1.2 ArrayList データ構造

の容量になります。CAPACITY; 実寸: サイズ。
ArrayListの基礎となるデータ構造は配列であり、配列要素の型はObject、すなわちあらゆる種類のデータを保持することができます。ArrayListクラスのインスタンスに対するすべての操作は、底辺の配列に基づいて行われます。

II. ArrayListのソースコード解析

2.1 ArrayListの継承構造と階層構造

public class ArrayList
 extends AbstractList

        implements List
, RandomAccess, Cloneable, java.io.

構造図はもう少し視覚的なものです。

• ArrayListです。ArrayListがジェネリックタイプをサポートすることを説明します。
• extends AbstractList : AbstractListを継承しています。 なぜ、ArrayListに直接Listを実装させるのではなく、AbstractListを先に継承してListを実装させるのですか？
  自体は、独自のメソッドのいくつかの実装では、コードがより簡潔であるように、一般的な方法でクラスの最下位レベルの継承構造上に抽出され、最初に一緒に達成するために、コードの重複を減らすことができます。だから、一般的に抽象的なクラスの上にクラスを参照してください、このの役割である必要があります。
• リストインターフェイスを実装しています。 ArrayListの親クラスであるAbstractListもListインターフェースを実装しているのに、なぜサブクラスのArrayListはそれをスルーしているのでしょうか？ コレクションの作者であるJoshは、コードを書いたときにこれが役に立つと思ったが、実際には役に立たない、しかし何も影響しないので今までそのままにしていた、と言っています。
• は RandomAccess インターフェースを実装しています。これは、ArrayList が高速な（通常は固定時間の）ランダムアクセスをサポートすることを示します。ArrayListでは、要素オブジェクトをその序数で素早く取得することができ、これは高速なランダムアクセスである。
• Cloneableインターフェイスを実装していること。このインタフェースを実装することにより、Object.Clone()メソッドを使用できるようになります。
• implements java.io.Serializable: クラスがシリアライズ機能を持っていること、クラスがシリアライズできることを示します、シリアライズとは何でしょうか？簡単に言うと、クラスからバイトストリームに転送し、さらにバイトストリームから元のクラスにも転送する機能です。

2.2 クラスの属性

// Serialized id
private static final long serialVersionUID = 8683452581122892189L;

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* Shared empty array instance used for empty instances.
* Specifies that this ArrayList returns the empty array when its capacity is 0.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* Shared empty array instance used for default sized empty instances. we
We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * the first element is added.
We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * the first element is added. When an ArrayList is first created, the amount of data within it is 0.
* It differs from EMPTY_ELEMENTDATA in that the array is returned by default, whereas EMPTY_ELEMENTDATA is returned when the user specifies a capacity of 0.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* The array buffer into which the elements of the ArrayList are stored.
* Any
* Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added.
* Holds the elements added to the ArrayList. 
* The capacity of the ArrayList is the length of the array. 
* The value DEFAULTCAPACITY_EMPTY_ELEMENTDATA expands the array to DEFAULT_CAPACITY when the first element is added to the ArrayList. 
* is marked as TRANSIENT and will not be serialized when the object is serialized.
*/
transient Object[] elementData; // non-private to simplify nested class access

/* The size of the ArrayList (the size of the array).
* The size of the ArrayList (the number of elements it contains).
* The actual size of the ArrayList (the number of elements it contains / the number of actual data) defaults to 0
* @serial
*/
private int size;
  
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in
Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit
OutOfMemoryError: Requested array size exceeds VM limit */
/**
* The maximum size assigned to arrays
* Why subtract 8?
* Because some VMs keep some header words in the array and trying to allocate this maximum storage capacity may cause the array size to be larger than the VM's limit, eventually leading to OutOfMemoryError.
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// Remark: MAX.VALUE is 0x7fffffff, which is converted to decimal is 2147483647, that is, the maximum length of the array is 2147483639.

2.3 メソッドを構築する

ArrayList には、3 つのコンストラクタ・メソッドがあります。

• ArrayList(int initialCapacity): 容量が指定された空の ArrayList を構築します。これは、初期容量の大きさをパラメータとするコンストラクタです。
  • initialCapacity が 0 より大きい場合、配列をインスタンス化し、カスタム容量サイズを elementData の初期サイズとして扱います。
  • 初期サイズが0であれば、空の配列をelementDataに代入します。
  • 初期容量が0より小さい場合、例外を投げる

   /**
     * Constructs an empty list with the specified initial capacity.
     * Constructs an empty list with the specified initial capacity.
     * @param initialCapacity the initial capacity of the list (the initialized capacity of the list)
     * @throws IllegalArgumentException if the specified initial capacity is negative
	 * Throws an exception if the specified initial capacity is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

• ArrayList()。初期サイズ10で空のリストを構築します。パラメータを渡さずにArrayListオブジェクトを作成する場合は、このパラメータレスコンストラクタを使用します。前のセクションで、DEFAULTCAPACITY_EMPTY_ELEMENTDATAは空のObject[]であり、elementDataを初期化し、これもObject[]型であることがわかりました。空のObject[]はデフォルトの容量が10になりますが、ここでは配列の容量が10に変化していないため、いつ配列が10に初期化されるのでしょうか。答えは、要素が追加されたときです（addメソッド）。最初のaddが行われたとき、elementDataはデフォルトの長さである10になります。

    /**
     * Constructs an empty list with an initial capacity of ten.
	 * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

• ArrayList(Collection<? extends E> c)。指定されたコレクションの要素を、コレクションのイテレータが返す順序で含むリストを構築する。2番目に参照されるコンストラクタは、その親であるCollectionオブジェクトの値で構築されます。
  • コレクションオブジェクトを配列に変換し、配列のアドレスをelementDataに代入します。
  • 配列の実際のサイズが0に等しい（cに要素がない）場合、空の配列EMPTY_ELEMENTDATAをelementDataに代入します。
  • sizeの値が0より大きい場合、Arrays.copyメソッドを実行して、コレクションオブジェクトの内容をelementDataにコピーする（ディープコピーと解釈できる）。

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     * Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's * iterator.
     * @param c the collection whose elements are to be placed into this list
	 * the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
	 * if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) ! = 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // The implementation of toarray() is different for each collection, so you need to determine if it is not of type Object[].class, then you need to use the method in ArrayList to transform it.
            if (elementData.getClass() ! = Object[].class)
		//copyOf(the array to be copied, the length of the copy to be returned, the class of the copy to be returned)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayListのコンストラクタは1つのことを行います。それはデータを格納するコンテナを初期化することで、それは本質的に配列であり、その中でelementDataと呼ばれています。

2.4 主なメソッド

2.4.1 get() メソッド

    /**
     * Returns the element at the specified position in this list.
     * Returns the element at the specified position in this list
     * @param index index of the element to return The index of the element to be returned.
     * @return the element at the specified position in this list
	 The element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);// out-of-bounds check
        return elementData(index);//return the element whose index is index
    }
    /**
     * Checks if the given index is in range. If not, throws an appropriate
     * This method does *not* check if the index is
     This method does * not* check if the index is * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
	 Checks if the specified index is in range. If it is not, a runtime exception is thrown.
	 This method does not check if the index is negative, it always takes precedence immediately before the array access
	 If the given index index>=size, an out-of-bounds exception is thrown
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

   /**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */private
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    // Positional Access Operations positional access operations
	// Returns the element with index index
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

コードからわかるように、ArrayListは一番下が配列なので、そのgetメソッドは非常にシンプルです。それはまず、境界外 (インデックスが 0 より小さいか、配列の実際の長さ以上である。エラーメッセージはインデックスと配列の実際の長さを返す) があるかどうかを判断し、次に配列の添え字から直接要素を取得します。

2.4.2 set() メソッド

    /**
     * Replaces the element at the specified position in this list with
     * the specified element.
     * Replaces the element at the specified position in this list with * the specified element.
     * @param index index of the element to replace The index of the element to be replaced
     * @param element element to be stored at the specified position to be stored at the specified position
     * @return the element previously at the specified position (returns the element that was replaced)
     * @throws IndexOutOfBoundsException {@inheritDoc} Throws an out-of-bounds exception if the parameter specifies index index>=size
     */
    public E set(int index, E element) {
		// Check if the index is out of bounds. If the parameter specifies the index index>=size, an out-of-bounds exception is thrown
        rangeCheck(index);
		//record the replaced element (old value)
        E oldValue = elementData(index);
		//replace element (new value)
        elementData[index] = element;
		//return the replaced element
        return oldValue;
    }

設定位置が現在の配列長（size）より小さく0より大きいことを確認し、指定位置（index）の要素を取得してoldValueストアに入れ、設定する要素を指定位置（index）に入れ、元の位置oldValueの要素をユーザに返します。

2.4.3 add() メソッド

addのメソッドには、引数が1つのものと2つのものがあります。

• boolean add(E e) メソッド

    /**
     * Appends the specified element to the end of this list.
     * Appends the specified element to the end of this list
     * @param e element to be appended to this list The element to be appended to the list
     * @return 
true
 (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
		// Confirm list capacity, if not enough, add 1. note: only add 1 to ensure resources are not wasted
        ensureCapacityInternal(size + 1); // Increments modCount!!!
        // Place element e at the position of size, and size++
        elementData[size++] = e;
        return true;
    }
	// Check the capacity of the array, and expand it if it is not enough, only for internal use in the class 
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
		// If elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA, then take minCapacity as the maximum value between DEFAULT_CAPACITY and the parameter minCapacity. DEFAULT_CAPACITY has previously been defined as the default The initialized capacity is 10.
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	// array capacity check, expand if not enough, only for internal class use 
	// minCapacity the minimum capacity wanted
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
		// minCapacity>the current length of the array buffer
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);// expand
    }

この add メソッドは、リストの末尾に要素を追加します。
サイズは配列のデータ数であり、要素を追加するため、サイズ+1、最初にこの配列のサイズ+1の数を置くことができる決定します。初期化されたelementDataは、空の配列ではない、それは空の配列の長さのサイズは0である場合、それ以外の配列の長さは0ではありません。

• elementData要素が空の場合、要素を追加する最初の時間です、minCapacity =サイズ+ 1は、実際には、1に等しい、空の配列の長さを格納することはできませんので、それは10にminCapacityされ、デフォルト容量の大きさです。これは、この時点で10になるために必要なelementData配列の最小容量は、この時点でminCapacityのsureExplicitCapacity（）メソッドは10です。この時点までしかelementData配列の容量は、少なくとも10する必要があると言うために、elementDataのサイズを変更していない。
• もしelementData配列が空でなければ、この時点で必要な最小の容量は、元の配列の長さに1を足したものになります。
• minCapacity = size+1 であることを常に念頭に置き、 ensureExplicitCapacity() メソッドでは、まずオペランドを 1 つ増やし、必要最小限のスペースと実際の配列の長さを比較します。
  • elementDataの要素が空の場合、今は10という容量が必要ですが、elementData.lengthは0なので、拡張する必要があるのです。
  • elementData 配列の要素が空でない場合、要素を追加した後に元の配列長よりも大きな容量が必要なら拡張する必要があり、そうでなければ拡張する必要はありません。

次に進みましょう。ArrayListのサイズを自動的に拡大縮小するための重要なメソッドは、以下のgrow()メソッドにあります。

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. 
	 * For the first expansion, the logic is newCapacity = oldCapacity + (oldCapacity >> 1); i.e., increase the capacity by half from the original capacity.
	 After the first expansion, if the capacity is still less than minCapacity, the capacity will be expanded to minCapacity.
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
		// Get the current capacity of the array
        int oldCapacity = elementData.length;
		// Expand the capacity. The new capacity = current capacity + current capacity/2. That is, increase the current capacity by half (1.5 times the current capacity).
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		//If the expanded capacity is still less than the desired minimum capacity
        if (newCapacity - minCapacity < 0)
			//Expand the expanded capacity to the desired minimum capacity again
            newCapacity = minCapacity;
//when elementData is empty array, length=0, then oldCapacity=0, newCapacity=0, here is the real initialization of elementData size, is 10.
		// If the expanded capacity is greater than the critical value, the large capacity allocation
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        // The new capacity size has been determined, so copy the array and change the capacity size.
        // copyof(original array, new array length)
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
	//do large capacity allocation
    private static int hugeCapacity(int minCapacity) {
		//If minCapacity<0, throw exception
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
		// allocate Integer.MAX_VALUE if the desired capacity is greater than MAX_ARRAY_SIZE, otherwise allocate MAX_ARRAY_SIZE	
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

上記のリストの末尾にデータを追加する方法を組み合わせると、元の配列が空の場合、要素を1つ追加すると配列の容量は10になり、元の配列が空でない場合、要素を追加すると容量は元の容量の1.5倍となります。拡張された容量がArrayListに割り当てられた容量よりも大きい場合、必要な容量が割り当てられた容量よりも大きいかどうかを判断し、Yesの場合はminCapacityにInteger.MAX_VALUE:2147483647を割り当て、Noの場合はMAX_ARRAY_SIZE:2147483639を使用します。
addメソッドを呼び出すと、関数呼び出しは次のように進みます。

プログラムはaddを呼び出し、拡張する必要があればgrowを呼び出し、growはhugecapacityを呼び出すかもしれません。
例1（容量拡張の場合）。

　　List
 lists = new ArrayList
();
　　lists.add(8);

リストをサイズ0に初期化し、ArrayList()コンストラクタを空のパラメータで呼び出した後、lists.add(8)メソッドを呼び出すときの手順は次のとおりです。

addメソッドの前にelementData = {}で始まり、addメソッドを呼び出すとgrowまで呼び出しが続き、最終的にelementDataのサイズが10になり、その後add関数に戻りelementData[0]に8が入っていることが分かります。
例2（拡張しない場合）。

　List
 lists = new ArrayList
(6);
　　lists.add(8);

initialCapacityを6に指定してArrayList(int)型コンストラクタを呼び出し、elementData = new Object[6], elementDataをサイズ6のオブジェクトの配列に初期化し、add(8)メソッドを呼び出したときの正確な手順は次のとおりです。

addメソッドが呼ばれる前に、elementDataはすでにサイズ6であり、拡張処理なしでその後に渡されます。

• void add(int index, E element) メソッド

    /**
     * Inserts the specified element at the specified position in this
     * Shifts the element currently at that position (if any) and
     Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices).
     * Inserts the specified element at the specified position in the list. Moves the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
     * @param index index at which the specified element is to be inserted
	 * index at which the specified element is to be inserted (the position of the element to be inserted)
     * @param element element to be inserted The element that is about to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc} if index exceeds size
     */
    public void add(int index, E element) {
		// Out of bounds check
        rangeCheckForAdd(index);
		//check list capacity, if not enough, add 1. note: only add 1 to ensure that resources are not wasted
        ensureCapacityInternal(size + 1); // Increments modCount!!!
		// Copy the array, the purpose is to insert the element at the empty index position, and shift the element after the index by one position
		// Before inserting an element, move all the elements after index back one position
		//arraycopy(original array, starting position in the source array, target array, starting position in the target data, number of array elements to be copied)
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
 		//assign the specified index position to element
        elementData[index] = element;
		//actual capacity +1
        size++;
    }
    /**
     * A version of rangeCheck used by add and addAll.
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)// The inserted position cannot be larger than size and smaller than 0, if so, an out-of-bounds exception is reported
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

指定された位置に要素を追加する、つまり挿入する。
例 インデックス2に要素eを追加し、おおよそ以下のようになります。

add(int index, E e) は、まず要素を移動し、その後挿入操作を完了する必要があります。

2.4.4 remove() メソッド

• 指定された位置の要素を削除することで、インデックスによる削除を行います。

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     Shifts any subsequent elements to the left (subtracts one from their * indices).
     * Removes the element at the specified index index in this list
	 * Shifts any subsequent elements to the left (subtracts one from their * indices).
     * @param index the index of the element to be removed the index of the element to be removed
     * @return the element that was removed from the list The element that was removed
     * @throws IndexOutOfBoundsException {@inheritDoc} throws an out-of-bounds exception if the parameter specifies index index>=size
     */
    public E remove(int index) {
		// Check if the index is out of bounds. If the parameter specifies the index index>=size, an out-of-bounds exception is thrown
        rangeCheck(index);
		// structural modification count +1
        modCount++;
		//record the element at the index
        E oldValue = elementData(index);
		// the number of elements that need to be moved left after deleting the specified element
        int numMoved = size - index - 1;
		// if there are elements that need to be moved left, move them (after moving, the deleted elements will have been covered)
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
	 	// size is subtracted by one and the element at index size - 1 is set to null. in order for GC to work, the last position must be explicitly assigned a null value
	 	elementData[--size] = null; // clear to let GC do its work
		// return the deleted element
        return oldValue;
    }

ここから、インデックスに基づいて要素を削除する手順がわかります。

1. アウトオブバウンズチェックの実行
2. 修正回数を記録する(modCountは高速失敗を検出するフラグとして使用できる。)
3. インデックスで削除する要素を探す
4. 移動するビットの数を計算する
5. 要素を移動する（実際には削除する要素を上書きする）
6. size上の位置をnullに割り当てて、gc（ガベージコレクション機構）に高速にリサイクルさせる。
7. 削除された要素を返す

• オブジェクトで削除

    /**
     * Removes the first occurrence of the specified element from this list,
     * If the list does not contain the element, it is
     * More formally, removes the element with the lowest index
     More formally, removes the element with the lowest index * 

i
 such that
     (o==null ? get(i)==null : o.equals(get(i)))

     * (if such an element exists).  Returns 
true
 if this list
     * contains the specified element (or equivalently, if this list
     * changed as a result of the call).
     * removes the first occurrence of the specified element from the list, *
if it exists. If the list does not contain the element, it will remain unchanged. More formally, delete the element with the lowest index...
     * @param o element to be removed from this list, if present
     * @return 
true
 if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
	 Private remove method that skips bounds checking and does not return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
	//arraycopy(original array, starting position in the source array, target array, starting position in the target data, number of array elements to be copied)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

すべてのオブジェクトをループして、オブジェクトのインデックス位置を取得し、fastRemoveメソッドを呼び出して削除操作を実行します。
削除する要素のインデックスを探し、そのインデックスの後の要素を1つ先に移動させ（これを行うには System.arraycooy を呼び出します）、最後の要素を null に設定します。
ここで知っておくべきことは、主に arrayList は null 値を格納することができます。 .

• removeRange(int fromIndex, int toIndex)

    /**
     * Removes from this list all of the elements whose index is between
     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
     * Shifts any succeeding elements to the left (reduces their index).
     * This call shortens the list by {@code (toIndex - fromIndex)} elements.
     * (If {@code toIndex==fromIndex}, this operation has no effect.)
     * Remove all elements from this list whose indexes lie in between, including fromIndex but not toIndex.
	 * move any subsequent elements to the left (reducing their index)
	 * This call shortens the list by the {@code (toIndex - fromIndex)} element.
	 * (This operation is invalid if {@code toIndex==fromIndex})
     * @throws IndexOutOfBoundsException if {@code fromIndex} or
     * {@code toIndex} is out of range
     * ({@code fromIndex < 0 ||
     * fromIndex >= size() ||
     * toIndex > size() ||
     * toIndex < fromIndex})
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;// the number behind the removed index
        //arraycopy(original array, starting position in the source array, target array, starting position in the target data, number of array elements to be copied)
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);// length of the new array
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

このメソッドは，fromIndex と toIndex の間のすべての要素を削除し，toIndex より後の要素を (size-toIndex) ビットだけシフトし，ガベージコレクション機構がメモリを回収できるように，左シフト後の空の要素を null にセットし，最後に新しい配列のサイズを size に代入します．
jdk11の記述方法と比較してみてください。

	protected void removeRange(int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException(
                    outOfBoundsMsg(fromIndex, toIndex));
        }
        modCount++;
        shiftTailOverGap(elementData, fromIndex, toIndex);
    }
	
	private void shiftTailOverGap(Object[] es, int lo, int hi) {
        System.arraycopy(es, hi, es, lo, size - hi);
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }

• removeAll(Collection<? > c) と removeAll(Collection<? > c) があります。

    public boolean removeAll(Collection<? > c) {
		//Remove all elements of the specified collection
        return batchRemove(c, false, 0, size);
    }
	
	public boolean retainAll(Collection<? > c) {
		// detect whether two collections have intersection
        return batchRemove(c, true, 0, size);
    }
	
	boolean batchRemove(Collection<? > c, boolean complement, final int from, final int end) {
		Objects.requireNonNull(c);//nonnull check
		final Object[] es = elementData;//original collection
		int r;
		// Optimize for initial run of survivors
		for (r = from;; r++) { //from equals 0, end equals size
			if (r == end)
				return false;
		// determine if the set c contains the current element of the original set
			if (c.contains(es[r]) ! = complement)
				//If it contains, exit the loop
				break;
		}
		int w = r++;//w equals 0
		try {
			for (Object e; r < end; r++)//r equals 1
			// determine if the set c contains the current element of the original set
				if (c.contains(e = es[r]) == complement)
					//If it contains, save it directly
					es[w++] = e;
		} catch (Throwable ex) {// if c.contains() throws an exception
			// Preserve behavioral compatibility with AbstractCollection, even if c.contains() throws.
			// Copy the remaining elements and assign all the remaining elements to the original collection
			System.arraycopy(es, r, es, w, end - r);
			// w is the length of the current set
			w += end - r;
			throw ex;
		} finally {
			modCount += end - w;
		//There are two uses here, in removeAll(), w has been 0, it is directly the same as clear, all null. //retainAll(): there is no one intersection return true, there is an intersection but not all intersection also return true, and when two collections are equal, return false, so you can not confirm whether the two collections have an intersection based on the return value. If there are still elements in the original set, it means there is an intersection, and there are no elements in the meta set, which means there is no intersection between the two sets.	
			shiftTailOverGap(es, w, end);
		}
		return true;
    }
	
	public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
	
	public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
		//start is 0 at the beginning, end is equal to size
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }
	// The core operation for removing elements 
	private void shiftTailOverGap(Object[] es, int lo, int hi) {
		//arraycopy(original array, starting position in the source array, target array, starting position in the target data, number of array elements to be copied)
        System.arraycopy(es, hi, es, lo, size - hi);
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }

1. boolean retainAll(Collection<? > c)
このコレクションの要素のうち、指定されたコレクションにも含まれるものだけを保持する（オプションの操作）。言い換えれば、指定されたコレクションに含まれていないこのコレクションのすべての要素を削除します。
2. list.retainAll(list2)を実行します。
(1) list=list2である場合、すなわち2つのセットの要素が全く同じである場合、 戻り値はfalseとなります。
(2) list が list2 に含まれる場合 戻り値は false です。
(3) その他 返り値は真である。
理解できる。集合Aと集合Bが同一の集合である場合にもfalseが返されます．
このメソッドは、セットAのサイズが変化した場合はTrueを、サイズが変化していない場合はFalseを返し、セットのサイズを判定することで交差があるかどうかを判断しています。このメソッドが返すTrueとFalseではわかりません。
3. 実はこの方法は、集合listの要素がすべて集合list2にあれば、listの要素は削除されず、1つでもlist2になければ、削除されるということです。
つまり、listは戻り値trueでremove操作を行い、その逆で戻り値falseでremove操作を行う。

2.4.5 indexOf()メソッドとlastIndexOf()メソッド

	 // Returns the index of the first occurrence of the specified element in this list, or -1 if the list does not contain that element.
    public int indexOf(Object o) {
        if (o == null) { // The found element is null
            for (int i = 0; i < size; i++) // traverse the array, find the first empty element, return the subscript
                if (elementData[i]==null)
                    return i;
        } else { // find an element that is not null
            for (int i = 0; i < size; i++) // iterate through the array, find the first element equal to the specified element, return the subscript
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
	 // Return the index of the last occurrence of the specified element in this list, or -1 if the list does not contain the element.
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

   /**
     * Removes all of the elements from this list.
     The list will * be empty after this call returns.
	 Removes all of the elements from this list. The list will * be empty after this call returns.
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

2.4.6 clear() メソッド

   /**
     * Removes all of the elements from this list.
     The list will * be empty after this call returns.
	 Removes all of the elements from this list. The list will * be empty after this call returns.
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

III. 概要

1) arrayListはnullを格納できる。
2) arrayListは本質的にelementDataの配列である。
3) arrayListは、サイズを自動的に拡大縮小する機能を備えている点で配列と区別され、その主要なメソッドがgorw()メソッドである。
4) arrayListにおけるremoveAll(collection c)とclear()の違いは、removeAllは一括で指定した要素を削除するのに対し、clearはコレクション内の要素を削除することに終始する。
5) arrayListはもともと配列なので、データの問い合わせは非常に高速にできますが、これらを挿入したり削除したりする際には、パフォーマンスが大きく低下し、目的の効果を得るために動かすべきデータも多くなってしまうのです。
6) arrayListはRandomAccessを実装しているので、トラバースするときはforループを使用することをお勧めします。