ArrayList と LinkedList の使い分け

java.util.List は、Java プログラミングの中でも頻繁に使用します。特に List の中でも、java.util.ArrayList を使う場面は結構あります。

しかし、List を実装したクラスとして、java.util.LinkedList もあります。

ということで、ArrayList と LinkedList の使い分けをメモしておきます。

ArrayList を使う場合

ArrayList は java.util.RandomAccess を実装しています。

RandomAccess インタフェースを実装しているリストは、ランダムアクセス（適当な位置の要素にアクセスする処理）を行った場合に、一定時間内に要素へアクセスできることを保証しています。

つまり、ランダムアクセスが行われる可能性がある場合は、 ArrayList を使います。

ただし、 ArrayList には弱点もあります。

ArrayList の内部は配列になっています。そのため、要素の追加や削除を行うと、配列の挿入部分を確保するためや空き部分を埋めるために、他の要素の移動を行います。また、あらかじめ指定した容量を超えて要素を追加すると、超えた分量を格納できるだけの配列を新たに生成します。

さらに、大きいオブジェクトを扱う際には、余分な空き領域も大きくなってしまいます。

そのため、大量に要素の追加・削除を行う場合には、処理が遅くなることがあります。

LinkedList を使う場合

ArrayList に対して LinkedList は RandomAccess インタフェースを実装しません。

その代わり、要素の追加・削除には強い構成となっています。

LinkedList の内部はリスト構造になっています。要素ごとに前の要素と後ろの要素を記録することでリストを構成しているため、前後になる要素の記録をいじれば追加や削除は完了します。また、ArrayList のように余分な空き領域はできません。

ただし、先頭や最後尾以外の要素にアクセスする場合は、要素を一つずつ辿っていく必要があります。つまり、ランダムアクセスを行う場合には処理に時間がかかります。

そのため、要素の追加・削除を大量に行う場合でランダムアクセスを行う可能性が低い場合は、 LinkedList を使います。最終的にどれだけの要素を追加するのか不透明な場合や大きなオブジェクトを扱う際には特に有効でしょう。

リストの受け渡しは List で

今回の記事では、 ArrayList と LinkedList の使い分けについてメモしました。

しかし、次のようなコードは避けたほうが無難です。

public LinkedList createList() {
    // リストの生成処理
}

public void execute(ArrayList list) {
    // リストで何か処理
}

もしも、createList で生成されるリストを ArrayList に変更した場合はどうなるでしょうか。createList で生成されたリストを受け取る側のコードも変更する必要が出てくるかもしれません。

また、 execute メソッドに LinkedList を渡したい場合はどうすればよいでしょうか。わざわざ LinkedList から ArrayList に要素を格納し直すのは大変です。

冒頭の通り、ArrayList や LinkedList は List インタフェースを実装しています。ですので、次のようにすれば ArrayList や LinkedList を意識せずにリストをやりとりできます。

public List createList() {
    // リストの生成処理
}

public void execute(List list) {
    // リストで何か処理
}

ただし、そのリストに特有のメソッドを使いたい場合や、処理速度・メモリ容量を意識する場合は、あえて ArrayList や LinkedList でやりとりする必要があります。

ちなみに、List は java.util.Collection を実装しています。もしも、リストだけでなくセット（java.util.Set）も扱えるのであれば、Collection でやりとりするのもいいかもしれません。