Tbpgr Blog

Ruby プログラマ tbpgr(てぃーびー) のブログ

書籍 パーフェクトJava | リスト ArrayListとLinkedList

パンくず

書籍 パーフェクトJava
リスト

概要

Javaのリストについて

Javaのリスト

順序どおり並んだ集まりを扱う場合、JavaではListを使用します。

Listのインターフェース

項目名 処理内容
add 要素の追加
contains 要素の存在チェック
get 要素の取得
indexOf 要素の検索
lastIndexOf 要素の検索(後方から)
remove 要素の削除
set 要素の置換
size 素数の取得

ArrayListについて

標準的なリスト。
連続領域にデータを確保する。
予め領域のサイズが予想できる場合は、初期サイズを指定しておくことで
リストの再構築コストがなくなり高速になる。
デフォルトでは要素数10。

利点

・index指定による読み出しが速い
・index指定による書き換えが速い
連続領域でメモリを確保し、リストのサイズ×指定要素によるアクセスを行うことで
どの要素にアクセスする際も全く同じコストでアクセスすることが出来るため高速です。

欠点

・挿入が遅い(特にデータ量が多く、最初に要素を追加する場合)
・削除が遅い(特にデータ量が多く、最初に要素を削除する場合)
連続領域のデータを全て後ろに一つずつずらす必要があるため低速です。

LinkedListについて

リンク構造のリスト。
バラバラの領域にデータを確保し、それぞれ前要素・次要素へのリンクを持つ。

任意の位置の要素にアクセスする場合はリンクを辿っていくため処理が遅い。
内部実装ではNが真ん中より大きいか小さいかにより最初から辿るか、
後ろから辿るか決定されるため、真ん中に近い要素ほど処理が遅くなる。

要素の追加や変削除時は前後のリンクを付け直すだけでいいため高速。

※利点と決定はArrayListの逆

利点

・挿入が速い
・削除が速い

欠点

・index指定による読み出しが遅い
・index指定による書き換えが遅い

ArrayListとLinkedListの使い分け

・読み込みや順次処理中心ならArrayList
・書き込みや削除中心ならLinkedList