業務で ArrayList を使っていたところ
ここは LinkedList を使ったほうがいいよ
と先輩にアドバイスを貰いました。
LinkedList を実装するにあたり、それぞれ業務で使う上での長所と短所、加えてそれぞれがどのような仕組みになっているのか、理由を調べてみたのでまとめます。
それぞれの長所と短所と使い所
ArrayList
- 長所と短所
- 特定の要素にアクセスするスピードが早い
- 要素を追加するスピードが遅い
- 使い所
- 配列内の要素に対してランダムなアクセスを必要とし、配列内の要素に対して挿入／削除の操作があまり必要ない場合
- 例えば... データベースからデータを大量に読み込み、以後それを順に参照しつつ複雑な計算を行うような場合
LinkedList
- 長所と短所
- 要素を追加したり削除するスピードが早い
- 特定の要素にアクセスするスピードが遅い
- 使い所
- 配列内の要素に対してランダムなアクセスを必要とせず、配列内の要素に対して挿入／削除の操作を頻繁に行う場合
- 例えば... プログラム中で発生するデータの入れ物として使われ、時折データベースへ書き出してデータの永続化が図られるような用途
そもそも ArrayList ってどんな仕組みになってるの?
ArrayListクラスはListインターフェースを実装したクラスで、要素が順序をもった配列として実装されたコレクションです。
要素がそれぞれ順序番号を持っており、全てメモリ上でインデックス化されているため、特定の要素へすぐにアクセスすることが出来ます。
それぞれの要素が保持している順序番号が要素へのアクセスを高速にする一方、それが裏目にでる事もあります。
末尾意外の要素を足したり引いたりすると、それ以降の要素全ての順序番号を繰り上げたり繰り下げたりするための再配置処理が行われます。
その処理により ArrayList 内の要素には全て 0 から 全要素数から 1 引いた数までの全ての順序番号が付けられた要素がキレイに並び続けるのですが、処理が行われる分時間がかかってしまいます。
そしてその処理数は要素数に比例して多くなります。
LinkedList の仕組みは?
ArrayList の要素が順序番号を伴った配列として保持されている一方、LinkedList では要素同士が、それぞれ前後に持っているリンク情報で繋がっています。
それぞれの要素は順序番号を保持していないため、特定の要素を取り出す際は、先頭もしくは末尾から一つずつ順序を数えていく必要があるため、順序番号があらかじめ保持されている ArrayList に比べると、それだけ多くの時間がかかります。
一方要素を足したり引いたりする際は、リンク情報を書き換えれば終わりなので、再配置処理が行われない分 ArrayList よりも高速です。