ArrayList クラスRevised: Nov./6th/2004; Since: Feb./23rd/2003
クラス ArrayList は、インタフェース List の最も基本的な実装です。List インタフェースは、線形配列型のデータ構造の振る舞いを規定するものであり、実装するクラスには、ArrayList, LinkedList, Vector が挙げられます。
java.lang.Object
|
+--java.util.AbstractCollection
|
+--java.util.AbstractList
|
+--java.util.ArrayList
ArrayList クラスは java.util パッケージに含まれるので、利用するファイルではパッケージをインポートしておく必要があります。
古いコレクションクラスである Vector を置き換えるのが ArrayList です。その最大の違いは、Vectorではマルチスレッドによる同時アクセスに対して保護されているのに対して、ArrayListでは保護されていないということです。Vectorは最大でも一つのスレッドからしかアクセスされ得ませんが、ArrayListは同時に複数のスレッドからアクセスされる可能性があります。そのために、ArrayListをマルチスレッド環境で利用する場合は、同時アクセスによるデータの不整合が発生しないように、明示的にマルチスレッドによるアクセスの同期をとるように指定する必要があります。その反面、Vectorに比べてArrayListのほうがかなり高速です。
一般に、Vectorを使うときは、ArrayListを使うようにしましょう。また、配列が利用できないか検討することも必要です。
API 仕様では次のように説明されています：
Listインタフェースのサイズ変更可能な配列の実装です。リストの任意のオペレーションをすべて実装し、nullを含むすべての要素を許容します。このクラスは、Listインタフェースを実装するほか、リストを格納するために内部的に使われる配列のサイズを操作するメソッドを提供します。(このクラスは、同期化されないことを除いてVectorとほぼ同等です。)
ArrayList はサイズが拡張可能な配列型データ構造です。デフォルトでは初期サイズは10個になっており、サイズが足りなくなるたびに50%ずつサイズが拡張します。内部的には Object 型の配列を使っているので、サイズ拡張毎に、新しい配列の生成と既存の要素のコピー及び既存の配列の破棄というプロセスが必要になるので、パフォーマンスが非常に悪化します。
50%ずつのサイズ拡張に伴うメモリの浪費も無視できません。可能であれば、最初から必要なサイズを見積もって、インスタンス化するべきです。このとき、予約容量によるメモリの浪費とパフォーマンスのトレードオフであることを認識する必要があります。現在の要素数以上にサイズが増えないことがわかっていれば、メモリの使用効率を最適化するために、trimToSize() メソッドによって、現在の要素数までサイズを減じることも可能です。
要素の追加に関しては、インデックスの最後に追加する分には、既存の要素数によらず（サイズ拡張を伴わなければ）一定のパフォーマンスが得られます。一方、先頭に追加すると、後続の既存の要素が全て後ろに追い出されますので、サイズが大きくなるに従い、パフォーマンスが極端に悪化します。
ArrayListはランダムアクセスをサポートします。そのため、get(i)によるi番目インデックス要素の取得は非常に高速であり、単純な配列に準じます。例えば、ランダムアクセスに依存する java.util.Collections クラスの binarySearch(List list, Object key) メソッドにより、極めて高速な要素の探索が可能になります。
ArrayList() |
初期容量 10 で空のリストを作成します。 |
ArrayList(Collection c) |
指定されたコレクションの要素を含むリストを作成します。 |
ArrayList(int initialCapacity) |
指定された初期サイズで空のリストを作成します。 |
ArrayList のサイズは自動的に拡張可能です。しかし、サイズの拡大はパフォーマンスの悪化を招くので、最初から適切なサイズで生成するようにしましょう。メモリ使用量とパフォーマンスのトレードオフであることを認識することが重要です。
二番目のコンストラクタ引数の Collection というのは、コレクション・フレームワークの List と Set のスーパー・インタフェースです。 List と Set を実装するデータ構造のクラス型オブジェクトを引数に取れるということです。このコンストラクタを使えば、異なる特性のデータ構造間の変換も容易です。
基本的には、 Vector のメソッドと同様です。メソッドが多いので、代表的なメソッドの名前だけ紹介しておきます。全てのメソッドの詳細な定義は API 仕様を直接ご確認ください。
要素の追加（add() 系メソッド）、挿入（insert() 系メソッド）、削除（remove() 系メソッド）、配列/文字列などへの変換、サイズ変更などのメソッドが多く定義されています。
ArrayList と LinkedList のパフォーマンスを比較してみましょう。
次のコードは get(i) メソッドによって、List の要素に直接アクセスするサンプルです。クラス LinkedList は、最初や最後から順番にアクセスするので、クラス ArrayList よりも遅くなります。
import java.util.*;
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 arrayList;
LinkedList linkedList;
int MAX = Integer.parseInt(args[0]);
Object[] intarray = new Integer[MAX];
for (int i = 0; i < MAX; i++) {
intarray[i] = new Integer(i);
}
List list = Arrays.asList(intarray);
arrayList = new ArrayList(list);
linkedList = new LinkedList(list);
ListDemo demo = new ListDemo();
System.out.println("ArrayList: " +
demo.elapsed(arrayList, MAX));
System.out.println("LinkedList: " +
demo.elapsed(linkedList,MAX));
}
}
ここでは、配列 itnarray[] からリスト・オブジェクトを生成するのに、 java.util.Arrays の asList() を使っています。ArrayList も LinkedList も List 型オブジェクトを引数にとるコンストラクタによって初期化可能です。
get() の実行による時間の比較のためのメソッド ellapsed() の引数には List 型を指定しています。コレクション・フレームワークは、インタフェースによる統一的な設計を特徴としているので、メソッド引数にインタフェース型を指定することが非常に効果的です。そのインタフェースを実装するクラス型オブジェクトを引数に与えることで、各々のクラス型に応じた異なる振る舞いを持たせることが可能となるからです。ポリモーフィズム（多態性）の実装の顕著な例です。
経過時間の測定には、java.lang.System の currentTimeMills() を使いました。これは、現在の時間をミリ秒で返すものです。実行に要した時間の目安にはなるでしょう。
C:\java>javac ArrayListDemo.java C:\java>java ArrayListDemo 1000 ArrayList: 0 LinkedList: 10 C:\java>java ArrayListDemo 10000 ArrayList: 10 LinkedList: 200 C:\java>java ArrayListDemo 50000 ArrayList: 10 LinkedList: 13269
次のコードは add() メソッドを使って、 List の最初に要素を追加するものです。LinkedList の場合は、前後の要素にたいする Entry を付け替えるだけですが、 ArrayList では後続の要素を全て追い出すことになるので、パフォーマンスが劣化します。
import java.util.*;
class ListAddDemo {
void elapsed(List list, int MAX) {
long start = System.currentTimeMillis();
for (int i = 0; i > MAX-1; i++) {
list.add(0, new Integer(i));
long end = System.currentTimeMillis();
if (i % 10000 == 0) {
System.out.println(end - start);
}
}
}
}
class ArrayListAddDemo {
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();
int MAX = Integer.parseInt(args[0]);
ListAddDemo demo = new ListAddDemo();
System.out.println("ArrayList:");
demo.elapsed(arrayList, MAX);
System.out.println("LinkedList:");
demo.elapsed(linkedList, MAX);
}
}
ここでは要素をリストの先頭に追加していく時間の経過を 10000 ミリ秒単位で出力しています。出力に要する時間も馬鹿にならないのですが、比較の目安にはなるでしょう。
C:\java>javac ArrayListAddDemo.java C:\java>java ArrayListAddDemo 100000 ArrayList: 250 791 1482 2443 3695 5207 7050 9193 11827 LinkedList: 20 90 100 100 120 130 240 240 250
ArrayList はサイズに対して発散的で、LinkedList は階段的に増加して Log 的（対数的）発散に見えます。説明できないこともあるのですが、概ね、ArrayList はサイズの増加に対するコスト増が大きく、LinkedList ではサイズの増加に対しても一定のパフォーマンスを保っていることが見て取れます。
LinkedList はインデックスが前後の要素をポイントしているので、順次アクセスに対して最適化されています。ArrayList はランダムアクセスに最適化されており、効果的に反復を実行する仕組みを持っていません。その都度毎にランダムアクセスするため、 LinikiedList に比べると若干遅くなります。
import java.util.*;
class ListIterationDemo {
long elapsed(List list) {
long start = System.currentTimeMillis();
Iterator itr = list.iterator();
while (itr.hasNext()) {
itr.next();
}
long end = System.currentTimeMillis();
return (end - start);
}
}
class ArrayListIterationDemo {
public static void main(String[] args) {
ArrayList arrayList;
LinkedList linkedList;
ListIterationDemo demo = new ListIterationDemo();
int MAX = Integer.parseInt(args[0]);
Object[] intarray = new Integer[MAX];
for (int i = 0; i > MAX; i++) {
intarray[i] = new Integer(i);
}
List list = Arrays.asList(intarray);
if (args[1].equals("ArrayList")) {
arrayList = new ArrayList(list);
System.out.println("ArrayList: " +
demo.elapsed(arrayList));
} else if (args[1].equals("LinkedList")) {
linkedList = new LinkedList(list);
System.out.println("LinkedList: " +
demo.elapsed(linkedList));
} else {
System.out.println("Arguments invalid!");
return;
}
}
}
ここでは、先に実行した処理の影響が出ないように、if 構文を用いることで、引数によって生成するオブジェクトを変えています。
C:\java>javac ArrayListIterationDemo.java C:\java>java ArrayListIterationDemo 10000 ArrayList ArrayList: 10 C:\java>java ArrayListIterationDemo 100000 ArrayList ArrayList: 20 C:\java>java ArrayListIterationDemo 1000000 ArrayList ArrayList: 130 C:\java>java ArrayListIterationDemo 10000 LinkedList LinkedList: 10 C:\java>java ArrayListIterationDemo 100000 LinkedList LinkedList: 10 C:\java>java ArrayListIterationDemo 1000000 LinkedList LinkedList: 121
古いAPIと新しいAPIの例として、繰り返し（反復）が挙げられます。コレクション・フレームワークでは、要素を順番にアクセスするために、対象のコレクション・オブジェクトから、インタフェースIterator型のオブジェクトを取得して使います。Vectorでは、Iteratorのほかに、古いAPIであるインタフェースEnumerationも使えます。
LinkiedListはArrayListと同時に提供されたもので、各要素は前後の要素への双方向リンクを持っています。前後の要素へのリンクを持たない、単純な配列やArrayList, Vectorの場合は、挿入すると、後続の要素を一個ずつずらしてコピーする必要があるので、要素数が増大すると、必要なコストも増大します。一方、LinkedListの場合は、要素の挿入や削除には、前後の要素からのポインタの付け替えだけで実現できるので非常に高速です。このような特性を活かして、LinkedListでは、双方向への繰り返しや、先端および終端にある要素を挿入／取得／削除のためのメソッドが利用可能です。これらのメソッドにより、LinkedListは、スタック(LIFO: Last In First Out)、キュー(FIFO: First In First Out, LILO: Last In Last Out)として使うことができます。
動作特性としてまとめると、LinkedListでは、要素のアクセスに、前後の要素へのリンクを利用して、先頭から順番にアクセスしていくので、要素を索引番号で直接アクセスできるArrayListに比べて、索引番号による要素の特定（ランダム・アクセス）が著しく遅くなります。その一方で、途中の要素の挿入／削除時には、後続要素のコピーが必要になるArrayListに比べて、前後の要素のポインタの付け替えだけで済むので高速になります。
ListやSetなど、Collectionを実装するクラス型オブジェクトの要素を全て取り出したいことがあります。このようなときは、Iteratorを使うのが普通です。
//Iteratorの取得
public static void printAll(Collection collection) {
Iterator it = collection.iterator();
while(it.hasNext()) { // 次の要素が存在する限りブロック内を繰り返し実行
System.out.println(it.next()); // 次の要素を取得してその次の要素へ進む
}
}
これは、次のように書くこともできます。
for (Iterator it = collection.iterator(); it.hasNext();) {
System.out.println(it.next()); // 全ての要素を順番にプリント
}
Iteratorでは、他にも削除のメソッドがサポートされています。
Vectorのようなコレクション・フレームワーク以前からあるクラスでは、Enumerationも使うことができます。Enumerationで提供される機能はIteratorでも提供されています。Iteratorを使うことで、オブジェクトを他のコレクション・クラス型へ変更することができるようになります。
// Vector型オブジェクトvecのEnumerationの利用
for (Enumeration e = vec.elements(); e.hasMoreElements();) {
System.out.println(e.nextElement()); // 全ての要素を順番にプリント
}
LinkedListは、前後の要素へのポインタを持ったダブル・リンクリストです。特徴は、前後の要素への繰り返し参照が高速だという点が挙げられます。LinkedListではIteratorのほかにListIteratorを使うこともできます。Iteratorでは、次の要素への移動しかサポートしていませんが、LinkedListでは逆方向へ要素をたどることができます。
// indexから逆方向に全ての要素をプリント
public static void printReverse(LinkedList list, int index) {
for (ListIterator lit = list.listIterator(index); lit.hasPrevious();) {
System.out.println(lit.previous());
}
}
ListIteratorでは、他にも要素の挿入／削除／置換などのメソッドがサポートされています。
バイナリサーチは、二分探索法と訳されます。ソートされた List に対して、指定した値がどこにあるのか、そもそもないのかを探索する方法です。まず、指定された値と List の中央の値を比較して、指定された値のほうが小さければ、 List の下半分を残し、大きければ上半分を残します。そして、半分の更に中央の値と比較して、探索対象のほうが大きければ List の上半分を残し、小さければ下半分を残し、最大値／最小値を超えるまでこれを繰り返します。
二分探索法は本質的に、ランダムアクセスを使用しており、LinkedList では ArrayList に比べて極端にパフォーマンスが悪化します。
import java.util.*;
class ListSearchDemo {
long elapsed(List list, int MAX) {
long start = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
Collections.binarySearch(list, new Integer(i));
}
long end = System.currentTimeMillis();
return (end - start);
}
}
class ArrayListSearchDemo {
public static void main(String[] args) {
List list = null;
int MAX = 0;
try {
list = (List) Class.forName("java.util." + args[0]).newInstance();
} catch (ClassNotFoundException e) {
e.printStackTrace();
} catch (InstantiationException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
}
MAX = Integer.parseInt(args[1]);
Integer[] intarray = new Integer[MAX];;
for (int i = 0; i < MAX; i++) {
intarray[i] = new Integer(i);
}
List srcLst = Arrays.asList(intarray);
list.addAll(srcLst);
Collections.sort(list);
ListSearchDemo demo = new ListSearchDemo();
System.out.println(args[0] + ": " + demo.elapsed(list, MAX));
}
}
ここでは、 List オブジェクトの生成にクラス・ローダーを使っています。これは、引数の文字列から生成するクラスを変えるために採用した工夫です。Class.forname() の戻り値型は java.lang.Class 型なので、List 型にキャストしています。この方法は、メソッド引数によって生成するオブジェクトを変える場合などに、柔軟に使うことができます。
配列から List を作るに当たっては、java.util.Arrays の asList() を使っていますが、戻り値型が List 型であるため、 ArrayList や LinkedList の要素にするために addAll() で要素の全てをリストオブジェクトに代入しています。
ここでは java.util.Collections の binarySearch() のコスト比較をしていますが、それに先立って要素がソートされている必要があります。ソートされていることを保障するために、ここでは Collections クラスの sort() メソッドでソートを欠けてからサーチしています。
C:\java>javac ArrayListSearchDemo.java C:\java>java ArrayListSearchDemo ArrayList 10000 ArrayList: 30 C:\java>java ArrayListSearchDemo ArrayList 20000 ArrayList: 50 C:\java>java ArrayListSearchDemo ArrayList 30000 ArrayList: 80 C:\java>java ArrayListSearchDemo ArrayList 50000 ArrayList: 140 C:\java>java ArrayListSearchDemo LinkedList 10000 LinkedList: 3204 C:\java>java ArrayListSearchDemo LinkedList 20000 LinkedList: 13579 C:\java>java ArrayListSearchDemo LinkedList 30000 LinkedList: 40438 C:\java>java ArrayListSearchDemo LinkedList 50000 LinkedList: 150196