ArrayListとLinkedListの性能比較

メモリ使用量

　1000万回、1文字をaddした時のメモリ使用量を計測

　　ArrayList
      

　　LinkedList
      

　　【結果】
　　　ArrayListが89,863KB(約87MB)のメモリ使用量に対し、LinkedListは234,929KB(約229MB)もメモリを使用。
　　　メモリ使用量的にはArrayListの方が効率的。


追加(add)の速度

　1000万回、1文字をaddした時の速度を計測

　　ArrayList
      
　　1回目　455ミリ秒
　　2回目　433ミリ秒
　　3回目　446ミリ秒
　　 平均　 444ミリ秒

　　LinkedList
      

　　1回目　2092ミリ秒
　　2回目　2054ミリ秒
　　3回目　2056ミリ秒
　　 平均　 2067ミリ秒

　　【結果】
　　　ArrayListは約444ミリ秒でaddが完了。
　　　LinkedListは約2067ミリ秒でaddが完了。
　　　ArrayListの方が4倍以上も早い結果に。
　　　addの速度的にもArrayListの方が効率的。


挿入(add)の速度

　1000万件追加されているリストに対して、任意で指定したインデックスへ1万回addした時の速度を計測

　　ArrayList
      
　　1回目　51024ミリ秒
　　2回目　49430ミリ秒
　　3回目　51319ミリ秒
　　 平均　 50591ミリ秒

　　LinkedList
      

　　1回目　50540ミリ秒
　　2回目　48622ミリ秒
　　3回目　48304ミリ秒
　　 平均　 49155ミリ秒

　　【結果】
　　　ArrayListは約50秒でaddが完了。
　　　LinkedListは約49秒でaddが完了。
　　　若干ではあるが、LinkedListの方が早い。
　　　※今回は1万件で1秒差。addするデータ件数が増えれば増えるほど差は大きくなると思われる。


取得(get)の速度

　1000万件追加されているリストから、10万回getした時の速度を計測

　　ArrayList
      
　　1回目　1ミリ秒
　　2回目　1ミリ秒
　　3回目　1ミリ秒
　　 平均　 1ミリ秒
　　 ※100万回で9ミリ秒

　　LinkedList
      

　　1回目　3591ミリ秒
　　2回目　3582ミリ秒
　　3回目　3570ミリ秒
　　 平均　 3581ミリ秒

　　【結果】
　　　ArrayListは一瞬でgetが完了しているのに対し、LinkedListは約3秒かかっている。
　　　圧倒的にArrayListの方が早い。
　　　※LinkedListはIteratorのnextで値を取得すると高速。しかし、ArrayListのIterator.nextと大差ない処理速度。


更新(set)の速度

　1000万件追加されているリストに対し、10万回setした時の速度を計測

　　ArrayList
      
　　1回目　2ミリ秒
　　2回目　2ミリ秒
　　3回目　2ミリ秒
　　 平均　 2ミリ秒

　　LinkedList
      

　　1回目　21100ミリ秒
　　2回目　19742ミリ秒
　　3回目　19758ミリ秒
　　 平均　 20200ミリ秒

　　【結果】
　　　ArrayListは一瞬でsetが完了しているのに対し、LinkedListは約20秒かかっている。
　　　圧倒的にArrayListの方が早い。


削除(remove)の速度

　1000万件追加されているリストから、1万回removeした時の速度を計測

　　ArrayList
      
　　1回目　54337ミリ秒
　　2回目　53236ミリ秒
　　3回目　56006ミリ秒
　　 平均　 54526ミリ秒

　　LinkedList
      

　　1回目　359ミリ秒
　　2回目　374ミリ秒
　　3回目　397ミリ秒
　　 平均　 376ミリ秒

　　【結果】
　　　ArrayListは約54秒かかっているのに対し、LinkedListは約376ミリ秒で完了。
　　　圧倒的にLinkedListの方が早い。
　　　※clearメソッドで全件削除する場合は、どちらも一瞬で完了するが、ArrayListの方が高速。


結論
　LinkedListは、要素間に値を追加、削除するような操作が多い時に使うとよい。
　特にremoveが多い場合は効果絶大。
　逆に言うと、remove操作が無い場合はLikedListを使う必要性は無い。


戻る