読者です 読者をやめる 読者になる 読者になる

かまたま日記3

プログラミングメイン、たまに日常

ArrayListとLinkedListの違い

Java

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

  • ArrayList
    • 要素を配列で保持している
      • 配列がメモリ上でインデックス化されている
        • インデックスの修正、コピーに対するコストが要素数に比例して大きくなる
        • 要素がメモリ上のインデックスに保管されているため、n番目の要素へのアクセスが早い
  • LinkedList
    • 要素を数珠つなぎに保持している
      • 前後の要素に対するリファレンスを保持している
        • 要素の追加、削除はリファレンスの変更のみでOKのため、コストが一定
        • ある要素が何番目かが分からないため、n番目の要素に対して1から順にたどる必要がある

<まとめ>
ArrayListに適した用途

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

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

LinkedListに適した用途

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

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