パンくず
書籍 パーフェクトJava
リスト
概要
Javaのリストについて
Listのインターフェース
| 項目名 | 処理内容 |
|---|---|
| add | 要素の追加 |
| contains | 要素の存在チェック |
| get | 要素の取得 |
| indexOf | 要素の検索 |
| lastIndexOf | 要素の検索（後方から） |
| remove | 要素の削除 |
| set | 要素の置換 |
| size | 要素数の取得 |
ArrayListについて
標準的なリスト。
連続領域にデータを確保する。
予め領域のサイズが予想できる場合は、初期サイズを指定しておくことで
リストの再構築コストがなくなり高速になる。
デフォルトでは要素数10。
利点
・index指定による読み出しが速い
・index指定による書き換えが速い
連続領域でメモリを確保し、リストのサイズ×指定要素によるアクセスを行うことで
どの要素にアクセスする際も全く同じコストでアクセスすることが出来るため高速です。
欠点
・挿入が遅い（特にデータ量が多く、最初に要素を追加する場合）
・削除が遅い（特にデータ量が多く、最初に要素を削除する場合）
連続領域のデータを全て後ろに一つずつずらす必要があるため低速です。
LinkedListについて
リンク構造のリスト。
バラバラの領域にデータを確保し、それぞれ前要素・次要素へのリンクを持つ。
任意の位置の要素にアクセスする場合はリンクを辿っていくため処理が遅い。
内部実装ではNが真ん中より大きいか小さいかにより最初から辿るか、
後ろから辿るか決定されるため、真ん中に近い要素ほど処理が遅くなる。
要素の追加や変削除時は前後のリンクを付け直すだけでいいため高速。
※利点と決定はArrayListの逆
利点
・挿入が速い
・削除が速い
欠点
・index指定による読み出しが遅い
・index指定による書き換えが遅い
