ArrayList と LinkedList - ぼうメモ帳

今日の技術ネタ。難しい話は、なし。

議題

ArrayListとLinkedList、どちらを使えばよいでしょうか。

最近、会社のタバコ部屋で、上記の質問をされました。
気まぐれに、自チームで開発しているツールのソースコードレビューをしていたら、一度作ったら変更しないListに対してLinkedListが多用されていたので、なぜそれを選んだと聞くと、LinkedListの方が汎用性に優れるという回答があった。

自分の考え

とりあえず、ArrayListを使え。 ArrayListとLinkedListの使い分けが理解できなければ、LinkedListは使う価値なし。

理由１：性能面

ArrayListに対するLinkedListが持つ圧倒的な優位性は、下記の２つです。たった、これだけです。

先頭への挿入が速い
Iterator/ListIterator使用時のadd/removeが速い

まず、先頭への挿入が速いという話ですが、先頭への挿入しかしない場合は、ArrayListの末尾に挿入して、一通りの挿入処理が終わったら、reverseすれば良いです。それで、十分に元が取れます。もし、先頭と最後に半々ぐらいで挿入したい場合は、ArrayDequeを使えば良いです。ArrayDequeは、RingBufferの構造をしているので、先頭と最後への挿入であれば速いです。

次に、LinkedListは、Iterator/ListIteratorを使用したときは、途中の要素を追加／削除するときは圧倒的に速いです。

LinkedListを教科書とかで読むと、一般的には途中要素への挿入削除が速いとしか書いていませんが、これは動作させるマシンの特性に依存します。 ArrayListの場合、途中に挿入・削除しようとすると、配列のコピーが発生しますが、連続領域のコピーであるため、このコピーは速いです。対して、LinkedListの場合、Iterator等を使わずに挿入・削除を行おうとすると、ポインタを手繰りながら目的のエントリまで到達し、そこで初めてO(1)処理が行われます。そのため、メモリへのランダムアクセスが大量に発生します。

昨今のCPUは、メモリアクセスに比べてCPU性能が上がりすぎているため、CPUキャッシュをいかに使うか、すなわちメモリの局所性をいかに活かすかが重要であり、昔ほどLinkedListの優位性はなくなりました。（もちろん、今でも挿入・削除しかしないのであれば根本的にはLinkedListの方が速いのですが、本当に、それだけで済みますか？　途中で検索処理が１回でも入った瞬間に、そのメリットは打ち消されます。例えば、何番目に挿入するっていう処理、検索なしに書きますか？　大抵の場合、何番目に挿入するかを決定するためにリストを舐める処理が入ると思います。この舐める処理を入れた瞬間、ArrayListに負けます。）

そのため、LinkedListは、Iterator/ListIteratorで頭から舐めながら、都度都度入れたり抜いたりするときだけ使えます。ただ、この処理、書きますか？という話です。この処理を、素でさっと書けるだけの技量があるなら、そもそも、ArrayListとLinkedListを迷うようなことはありません。

理由２：メモリ面

LinkedListとArrayListでは、メモリ使用量が圧倒的に異なります。

Javaは、オブジェクトヘッダを持つため、オブジェクトを生成するだけで8バイトのメモリを消費します。 LinkedListは、双方向リストであるため、エントリのオブジェクトヘッダ（８バイト）、前のエントリへの参照（８バイト）、本エントリの値への参照（８バイト）、次のエントリへの参照（８バイト）と、１つのエントリを保持するために３２バイトのメモリが必要になります。

対して、ArrayListであれば、配列でガッツリ確保しているため、本エントリの値への参照（８バイト）だけが必要になります。（配列のヘッダなどは、保持するエントリの数が多くなればオーバーヘッドとしては無視できる。）ただし、ArrayListは大きめに配列を保持する（最大１．５倍）ため、余分な領域が生まれます。

そのため、ArrayListが平均１．３倍の配列領域を確保していると考えると、LinkedListの方がArrayListに比べて３倍ぐらいメモリを使用することになります。

結論

大概のケースに置いて、ArrayListの方が性能がよく、さらに全てのケースに置いてメモリ使用量がArrayListの方が優れていると考えると、 ArrayListとLinkedListのどちらを使えば良いか悩むのであれば、とりあえず、ArrayListを使うべきです。

それで性能問題が起きたら、初めてLinkedListを候補に入れれば良いです。ただ変更するときは、OutOfMemoryErrorに注意しましょう。