先日ArrayListとLinkedListの違いわかるかと聞かれて、答えることができなかったので備忘録として記事します。
ArrayListとは
ArrayListは、内部的には配列を利用したリスト構造です。標準的な配列と異なる点は、サイズを後からでも変更できる点です。その性質上、インデックス値による値の読み書きは高速ですが、要素の挿入／削除は、配列サイズが大きくなるほど、また、操作位置が先頭に近くなるほど遅くなります。
・メリット
要素がそれぞれ順序番号を持っており、全てメモリ上でインデックス化されているため、特定の要素へすぐにアクセスすることが出来ます。
・デメリット
末尾意外の要素を足したり引いたりすると、それ以降の要素全ての順序番号を繰り上げたり繰り下げたりするための再配置処理が行われ、
その処理により ArrayList 内の要素には全て 0 から 全要素数から 1 引いた数までの全ての順序番号が付けられた要素がキレイに並び続けるのですが、処理が行われる分時間がかかってしまいます。
そしてその処理数は要素数に比例して多くなります。
| メソッド | 概要 |
|---|---|
| add([int index,] E e) | 指定位置indexに要素eを挿入（index省略で末尾に挿入） |
| clear() | リストからすべての要素を削除 |
| contains(Object e) | リストに要素oが含まれているかを判定 |
| get(int index) | be |
| indexOf(Object e) | 要素oが登場する最初のインデックス値を取得 |
| isEmpty() | リストが空か判定 |
| remove(int index｜Object o) | 指定の要素を削除 |
| set(int index, E e) | index番目の要素を設定int size() |
| int size() | リストに含まれる要素の数を取得 |
LinkedListとは
LinkedListは、要素同士を前後双方向のリンクで参照するリンクリストを表します。その性質上、要素の挿入／削除はリンクの付け替えで済むため、ArrayListに較べても高速です。反面、インデックス値によるランダムなアクセスは苦手であるという性質を持ちます。このような理由から、挿入／削除操作が多い状況ではLinkedListを、それ以外の場合はArrayListを使う、という使い分けになるでしょう。
LinkedListクラスで利用できるメソッドは、ArrayListと同じですので、そちらも合わせて参照してください。以下は、LinkedListで要素をセットし、その内容を順に読み込む例です。
・メリット
要素を足したり引いたりする際は、リンク情報を書き換えれば終わりなので、再配置処理が行われない分 ArrayList よりも高速です。
・デメリット
それぞれの要素は順序番号を保持していないため、特定の要素を取り出す際は、先頭もしくは末尾から一つずつ順序を数えていく必要があるため、順序番号があらかじめ保持されている ArrayList に比べると、それだけ多くの時間がかかります。
結論
ArrayListは要素に対してランダムなアクセスを必要とし、配列内の要素に対して挿入／削除の操作があまり必要ない場合に利用。
LinkedListは末尾の要素以外に追加/削除処理を頻繁に必要とし、特定の要素に対するアクセスが必要としない場合に利用。