<<PREV | ToC | NEXT>>

インタフェースListの実装クラス

Revised: May/6th/2008; Since: Feb./23rd/2003

クラスArrayListは、インタフェースListの最も基本的な実装です。インタフェースListは、線形配列型のデータ構造の振る舞いを規定するものであり、実装するクラスには、ArrayList, LinkedList, Vectorなどが挙げられます。

ArrayListの継承階層

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--java.util.AbstractList
              |
              +--java.util.ArrayList

ArrayList クラスは java.util パッケージに含まれるので、利用するファイルではパッケージをインポートしておく必要があります。

ArrayListの概要

古いコレクションクラスであるVectorを置き換えるのがArrayListです。その最大の違いは、Vectorではマルチスレッドによる同時アクセスに対して保護されているのに対して、ArrayListでは保護されていないということです。Vectorは最大でも一つのスレッドからしかアクセスされ得ませんが、ArrayListは同時に複数のスレッドからアクセスされる可能性があります。そのために、ArrayListをマルチスレッド環境で利用する場合は、同時アクセスによるデータの不整合が発生しないように、明示的にマルチスレッドによるアクセスの同期をとるように指定する必要があります。その反面、Vectorに比べてArrayListのほうが高速です。

一般に、Vectorを使うときは、ArrayListを使うようにしましょう。同期化が必要な場合は、Collections.synchronizedList メソッドで同期化されたオブジェクトを取得するか、ArrayListをインスタンス化してカプセル化する包含オブジェクトで同期化するのが普通です。また、パフォーマンス上の利得を得るためには、配列を利用できないか検討してください。

API 仕様では次のように説明されています：

List インタフェースのサイズ変更可能な配列の実装です。リストの任意のオペレーションをすべて実装し、null を含むすべての要素を許容します。このクラスは、List インタフェースを実装するほか、リストを格納するために内部的に使われる配列のサイズを操作するメソッドを提供します (このクラスは、同期化されないことを除いて Vector とほぼ同等)。

size、isEmpty、get、set、iterator、および listIterator の処理は、一定の時間で実行されます。add の処理も、一定の償却時間で実行されます。 つまり、n 個の要素を追加するには O(n) 時間が必要です。ほとんどの場合、ほかのすべての処理も比例的な時間で実行されます。定数の係数は、LinkedList の実装の場合より小さくなります。

ArrayListの動作特性

ArrayListはサイズが拡張可能な配列型データ構造です。デフォルトでは初期サイズは10個になっており、サイズが足りなくなるたびに50%ずつサイズが拡張します。内部的にはObject型の配列を使っているので、サイズ拡張毎に、新しい配列の生成と既存の要素のコピー及び既存の配列の破棄というプロセスが必要になるので、パフォーマンスが非常に悪化します。

50%ずつのサイズ拡張に伴うメモリの浪費も無視できません。可能であれば、最初から必要なサイズを見積もって、インスタンス化するべきです。このとき、予約容量によるメモリの浪費とパフォーマンスのトレードオフであることを認識する必要があります。現在の要素数以上にサイズが増えないことがわかっていれば、メモリの使用効率を最適化するために、メソッドtrimToSize()によって、現在の要素数までサイズを減じることも可能です。

要素の追加に関しては、インデックスの最後に追加する分には、既存の要素数によらず（サイズ拡張を伴わなければ）一定のパフォーマンスが得られます。一方、先頭に追加すると、後続の既存の要素が全て後ろに追い出されますので、サイズが大きくなるに従い、パフォーマンスが極端に悪化します。

ArrayListはランダムアクセスをサポートします。そのため、メソッドget(i)によるi番目インデックス要素の取得は非常に高速であり、単純な配列に準じます。例えば、ランダムアクセスに依存するjava.util.CollectionsクラスのbinarySearch(List list, Object key)メソッドにより、極めて高速な要素の探索が可能になります。

ArrayListのコンストラクタ

