Java ArayListはどうしてRandom Accessインターフェースを実現しますか？

私たちの開発では、Listインターフェースは最も一般的ですが、毎日のようにArayListやLinkdListを使っています。しかし、慎重な学生はRandomAccessインターフェースを実現しています。Linked ListはRandom Accessインターフェースを実現していません。これは何ですか？

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

RandomAccessインターフェースの中では空いていますが、RandomAccessインターフェースは何ですか？

public interface RandomAccess {
}

Random Accessインターフェース
RandomAccessは、Listがこのインターフェースを実現すれば、高速ランダムアクセスがサポートされるというマークインターフェースです。ランダムアクセスとは何ですか？次に例を挙げて説明します。Collectionは集合の道具類です。Collectionのソースコードの中の2つの検索方法を見てみます。

public static 
    int binarySearch(List extends Comparable super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()

ソースでは、listがRandomAccessの例かどうかを判断することができますが、もしそうであれば、indexedvinarySearchの方法を実行します。そうでなければ、iteratoBinarySearchの方法を実行します。この二つの方法を見てみます。

private static 
int indexedBinarySearch(List extends Comparable super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable super T> midVal = list.get(mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}
private static 
int iteratorBinarySearch(List extends Comparable super T>> list, T key)
{
    int low = 0;
    int high = list.size()-1;
    ListIterator extends Comparable super T>> i = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable super T> midVal = get(i, mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

上記の2つの方法のソースコードは、RandomAccessインターフェースのListはインデックスを使用して遍歴していますが、RandomAccessインターフェースを実現していないListは、ローズマリーを使用して遍歴しています。なぜこのように設計しますか？二分検索のエルゴード操作に関わる以上、ArayListとLinked Listエルゴードの性能を分析してみましょう。

public class CollectionTest {
    public static void main(String[] args){
        long arrayListIndexedTime = arrayListIndexed();
        long arrayListIteratorTime = arrayListIterator();
        long linkedListIndexedTime = linkedListIndexed();
        long linkedListIteratorTime = linkedListIterator();
        System.out.println("  ArrayList  for       ：" + arrayListIndexedTime);
        System.out.println("  ArrayList  iterator       ：" + arrayListIteratorTime);
        System.out.println("  LinkedList  for       ：" + linkedListIndexedTime);
        System.out.println("  LinkedList  iterator       ：" + linkedListIteratorTime);
    }

    //  ArrayList  for       
    public static long arrayListIndexed() {
        List arrayList = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            arrayList.add(i);
        }
        //      
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < arrayList.size(); i++) {
            arrayList.get(i);
        }
        //      
        long endTime = System.currentTimeMillis();
        //      
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //  ArrayList  iterator       
    public static long arrayListIterator() {
        List arrayList = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            arrayList.add(i);
        }
        //      
        long startTime = System.currentTimeMillis();
        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        //      
        long endTime = System.currentTimeMillis();
        //      
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //  LinkedList  for       
    public static long linkedListIndexed() {
        List linkedList = new LinkedList<>();
        for (int i = 0; i < 10000; i++) {
            linkedList.add(i);
        }
        //      
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.get(i);
        }
        //      
        long endTime = System.currentTimeMillis();
        //      
        long resultTime = endTime - startTime;
        return resultTime;
    }

    //  LinkedList  iterator       
    public static long linkedListIterator() {
        List linkedList = new LinkedList<>();
        for (int i = 0; i < 10000; i++) {
            linkedList.add(i);
        }
        //      
        long startTime = System.currentTimeMillis();
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        //      
        long endTime = System.currentTimeMillis();
        //      
        long resultTime = endTime - startTime;
        return resultTime;
    }
}

テストの結果は以下の通りです

  ArrayList  for       ：1
  ArrayList  iterator       ：2
  LinkedList  for       ：47
  LinkedList  iterator       ：1

テスト結果を分析します。arrayListはforエルゴードを通過するのはiteratorを通過するより少し早いです。Linked Listはiteratorを通過するのがforエルゴードより速いです。
したがって、我々のアプリケーションでは、Listインターフェースを使用するどのような実装クラスを考慮すると、より効率的にシーンニーズを満たすことができます。そこでここではRandomAccessインターフェースを実現することによって、Listのどの実現クラスを区別しますか？
締め括りをつける
＊最後の要約文：RandomAccessインターフェースを実現するListは、forループを通じてデータを巡回することができ、iteratorエルゴードデータを使用するよりも効率的に、RandomAccessインターフェースを実現していないListは、iteratorエルゴードデータを経由してforループを使用するよりもデータを遍歴することができます。