今回のテーマは「Listの操作にかかる時間」です。

みなさんはListの要素を繰り返し追加、削除する際に、処理にかかる時間を意識したことがあるでしょうか。 実はListの先頭から操作した場合と末尾から操作した場合では、処理にかかる時間が大幅に違う場合があるのです。

一般に最もよく使われているArrayListを使って時間を計測してみましょう。 時間の計測には、Apache CommonsのStopWatchクラスを使用しています。

import java.util.ArrayList; 
import java.util.List; 
import java.util.ListIterator;
import org.apache.commons.lang.time.StopWatch;

public class Main { 
    public static void main(String[] args) { 
        List<Integer> list = new ArrayList<Integer>(); 
        StopWatch stopWatch = new StopWatch(); 
        stopWatch.start(); 
        for (int i = 100000; i > 0; i--) { 
            list.add(0, i);         } 
        stopWatch.stop(); 
        System.out.println("要素を先頭に追加した場合：" + stopWatch.getTime() 
                                                                       + "ミリ秒");

        stopWatch.reset(); 
        stopWatch.start(); 
        for (ListIterator<Integer> iterator = list.listIterator(); 
                                                            iterator.hasNext();) { 
            iterator.next(); 
            iterator.remove(); 
        } 
        stopWatch.stop(); 
        System.out.println("要素を先頭から削除した場合：" + stopWatch.getTime() 
                                                                       + "ミリ秒");

        stopWatch.reset(); 
        stopWatch.start(); 
        for (int i = 1; i <= 100000; i++) { 
            list.add(i); 
        } 
        stopWatch.stop(); 
        System.out.println("要素を末尾に追加した場合：" + stopWatch.getTime() 
                                                                      + "ミリ秒");

        stopWatch.reset(); 
        stopWatch.start(); 
        for (ListIterator<Integer> iterator = list.listIterator(list.size()); 
                                                       iterator.hasPrevious();) { 
            iterator.previous(); 
            iterator.remove(); 
        } 
        stopWatch.stop(); 
        System.out.println("要素を末尾から削除した場合：" + stopWatch.getTime() 
                                                                     + "ミリ秒"); 
    } 
}

処理にかかる時間が全然違うことがわかると思います。
なお、Listに変更が多い処理はLinkedListのほうが適していますし、計測結果も違ってきます。