ArrayList のサイズは自動的に拡張可能です。しかし、サイズの拡大はパフォーマンスの悪化を招くので、最初から適切なサイズで生成するようにしましょう。メモリ使用量とパフォーマンスのトレードオフであることを認識することが重要です。

二番目のコンストラクタ引数のCollectionというのは、コレクション・フレームワークのListとSetのスーパー・インタフェースです。ListとSetを実装するデータ構造のクラス型オブジェクトを引数に取れるということです。このコンストラクタを使えば、異なる特性のデータ構造間の変換も容易です。

ArrayListのメソッド

基本的には、Vectorのメソッドと同様です。メソッドの詳細な定義は API 仕様を直接ご確認ください。

要素の追加（add() 系メソッド）、挿入（insert() 系メソッド）、削除（remove() 系メソッド）、配列/文字列などへの変換、サイズ変更などのメソッドが多く定義されています。

サンプル

ジェネリクスを用いた型パラメータの利用方法はクラスVectorの場合と同様です。

ここではArrayListとLinkedListのパフォーマンスを比較してみましょう。

ランダムアクセス

次のコードはメソッドget(i)によって、Listの要素に直接アクセスするサンプルです。クラスLinkedListは、最初や最後から順番にアクセスするので、クラスArrayListよりも遅くなります。

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

class ListDemo {
	long elapsed(List<?> list, int MAX) {
		long start = System.currentTimeMillis();
		for (int i = MAX - 1; i > 0; i--) {
			list.get(i);
		}
		long end = System.currentTimeMillis();
		return (end - start);
	}
}
class ArrayListDemo {
	public static void main(String[] args) {
		ArrayList<Integer>  arrayList;
		LinkedList<Integer> linkedList;
		int MAX = Integer.valueOf(args[0]);
		
		Integer[] intarray = new Integer[MAX];
		for (int i = 0; i < MAX; i++) {
			intarray[i] = Integer.valueOf(i);
		}
		
		List<Integer> list = Arrays.asList(intarray);
		arrayList = new ArrayList<Integer>(list);
		linkedList = new LinkedList<Integer>(list);
		
		ListDemo demo = new ListDemo();
		System.out.println("ArrayList: " +
			demo.elapsed(arrayList, MAX));
		System.out.println("LinkedList: " +
			demo.elapsed(linkedList,MAX));
	}
}

ここでは、配列intarray[]からリスト・オブジェクトを生成するのに、java.util.ArraysのasList()を使っています。ArrayListもLinkedListもList型オブジェクトを引数にとるコンストラクタによって初期化可能です。

get()の実行による時間の比較のためのメソッドelapsed()の引数にはList<?>型を指定しています。コレクション・フレームワークは、インタフェースによる統一的な設計を特徴としているので、メソッド引数にインタフェース型を指定することが非常に効果的です。そのインタフェースを実装するクラス型オブジェクトを引数に与えることで、各々のクラス型に応じた異なる振る舞いを持たせることが可能となるからです。ポリモーフィズム（多態性）の実装の顕著な例です。

なお、型パラメータの?はワイルドカードです。異なる型パラメータを持つList型オブジェクトが渡されても、このメソッドは実行可能です。

経過時間の測定には、java.lang.SystemのcurrentTimeMills()を使いました。これは、現在の時間をミリ秒で返すものです。実行に要した時間の目安にはなるでしょう。

D:\java>javac ArrayListDemo.java

D:\java>java ArrayListDemo 10000
ArrayList: 15
LinkedList: 126

D:\java>java ArrayListDemo 50000
ArrayList: 16
LinkedList: 8536

D:\java>java ArrayListDemo 100000
ArrayList: 16
LinkedList: 31595

D:\java>

ArrayListの実行結果が要素数の増大に対して全く増えていないのに比べて、LinkedListでは指数関数的に増えていることがわかります。

要素の挿入／削除

