Javaプログラミング-ArrayListとLinkedListの違い

JavaのList型にArrayListとLinkedListがある。
実際のプログラミングではどちらを使うのがよいのか。[壁]д･)？

◆ArrayList
データの持ち方：配列構造
データの参照：速い
データの更新：遅い

◆LinkedList
データの持ち方：リスト構造
データの参照：遅い
データの更新：速い

違いが出る理由としては、データの持ち方にある。（｀･ω･´）

ArrayListの配列構造は、データを最初から順番に参照していく処理は速いです。
逆に、データを削除や追加を行うと、配列の並べ替えが起きるので遅いのです。

（例）ArrayList[2]のDATA2を削除します。
  　   [0]         [1]          [2]         [3]          [4]
  [DATA0][DATA1][DATA2][DATA3][DATA4]
① DATA2を削除
     [0]          [1]          [3]         [4]
[DATA0][DATA1][DATA3][DATA4]
②[3][4]の配列を並べ替えます。
　 [3]のデータを[2]に、[4]のデータ[3]に移動します。
     [0]         [1]       [3→2]    [4→3]
[DATA0][DATA1][DATA3][DATA4]
この用に余計な処理が起きるのです。


LinkedListのリスト型構造は、データと次データの場所を保持しています。
このような構造をとる事で、チェーンのようにつないで全体のLinkedListとしての形をしている訳です。
順番に参照する動作など、任意の要素を参照する際は最初からたどらなくてはいけないため、時間が掛かります。
この時間はListの要素数に比例して時間が掛かります。
逆に削除、更新する際は、[次DATAの場所]を変更するだけですので、速いです。

（例1）DATA2の参照
 [DATA0]+[DATA1の場所]
                          →[DATA1]+[DATA2の場所]
                                                       →[DATA2]+[最後]
①DATA0のDATA1の場所を取得
②DATA1のDATA2の場所を取得
③DATA2を取得

（例2）DATA1を削除
 [DATA0]+[DATA1の場所]
                          →[DATA1]+[DATA2の場所]
                                                       →[DATA2]+[最後]
①DATA1を削除
 [DATA0]+[DATA1の場所]
                                                            [DATA2]+[最後]

②DATA0の[DATA1の場所]を[DATA2の場所]に変更
 [DATA0]+[DATA2の場所]
                          →[DATA2]+[最後]


二つのListには明確な違いがありますが、
どちらが悪くてどちらが良いというものではありません。
扱うデータによって変わるため、最適なListを選択してください。

Javaプログラミングではループ文でこれらのListを用いた時に、
処理速度に大きな違いがでてしまいますので、ご注意ください。


◆おまけ（´･ω･)ﾉ
実際のところIteratorパターンという考え方と、
Iteratorインタフェースがあり、
Listの違いなどを意識せず、ループを提供するものがあったりします。
Iteratorと拡張for文を合わせてLinkedListを使用するのが最近は多い気がします。
これをするとLinkedListの順に参照する速さはArrayListとそこまで変わらなくなり、
プログラムの安全も保たれたりします。
このことは次か、そのうち書きたいと思います。

興味があったら自分で調べると色々でてくるよ（´･ω･)ｂ