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

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

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

コレクションとは何なのか？

• モノの集まりを表現するモノであり、かつ、モノの集まりに対する操作を提供するモノ

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

• コレクションの共通操作をインターフェースとしてまとめ、個別のデータ構造やアルゴリズムを（インターフェースを実装した）具象クラスとして提供する。
• 開発者は決められた操作に従ったメソッド呼び出しをするだけで、データ構造やアルゴリズムの詳細を気にすることなく利用できる。

どんな種類があるのか？

• リスト
• マップ
• セット
• スタック、キュー、デック

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

リストとは？

• 順序通り並んだ集まり（シーケンスと呼ぶ流儀もあるらしいです。）

主なメソッド

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

リストの具象クラス

• ArrayList
  • 内部的には配列を使ったデータ構造

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

• LinkedList
  • リンクでノードを繋ぐデータ構造

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

それぞれの特徴

ArrayListの特徴

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

メモリ使用量という観点

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

LinkedListの特徴

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

リストの具象クラスの使い分け

• 要素の読み込みが中心（要素全てをなめる処理や検索）の場合、ArrayListの方が効率的
• 要素の挿入や削除の頻度が高い場合、LinkedListの方が効率的
• 要素の書き換え処理が多い場合、ArrayListの方が効率的

追加調査（ソートに関して）

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

リストはなるべくimmutableで使用すべき？(ここからは個人の意見です)

immutableとは？

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

まとめ

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

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