次のコードはadd()メソッドを使って、 List の最初に要素を追加するものです。LinkedListの場合は、前後の要素にたいするEntryを付け替えるだけですが、ArrayListでは後続の要素を全て追い出すことになるので、パフォーマンスが劣化します。

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

class ListAddDemo {
	void elapsed(List<Integer> list, int MAX) {
		long start = System.currentTimeMillis();
		for (int i = 0; i < MAX-1; i++) {
			list.add(0, i);	// オートボクシング
			long end = System.currentTimeMillis();
			if (i % 10000 == 0) {
				System.out.println(end - start);
			}
		}
	}
}
class ArrayListAddDemo {
	public static void main(String[] args) {
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
		int MAX = Integer.valueOf(args[0]);
		ListAddDemo demo = new ListAddDemo();
		System.out.println("ArrayList:");
		demo.elapsed(arrayList, MAX);
		System.out.println("LinkedList:");
		demo.elapsed(linkedList, MAX);
	}
}

ここでは要素をリストの先頭に追加していく時間の経過を 10000 ミリ秒単位で出力しています。出力に要する時間も馬鹿にならないのですが、比較の目安にはなるでしょう。

D:\java>javac ArrayListAddDemo.java

D:\java>java ArrayListAddDemo 100000
ArrayList:
0
62
249
608
1028
1589
2275
3086
4099
5221
LinkedList:
0
15
15
15
15
15
62
78
78
78

D:\java>

ArrayListはサイズに対して発散的で、LinkedList<,/code>はLog的（対数的）発散に見えます。説明できないこともあるのですが、途中の要素が増減する操作に対しては、ArrayListはサイズの増加に対するコスト増が大きく、LinkedListではサイズの増加に対しても一定のパフォーマンスを保っていることが見て取れます。

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class ListSearchDemo {
	long elapsed(List<Integer> list, int MAX) {
		long start = System.currentTimeMillis();
		for (int i = 0; i < MAX; i++) {
			Collections.binarySearch(list, i);
		}
		long end = System.currentTimeMillis();
		return (end - start);
	}
}
class BinarySearchDemo {
	public static void main(String[] args) {
		List<Integer> list = null;
		for (int i = 1; i < 5; i++) {
			int MAX = i * 10000;
			try {
				// forName()はObject型を返す
				// List型を返すようにClassクラスの型パラメータを工夫
				// 但し、Class型は型パラメータを持てないので、未検査例外が発生
				Class<? extends List> cls = Class.forName("java.util." + args[0]).asSubclass(List.class);
				list = cls.newInstance();
			} catch (ClassNotFoundException e) {
				e.printStackTrace();
			} catch (InstantiationException e) {
				e.printStackTrace();
			} catch (IllegalAccessException e) {
				e.printStackTrace();
			}
			Integer[] intarray = new Integer[MAX];;
			for (int j = 0; j < MAX; j++) {
				intarray[j] = Integer.valueOf(j);
			}
			List<Integer> srcLst = Arrays.asList(intarray);
			list.addAll(srcLst);
			Collections.sort(list);
			ListSearchDemo demo = new ListSearchDemo();
			System.out.println(args[0] + ": " + demo.elapsed(list, MAX));
		}
	}
}

D:\java>javac -Xlint BinarySearchDemo.java
BinarySearchDemo.java:25: 警告:[unchecked] 無検査変換です
検出値  : capture#222 of ? extends java.util.List
期待値  : java.util.List<java.lang.Integer>
                                list = cls.newInstance();
                                                      ^
警告 1 個

D:\java>java BinarySearchDemo ArrayList
ArrayList: 15
ArrayList: 31
ArrayList: 32
ArrayList: 32

D:\java>java BinarySearchDemo LinkedList
LinkedList: 2929
LinkedList: 8630
LinkedList: 19437
LinkedList: 35413

D:\java>

Class<? extends List> cls = Class.forName("java.util." + args[0]).asSubclass(List.class);