Listインタフェースの2つの実装の違い

今日は暇で、Javaの知识を勉强して、突然リストを思い出しました.
実際には2つのリストがあります.1つは基本的なArrayListで、その利点はランダムアクセス要素であり、もう1つはより強力なLinkedListであり、高速ランダムアクセスのために設計されたのではなく、より一般的な方法を持っていることです.
List:順序はListの最も重要な特徴である:それはメンテナンス要素の特定の順序を保証する.ListはCollectionに多くの方法を追加し、リストの間に要素を挿入して削除することができる(これはLinkedListのみが使用することを推奨する.)1つのListはListIteratorを生成することができ、それを使用して2つの方向からListを遍歴することができ、リストの間から要素を挿入および除去することができる.
ArrayList:配列により実現されるList.エレメントへの迅速なランダムアクセスは可能ですが、リストの間にエレメントを挿入して削除する速度は遅いです.ListIteratorは、エレメントを挿入および削除するのではなく、ArrayListを後方から前方に巡回するためにのみ使用されます.それはLinkedListよりもオーバーヘッドが大きいからです.
LinkedList:シーケンスアクセスを最適化しており,リストへの挿入と削除のオーバーヘッドは大きくない.ランダムアクセスは相対的に遅い.(ArrayListで代用します.)LinkedListをスタック、キュー、および双方向キューとして使用できるようにするには、addFirst()、addLast()、getFirst()、getLast()、removeFirst()およびremoveLast()の方法もあります.
 
では、二人の間の速度をテストするためにコードを書きます.

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    
    public static void main(String[] args){
        SimpleDateFormat matter = new SimpleDateFormat("    :yyyy MM dd E HH mm ss ");
        List<Integer> list = new ArrayList<Integer>();
        System.out.println("         ： " + matter.format(System.currentTimeMillis()));
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        System.out.println("           ..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(list.size() - 1);
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("          ..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(0);
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("          ..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove((int)Math.random() * (list.size() - 1));
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        
        
        list = new LinkedList<Integer>();
        System.out.println("         ： " + matter.format(System.currentTimeMillis()));
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        System.out.println("           ..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(list.size() - 1);
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("          ..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(0);
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("          ..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove((int)Math.random() * (list.size() - 1));
        }
        System.out.println("       : " + matter.format(System.currentTimeMillis()));
        
    }
}

出力結果は次のとおりです.
配列形式の開始時間:現在時間:2013年05月29日水曜日16時49分07秒書き込み完了時間:現在時間:2013年05月29日水曜日16時49分07秒毎回最後の要素をクリア...现在时间:2013年05月29日水曜16时49分07秒パージ终了时间:现在时间:2013年05月29日水曜16时49分07秒毎回1つ目のエレメントをパージ...现在时间:2013年05月29日水曜16时49分07秒パージ终了时间:现在时间:2013年05月29日水曜16时49分37秒毎回ランダムに1つの要素をパージ...现在时间:2013年05月29日水曜16时49分37秒结束时间:现在时间:2013年05月29日水曜16时49分51秒チェーンテーブル形式开始时间:现在时间:2013年05月29日水曜16时49分51秒书き込み完了时间:现在时间:2013年05月29日水曜16时49分51秒毎回最后の要素をクリア...现在时间:2013年05月29日水曜16时49分51秒クリア时间:现在时间:2013年05月29日水曜16时49分51秒毎回1つ目の要素をクリア...现在时间:2013年05月29日水曜16时49分52秒パージ终了时间:现在时间:2013年05月29日水曜16时49分52秒ランダムに1つの要素をパージ...現時点:2013年05月29日水曜16時49分52秒クリア済み時間:現時点:2013年05月29日水曜16時49分52秒
出力結果から,配列形式の場合,最後の要素を毎回消去する時間は1秒未満であり,主に消去中にソート操作に関与しないことがわかる.
配列形式で1番目の要素を消去する操作では、その後のN-1個の残りの要素を毎回前に移動し、約30秒かかります.
配列形式でランダム要素をクリアし、移動するたびに1/2(N-1)個あるので、理論的に消費される時間は15秒で、結果は14秒で、正常であることを示しています!
結果から,チェーンテーブル形式の実装では削除操作にほとんど時間がかからないことも分かる.