ArrayListとLinkedListの違い

今まではArrayListしか使ってこなかったのですが、
用途によって使い分けられるようになれなければ、と思いました。

• ArrayList
  • 要素を配列で保持している
    • 配列がメモリ上でインデックス化されている
      • インデックスの修正、コピーに対するコストが要素数に比例して大きくなる
      • 要素がメモリ上のインデックスに保管されているため、n番目の要素へのアクセスが早い

• LinkedList
  • 要素を数珠つなぎに保持している
    • 前後の要素に対するリファレンスを保持している
      • 要素の追加、削除はリファレンスの変更のみでOKのため、コストが一定
      • ある要素が何番目かが分からないため、n番目の要素に対して1から順にたどる必要がある

＜まとめ＞
ArrayListに適した用途

• 配列内の要素に対してランダムなアクセスを必要とする場合
• 配列内の要素に対して挿入／削除の操作があまり必要ない場合

　⇒　データベースからデータを大量に読み込み、以後それを順に参照しつつ複雑な計算を行うような場合

LinkedListに適した用途

• 配列内の要素に対してランダムなアクセスを必要としない場合
• 配列内の要素に対して挿入／削除の操作を頻繁に行う場合

　⇒　プログラム中で発生するデータの入れ物として使われ、時折データベースへ書き出してデータの永続化が図られるような用途