Listインターフェイスの3つのクラスを理解する：JavaTips ～Javaプログラミング編

» 2005年04月13日 10時00分公開

　JavaのコアAPIに含まれるjava.util.Listインターフェイスは、順序付けられた可変長のデータの集まり「リスト構造」を表現するためのインターフェイスです。コアAPIには、Listの実装クラスがいくつか用意されていますが、そのうち抽象クラスでないものは、Vector、ArrayList、LinkedListの3つになります。ただ、これらのクラスを使う際には、それぞれの実装の違いを意識せずに、なんとなくいずれかを選んで使っていることが多いのではないでしょうか？

　本TIPSでは、これら3つの実装クラスについて、それぞれの実装の違いを比較します。Listインターフェイスが提供する主な操作は、要素の挿入（add）、削除（remove）、参照（get）の3つです（注）。ここでは、その3つの操作と、マルチスレッド環境下での同期化の観点から、それぞれの性能を比較し、使い分けのポイントをまとめます。

注：Listのもう1つの重要な操作として、検索（contains）がありますが、本TIPSで取り上げる3つの実装クラスでは、この操作に関してはあまり違いがありません。そこで、本稿の考察の対象からは外してあります。

Vectorクラス

　Java 1.0以前から存在する最も古いクラスです。Java 2と呼ばれるようになるJava1.2から、コアAPIにコレクション・フレームワークが導入され、Javaでデータ構造を扱うためのクラス群が刷新されました。Vector以外のList実装クラスはそのときより導入されたものですが、Vectorは主にJava 2以前のコードとの下位互換性を保つために残されました。

　コレクション・フレームワークで導入された新しいクラスとの大きな違いは、同期化の処理が実装されているという点です。つまり、マルチスレッド環境において、複数のスレッドから同時に操作されても、データの整合性を保つことができます。これは良いことのようにも聞こえますが、半面1つのスレッドからしか使われないことが分かっている場合でも、同期化を行うため、パフォーマンスが低下します。この問題を回避するため、新しいコレクション・フレームワークからは、基本的に同期化は実装せず、必要に応じて同期化ラッパーを挿入する（後述）ような形の設計方針になりました。

　Vectorクラスの実装上の特徴は、次に説明するArrayListクラスとほぼ同じになります。そのため、要素の挿入／削除／参照については、ArrayListと同じメリット／デメリットを持ちます。

ArrayListクラス

　ArrayListクラスは、内部的に配列を使ってリスト構造を実装しています。

　こうした実装から、要素を挿入／削除する場合は、インデックスの修正や、配列サイズの変更のために配列のコピーをしなくてはなりません。そのため、要素数が増えれば増えるほど、要素の挿入／削除には大きなコストが掛かるようになります。ただし、あらかじめ一定のキャパシティが確保されているため、キャパシティの範囲内であれば、要素の挿入については低いコストで可能です（キャパシティを超える拡張を行う場合には、内部的にやはり配列のコピーが発生するため、コストは大きくなります。これを避けるため、ArrayListを利用する場合にはあらかじめ想定され得る最大のキャパシティを確保しておくことが重要です）。

　一方で、配列はメモリ上にインデックス化されて格納されているため、x番目の要素を参照する、という操作は迅速に行うことができます。

　なお、このクラスは同期化の処理が実装されていないため、Vectorクラスよりは動作が高速です。マルチスレッド環境下で使いたい場合は、コレクションのためのユーティリティ・クラスjava.util.Collectionsを使って、以下のように同期化ラッパーを挿入する必要があります。

 List syncList = Collections.synchronizedList(new ArrayList(...));

LinkedListクラス

　LinkedListクラスでは、データの要素を数珠つなぎ（リンクリスト）に繋げていくことで、リスト構造を実装しています。

　そのため、要素の挿入／削除は、前後の要素のリンクを付け替えるだけで済みます。従って、要素数が非常に大きな場合でも、そのコストはほぼ一定です。

　逆に、リストに格納されている個々の要素は、実際にリンクをたどってみないと、何番目の要素であるのかは分かりません。そのため、要素の任意の位置を参照するには、リストの大きさに比例した時間がかかることになります。

　ArrayList同様、このクラスも同期化されていません。従って、マルチスレッド環境下で利用する場合は、ArrayListで示したのと同様の方法を使って、同期化されたリストへラップする必要があります。

まとめ

　以上をまとめると、以下の表のようになります。


	参照	挿入／削除	同期化
Vector	○	×	○
ArrayList	○	×	×
LinkedList	×	○	×

　これを踏まえて、使い分けのポイントは次のようになるでしょう。


ArrayList	・配列内の要素に対してランダムなアクセスを必要とする場合・配列内の要素に対して挿入／削除の操作があまり必要ない場合
LinkedList	・配列内の要素に対してランダムなアクセスを必要としない場合・配列内の要素に対して挿入／削除の操作を頻繁に行う場合

　具体例でいえば、データベースからデータを大量に読み込み、以後それを順に参照しつつ複雑な計算を行うような場合は、ArrayListが適しているといえます。一方、プログラム中で発生するデータの入れ物として使われ、時折データベースへ書き出してデータの永続化が図られるような用途には、LinkedListの方が向いていることになります。

　Vectorについては、基本的には下位互換のために用意されているレガシ実装であることから、特に理由がなければ使わない方がよいでしょう。マルチスレッド環境下で利用しなければならない場合でも、同期化ラッパーを使うことをお勧めします。同期化の手順を明示的に踏むことで、同期化しなければならない、というプログラマの意図を、コード中で明らかにしておくことができるからです。