(java)LinkedListについて。

Question

Listインタフェースを扱う際の実装クラスでは、今まで目にしたコードでは以下のような感じでArrayListクラスを使っているケースが多く、自分自身もArrayListを使うことがほとんどです。

List<String> list = new ArrayList<String>();

もしArrayListクラスではなくLinkedListクラスを使うべきケースがあるとしたら、どんな場合なのでしょうか？

Answer 1

ArrayListは、動的サイズ変更が可能なリスト構造を持つ配列です。

要素の追加・削除が発生すると、インデックス修正や配列サイズ変更を行う必要があり、要素数に比例して要素の追加・削除に処理負荷がかかります。
あらかじめ一定のメモリ領域が確保されるため、その範囲内で追加・削除を行う分には問題ありませんが、範囲を超える拡張を行う場合には処理負荷がかかります。
このため、ArrayListを使う場合は想定されうる最大の領域分を、あらかじめ確保することが重要です。
また、指定したn番目の要素をランダムに参照するといった操作であれば、高速に実行できます。

LinkedListは、各データの要素を連結させたリスト構造を持つ配列です。

要素の追加・削除が発生しても前後の要素のリンクを付け替えれば良いので、要素数にかかわらず処理負荷がほぼ一定です。
逆に、リストに格納された個々の要素が何番目に存在するか？というのは実際にリンクをたどってみないと分かりません。
このため、指定したn番目の要素の位置をランダムに参照しようとすると、リストの大きさに比例した時間がかかります。

これらの違いを踏まえて、以下のような使い分けが良いかと思います。

ArrayList：配列の要素へのランダムアクセスが必要で、要素の追加・削除の操作があまり発生しない場合
LinkedList：配列の要素へのランダムアクセスが不要で、要素の追加・削除の操作が頻繁に発生する場合