JavaのArrayListとLinkedListの違いを理解して使い分ける

皆さん、こんにちは。技術開発グループのn-ozawanです。
先月末で今期入社の新人社員研修が終わり、今週から現場に配属されSE実務研修が始まりました。新人社員の皆様、新しい現場でも頑張ってください。

本題です。
ArrayListは、StringやSystemの次にJavaでよく使われるクラスかと思います。ArrayListはサイズが自動的に拡張する配列ですが、似たようなクラスにLinkedListがあります。ただLinkedListが使われているケースはあまり見かけませんよね。今回はArrayListとLinkedListの違いについてお話しします。

ArrayListとLinkedListの違い

ArrayList

ArrayListはサイズが自動的に拡張する配列です。本来、配列は定義時に指定した要素数を超えるデータを格納することは出来ません。ArrayListはもし配列の要素数を超えるデータを格納しようとしたときに、自動的に配列の要素数を拡張します。これにより配列の要素数を気にすることなくデータを格納することが出来ます。

LinkedList

LinkedListは要素同士を数珠繋ぎにしたリストです。配列ではありません。ArrayListと違い、データを末尾に追加したときは、末尾の要素と、追加した要素を繋ぎます。LinkedListも要素数の上限を気にすることなくデータを格納することが出来ます。

取得の違い

ArrayListは配列でデータを持ち、LinkedListは数珠繋ぎでデータを持つ、という違いがあります。では、このデータの持ち方により、具体的にどう違いが表れるのでしょうか。まずは取得処理から見ていきます。

特定のindexのデータを取得するとします。ArrayListは配列なので１ステップで該当のデータを取得することが出来ます。対してLinkedListはリストの先頭もしくは末尾からカウントしながら該当のデータを特定します。

ArrayListとLinkedListのそれぞれに100万件のデータを保持させて検証しました。先頭、中央(size / 2)、末尾のデータを取得する処理をそれぞれ1000回繰り返した結果が以下となります。

	先頭	中央	末尾
ArrayList	0ミリ秒	0ミリ秒	0ミリ秒
LikedList	0ミリ秒	1173ミリ秒	0ミリ秒

ArrayListはどこの要素を取得しても1ミリ秒にもなりません。LinkedListも先頭と末尾のデータを取得するのに0ミリ秒ですが、中央にあるデータを取得しようとすると1173ミリ秒もかかっています。これはLinkedListが、先頭もしくは末尾からカウントしながら該当のデータを探しているためです。

以上の結果から、リストのデータにランダムアクセスする場合は、LinkedListよりも、ArrayListのほうが　有利であることが分かります。

挿入の違い

挿入するときも違いがあります。ArrayListの場合、挿入したい要素より後ろの要素を、１つずらすようにコピーしてから、データを挿入します。それに対してLinkedListの場合、挿入したい要素の前後の要素と繋ぐだけです。

ArrayListは配列の拡張と、要素のコピー処理が発生します。これは配列の要素数が増えれば増えるほど、処理に時間を要することになります。対してLinkedListでは要素を繋ぎ変えるだけになります。

ArrayListとLinkedListのそれぞれに10万個のデータを挿入して検証しました。挿入個所は先頭、中央(size / 2)、末尾のそれぞれで試した結果が以下になります。

	先頭	中央	末尾
ArrayList	563ミリ秒	129ミリ秒	3ミリ秒
LikedList	5ミリ秒	5233ミリ秒	5ミリ秒

ArrayListを見ると、末尾にデータを挿入した場合は3ミリ秒かかるのに対し、先頭にデータを挿入した場合は563ミリ秒かかりました。これは要素のコピー処理に時間を要しているためです。

一方、LinkedListを見ると、先頭と末尾にデータを挿入した結果が同じ5ミリ秒となりました。これは単に要素を繋げているだけであり、ArrayListのようなコピー処理がないためです。ただし、中央にデータを挿入した場合は5秒以上かかっています。これはリストの中央にある要素を探すのに時間がかかっているためです。

予想外だったのが、ArrayListで末尾にデータを挿入したときの結果が、予想以上に速いことでした。１０年以上前に試したときは、LinkedListよりも遅かった記録があるのですが、今回は何回やってもLinkedListよりも早い結果になりました。ArrayListは要素が増えたタイミングで配列を拡張します。つまりメモリ領域の再確保が行われるため、LinkedListよりも遅くなると予想していました。この結果は、おそらく、メモリ関連の最適化などで、メモリ領域の確保スピードが向上したためLinkedListより早くなったと思われます。

削除の違い

削除では挿入の逆をします。ArrayListの場合、削除したい要素より後ろの要素を、１つ詰めるようにコピーして、最後の要素を削除します。LinkedListの場合、削除したい要素の前後の要素を繋げるだけです。

挿入の時と同じで、ArrayListの場合はコピー処理に時間を要します。対してLinkedListは要素間を繋ぎ変えるだけになります。

ArrayListとLinkedListのそれぞれに100万個のデータを保持して検証しました。先頭、中央(size / 2)、末尾のデータを削除する処理をそれぞれ1000回繰り返した結果が以下となります。

	先頭	中央	末尾
ArrayList	813ミリ秒	488ミリ秒	1ミリ秒
LikedList	2ミリ秒	14671ミリ秒	1ミリ秒

挿入の時と同じ傾向が表れていますね。理由も挿入時と同じなので説明は割愛します。

ArrayListとLinkedListの使い分け

従来、ArrayListは「追加や削除は遅いが、ランダムアクセスが高速」、LinkedListは「追加や削除は早いが、ランダムアクセスは低速」という特性から、ランダムアクセスが必要なときはArrayList、ソートした結果を格納して先頭からデータを読み込むなどの用途であればLinkedList、のような使い分けが言われていました。しかし、今日検証した結果、ArrayListの（末尾への）追加と削除が早くなっていることから、LinkedListの利用シーンが減ったなぁ、という印象を受けました。

LinkedListのいいところを強いて言うなら、メモリ効率の良さが挙げられるでしょう。ArrayListは多めに配列要素を確保します。対してLinkedListは必要な分のみ確保します。ArrayListは無駄なメモリを消費している場合がありますが、LinkedListは必要な分だけメモリを確保しているのです。

おわりに

今回の検証に利用したJava Runtimeは、Eclipse Temurin JDK 1.7 です。もしかしたら他のJDKでは結果が異なるかもしれません。似たようなクラスでも、きちんとその違いを理解して実装したいですね。

ではまた。