More than 3 years have passed since last update.

Javaのコレクションの特徴〜List編〜

Posted at 2021-04-30

業務でJavaのコレクションをよく触るが、なんとなくの理解で終わってしまっていたので、本を読んで特徴をまとめてみました。
ここに書いてあるのはパーフェクトJava の内容と実際に自分が業務で使っている際の感想になります。

コレクションフレームワーク

今回はリストについてまとめています。

メソッド名	意味	個人的な使用頻度
add	要素の追加	低
addAll	要素をまとめて追加	低
contains	要素の存在チェック	高
get	要素の取得	高
indexOf	要素の検索	低
lastIndexOf	要素の検索（後方から）	低
remove	要素の削除	中
set	要素の置換	低
size	要素数の取得	高
subList	部分リストの取得（要素コピーはせずに要素を共有した部分リストを返す）	低

List<String> fruitList = new ArrayList<>(Arrays.asList("Apple", "Grape", "Orange"));

List<String> fruitList = new LinkedList<>(Arrays.asList("Apple", "Grape", "Orange"));

良い点
- インデックスを指定して要素を読み出す速度が速い[get]
- インデックスを指定して要素を書き換える速度が速い[set]
- 上記から導かれる特徴で、先頭から順に全ての要素をなめる処理が早い
悪い点
- 要素の挿入が遅いことがある(先頭に近い位置への挿入は遅い。末尾に近い位置への挿入は早い時もあるが、遅い時もある)[add]
- 要素の削除が遅いことがある(先頭に近い位置の削除ほど遅く、末尾に近い位置の削除ほど早い。最末尾の削除は高速)[remove]
- 条件に合致した要素を検索する処理の速度はあまり早くない（工夫によりかなりはやくもできる）[contains,indexOf,lastIndexOf]

ArrayListは連続したメモリ領域を使いうため、一度確保した連続メモリ領域のサイズを容易に広げられない場合、新しい連続メモリ領域を確保してそこに古い領域のデータをコピーする挙動になる。そのため、たとえ末尾への要素の挿入であっても上述のコピー処理がとても重くなる可能性があるので注意が必要となる。解決策としては、予め要素数の上限を確保しておくことが挙げられる。
ただ個人的にリストの実装時はなるべくimmutableな実装をするべきだと考えているので、そちらを意識していれば上記の問題にぶち当たることも少なくなるかと思います。

良い点
- 要素の挿入が早い(ただし多くの場合、挿入の前に検索があることに注意)[add]
- 要素の削除が早い(ただし多くの場合、削除の前に検索があることに注意)[remove]
悪い点
- インデックスを指定して要素を読み出す速度はあまり速くない[get]
- インデックスを指定して要素を書き換える速度はあまり速くない[set]
- 条件に合致した要素を検索する処理の速度はあまり速くない[contains,indexOf,lastIndexOf]

ソートの処理はArrayListの方が早い
- 理由としてはLinkedListはソートの内部処理として1度Javaの配列に置換して、ソートするのに対してArrayListはそのままの状態でソートするため。（参考：ArrayList vs LinkedList: Sort, Get and Iteration）

immutableとは不変という意味です。そのためimmutableなリストは作成後に変更されることがありません。
- メリットとしては、immutableなリストを使用することで状態の変化によるリスクを気にする必要がなくなります。
リストの要素を変えてしまうと予想外の操作の影響を受け、バグを生じさせてしまう可能性が上がるため、set等の書き換えのメソッドはなるべく使わないようにした方が安全性という観点で良いです。
ただ一方で、要素を追加したい時もリストを作り直すことになるので、パフォーマンスに影響を与えることもあります。そのためパフォーマンスを追求しなければならない状況ではいまいちなこともあります。なので、状況に応じて使い分けは必要ではありますが、基本的にはオブジェクト同様にimmutebleなリストを扱うのが良いかと思います。
immutableなリストの作成方法は以下の記事がわかりやすかったので、ぜひ参照してください。
- https://qiita.com/kageryosan/items/b1699b477a9bf325c2ce

いろいろ書きましたが、なんだかんだ基本的にはimmutebleなArrayListを使う機会が一番多くなりそうだなと調べながら感じました。ただ、要素の挿入削除などが主の操作になるパターン（BEの処理だとあまりこんなケースはなさそうですが）に関してだけはLinkedListを使っていくべきみたいです。
あと、contains（存在チェック）とかは思ったより早い処理ではないなと感じたので、チェック→取得みたいなことはせずに直接取得してなかったら〜みたいな処理を書いたほうが効率的になるなぁという学びがありました。

次はMapについて書こうと思います。