Javaのパフォーマンスチューニング。第二回はArrayListとLinkedListの使い分け

ArrayListとLinkedListのパフォーマンスについて、簡単な実験

add(Object e)を使ってListに値を追加するケース

add(Object e)と、indexを指定しないaddメソッドを使います。
以下のソースコードで実験しました。
※以下、ArrayListは全てjava.util.ArrayList LinkedListは全てjava.util.LinkedList です。

public static void main(String[] args) {
  // ここの一行を切り替える
  List<String> list = new ArrayList<String>();  // ArrayListの場合
  List<String> list = new LinkedList<String>(); // LinkedListの場合

  long before = System.nanoTime();
  for(int i=0; i<10000; i++) {
    list.add("aa");
  }
  System.out.println(System.nanoTime() - before);
}

ArrayListの場合

上記を10回行なったところ
847418, 846204, 819625, 838742, 853644,
850054, 829031, 843651, 1050932, 841452

LinkedListの場合

上記を10回行なったところ
1112485, 1110282, 1112572, 1082978, 1084090,
1137864, 1108921, 1206105, 1146631, 1258097

となり、順番を指定せずaddしていくのならArrayListの方がやや高速です。

get(int index)Listから値を取得するケース

値を格納したListから、値を取得するケースです。
以下のソースコードで実験しました。

public static void main(String[] args) {
  // ここの一行を切り替える
  List<String> list = new ArrayList<String>();  // ArrayListの場合
  List<String> list = new LinkedList<String>(); // LinkedListの場合
  list.add("aa");
  list.add("bb");
  list.add("cc");
  list.add("dd");
  list.add("ee");

  long before = System.nanoTime();
  for(int i=0; i<10000; i++) {
    list.get(2);
  }
  System.out.print(System.nanoTime() - before);
}

ArrayListの場合

596626, 594848, 597257, 602190, 598340,
605840, 596513, 592892, 590663, 597573

LinkedListの場合

825877, 814325, 824907, 804359, 879027,
847430, 823110, 828835, 822768, 806054

となり、こちらもArrayListの方がやや高速です。
やはり普通にadd(Object e)メソッドや、get(int index)メソッドを使う分には
ArrayListの方が良いでしょう。

add(int index, Object e)を使って追加するケース

public static void main(String[] args) {
  // ここの一行を切り替える
  List<String> list = new ArrayList<String>();  // ArrayListの場合
  List<String> list = new LinkedList<String>(); // LinkedListの場合
  list.add("aa");
  list.add("bb");
  list.add("cc");
  list.add("dd");
  list.add("ee");

  long before = System.nanoTime();
  for(int i=0; i<10000; i++) {
    list.add(2, "ZZ");
  }
  System.out.print(System.nanoTime() - before);
}

ArrayListの場合、上記を10回行なったところ
36173553, 36551056, 36056320, 36108362, 36007614,
36144102, 36153884, 36236105, 36240613, 36135320

Linkedの場合、上記を10回行なったところ
1410705, 1591784, 1485074, 1458217, 1363326,
1373661, 1569167, 1394675, 1431901, 1401476

となり、LinkedListの方が圧倒的に早いことがわかります。
実際のJavaでのシステム開発でindexを指定したaddメソッドはあまり使うことはありませんが
使う場合は、LinkedListを使う方が良いこともあるでしょう。
ただし、上記のように1万回もループさせることは稀であることや
値を取得するgetメソッドのパフォーマンスはArrayListの方が高速なので
ArrayListを使った方が無難だと思います。