JavaのArrayListとLinkedListの違い（処理速度）についての定説はビッグデータ時代でも当てはまるか？
　ネットを検索してみると実装の違いから，ArrayListは参照優先で追加や削除の少ない場合に，LinkedListは追加や削除の多い場合に使用すると良いというのが定説になっている．しかし，ビッグデータ時代ではこんな定説だけを頼りにしてはいけないかもしれない．例えば今，仕事でやろうとしていたのは1000万のレコードをListに読み込んで処理するものであり，参照も多いし削除も多い（追加は無い）．どっちを選択すべきか悩ましい．そこでリスト後方で追加したり削除したりする下記の検証コードを組んで実験してみた．
　結果は下記の通り．

Insert Test Class	java.util.ArrayList
Insert A	4ms
Insert Test Class	java.util.LinkedList
Insert A	40ms
Remove Test Class	java.util.ArrayList
Remove A	1ms
Remove B	25ms
Remove Test Class	java.util.LinkedList
Remove A	19ms
Remove B	313ms

　Insert Aはリスト後方（リスト中80％の位置）にaddする時間を計測している．ArrayListは4ms，LinkedListは40msと，LinkedListの方が10倍も遅い結果になった．
　Remove Aはリスト後方（リスト中90％の位置）の要素をremoveする処理，Remove Bは（リスト中90％の位置）の要素を取得したのちに，そのオブジェクトを引数にしてremoveする処理をの時間をそれぞれ計測している．私が仕事でやりたかったのはRemove Bの処理が近い．リストから特定位置の要素を取得して取得したオブジェクトのメソッドを呼び出し，その結果に基づいてリストから削除するといったような処理である．Remove Aのテスト結果を見ても，ArrayListに対しLinkedListは19倍も処理時間がかかっている．したがって，“追加や削除が頻繁な場合はLinkedListを選べ”という定説は誤りであると言えるだろう．
　たとえばremoveメソッドを呼び出す際，特にObjectを指定したremoveは対象のオブジェクト検索しているはずなので処理に時間がかかる．つまり，リスト内への参照が行われている．今回の事例のように，リストの後方であるほどに時間がかかるのは自明であるから，参照が苦手なLinkedListのほうがremoveに時間がかかるのも容易に想像できる．今回の検証では10倍以上の差（25msに対し313ms）が出た．
　挿入位置を指定したaddでも，LinkedListでは挿入位置の特定のためにリスト構造を走査する処理が発生するはずである．大量のデータを扱っている場合は，挿入処理を行う時間よりも走査処理に要する時間がかかることによって，今回の検証のようにArrayListよりもLinkedListが不利な結果になるのである．LinkedListが有利なケースは，リストの先頭や最後に追加したり削除したりするなど，リスト構造を走査する必要がない場合のみであろう。
　私が仕事で実装していたプログラムの場合，特にObjectを指定したremoveを何度も呼び出しておりボトルネックとなった．ArrayListに変更しても実用的にならかなったため，“削除しない方法で削除”することでこの問題を解決することにした．その話題はまた今度．
============

package com.agentier.lab.listtest;

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

public class Tester {

    static final int LIST_NUM=10000000; 
    
    public static void main(String[] args) throws Exception {

        List<MyClass> listA = createList(ArrayList.class);
        List<MyClass> listB = createList(LinkedList.class);
        
        startTestInsert(listA);
        startTestInsert(listB);
        
        startTestRemove(listA);
        startTestRemove(listB);
    }

    static List<MyClass>
        createList(Class<? extends List> listClass) throws Exception {
        List<MyClass> list = listClass.newInstance();
        
        for(int i=0; i< Tester.LIST_NUM; i++){
            Tester.MyClass my = new MyClass(Math.random());
            list.add(my);
        }
        return list;
    }
    
    static void startTestInsert(List<MyClass> list){

        System.out
            .println("Insert Test Class\t"+list.getClass().getName());

        Tester.MyClass my = new MyClass(Math.random());

        long lInsertStartA = System.currentTimeMillis();
        list.add( (int)( list.size()*0.8), my);
        long lInsertEndA = System.currentTimeMillis();
        System.out
        .println("Insert A\t"+( lInsertEndA- lInsertStartA)+"ms");
    }

    static void startTestRemove(List<MyClass> list){

        System.out
            .println("Remove Test Class\t"+list.getClass().getName());

        long lRemoveStartA = System.currentTimeMillis();
        list.remove( (int)( list.size()*0.9));
        long lRemoveEndA = System.currentTimeMillis();
        System.out
        .println("Remove A\t"+( lRemoveEndA- lRemoveStartA)+"ms");
        
        long lRemoveStartB = System.currentTimeMillis();
        MyClass my = list.get( (int)( list.size()*0.9) );
        list.remove( my);
        long lRemoveEndB = System.currentTimeMillis();
        System.out
        .println("Remove B\t"+( lRemoveEndB- lRemoveStartB)+"ms");
    }
    

    
    static public class MyClass{
        double number;
        
        public MyClass(double num){
            this.number = num;
        }

        public double getNumber(){
            return number;
        }
        
        public void setNumber(double num){
            this.number = num;
        }
    }
}

（2012-01-18一部修正）