LinkedList
https://docs.oracle.com/javase/jp/8/docs/api/java/util/LinkedList.html
ArrayListと対になる存在で、連結リストと呼ばれる。
構造が違うためパフォーマンスが異なる。
クラス名 | 要素の検索速度 | 要素の追加削除速度 |
---|---|---|
ArrayList | 高速 | 低速 |
LinkedList | 低速 | 高速 |
ArrayList
連続して要素を並べることで順序を保持しています。
そのため、要素の追加や削除が行われると後ろの要素を1つずつ玉突き方式で移動させていきます。
この処理が遅く、ArrayListの要素の追加削除速度が遅い原因になります。
A,B,C,D の4つの要素からBを消した場合、CとDは一つ前に移動する処理が発生します。
LinkedList
次はどの要素かという情報を持つことで順序を保持しています。
そのため、要素の追加や削除が起きても「次はこの要素だ」という情報を書き換えるだけでよくなり高速です。
その一方、「○番目」という情報を持っていないためデータの取得時には先頭から対象まで全て数える必要があります。
この処理が遅く、LinkedListの要素の検索速度が遅い原因になります。
A,B,C,D の4つの要素からBを消した場合、Aの次の要素情報をCに書き換える処理が発生します。
使い分け
一度データを登録して、あとは読み取るだけであれば ArrayList
何度もデータの書き換えが発生するならば LinkedList
と使い分けすればよりよりプログラムになりそうです。