【Java】ArrayListとLinkedListの速度比較

備忘録
目次

はじめに

Javaのリストである、ArrayListとLinkedListの処理速度を計測し、性能を比較してみました。

計測

add（追加位置：指定なし＝最後）

“a”という文字列をそれぞれ1000万回追加して比較してみました。
追加位置は指定せず、リストの最後に追加しています。

List<String> arrayList = new ArrayList<>();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    arrayList.add("a");
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
long start2 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    linkedList.add("a");
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 172ms
LinkedList: 1265ms

ArrayListのほうが速いです。

add（追加位置：先頭）

“a”という文字列をそれぞれ100万回追加して比較してみました。
addの第1引数には0を指定し、リストの先頭に追加しています。

List<String> arrayList = new ArrayList<>();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
    arrayList.add(0, "a");
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
long start2 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
    linkedList.add(0, "a");
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 54978ms
LinkedList: 18ms

LinkedListのほうが速いです。

add（追加位置：最後）

“a”という文字列をそれぞれ1000万回追加して比較してみました。
addの第1引数にはリストの要素数を指定し、リストの最後に追加しています。

List<String> arrayList = new ArrayList<>();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    arrayList.add(arrayList.size(), "a");
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
long start2 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    linkedList.add(linkedList.size(), "a");
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 156ms
LinkedList: 1359ms

ArrayListのほうが速いです。

add（追加位置：ランダム）

“a”という文字列をそれぞれ10万回追加して比較してみました。
addの第1引数には0からリストの要素数までの値を指定し、ランダムな位置に追加しています。

List<String> arrayList = new ArrayList<>();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.add((int) (Math.random() * arrayList.size()), "a");
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.add((int) (Math.random() * linkedList.size()), "a");
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 234ms
LinkedList: 14356ms

ArrayListのほうが速いです。

contains

10万未満の正の整数のリストに対し、存在するランダムな値が含まれているかを10万回確認しています。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.contains((int) (Math.random() * arrayList.size()));
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.contains((int) (Math.random() * linkedList.size()));
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 3579ms
LinkedList: 11041ms

ArrayListのほうが速いです。

indexOf

10万未満の正の整数のリストに対し、存在するランダムな値が最初に検出された位置のインデックスを10万回取得しています。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.indexOf((int) (Math.random() * arrayList.size()));
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.indexOf((int) (Math.random() * linkedList.size()));
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 3766ms
LinkedList: 11487ms

ArrayListのほうが速いです。

lastIndexOf

10万未満の正の整数のリストに対し、存在するランダムな値が最後に検出された位置のインデックスを10万回取得しています。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.lastIndexOf((int) (Math.random() * arrayList.size()));
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.lastIndexOf((int) (Math.random() * linkedList.size()));
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 4116ms
LinkedList: 13237ms

ArrayListのほうが速いです。

get（取得位置：先頭）

1億件のリストから、先頭の要素を1億回取得しています。

List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 100000000; i++) {
    arrayList.add("a");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
    arrayList.get(0);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
for (int i = 0; i < 100000000; i++) {
    linkedList.add("a");
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
    linkedList.get(0);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 0ms
LinkedList: 0ms

両方とも非常に速いです。

get（取得位置：最後）

1億件のリストから、最後の要素を1億回取得しています。

List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 100000000; i++) {
    arrayList.add("a");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
    arrayList.get(arrayList.size() - 1);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
for (int i = 0; i < 100000000; i++) {
    linkedList.add("a");
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
    linkedList.get(linkedList.size() - 1);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 0ms
LinkedList: 0ms

両方とも非常に速いです。

get（取得位置：ランダム）

10万件のリストから、ランダムな位置の要素を10万回取得しています。

List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add("a");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.get((int) (Math.random() * 100000));
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add("a");
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.get((int) (Math.random() * 100000));
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 16ms
LinkedList: 4172ms

ArrayListのほうが速いです。

remove（削除位置：オブジェクト指定＝ランダム）

10万未満の正の整数のリストに対し、ランダムでリスト内の一致する要素を10万回削除します。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.remove(new Integer((int) (Math.random() * 100000)));
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.remove(new Integer((int) (Math.random() * 100000)));
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 3822ms
LinkedList: 15581ms

ArrayListのほうが速いです。

remove（削除位置：先頭）

100万件のリストから、先頭の要素を100万回削除します。

List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    arrayList.add("a");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
    arrayList.remove(0);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
for (int i = 0; i < 1000000; i++) {
    linkedList.add("a");
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
    linkedList.remove(0);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 54962ms
LinkedList: 0ms

LinkedListのほうが速いです。

remove（削除位置：最後）

1億件のリストから、最後の要素を1億回削除します。

List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 100000000; i++) {
    arrayList.add("a");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
    arrayList.remove(arrayList.size() - 1);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
for (int i = 0; i < 100000000; i++) {
    linkedList.add("a");
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
    linkedList.remove(linkedList.size() - 1);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 156ms
LinkedList: 446ms

ArrayListのほうが速いです。

remove（削除位置：ランダム）

10万件のリストから、ランダムな位置の要素を10万回削除します。

List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add("a");
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.remove((int) (Math.random() * arrayList.size()));
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<String> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add("a");
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.remove((int) (Math.random() * linkedList.size()));
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 218ms
LinkedList: 3391ms

ArrayListのほうが速いです。

set（置換位置：先頭）

1000万件のリストから、先頭の要素を1000万回置き換えます。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    arrayList.set(0, i);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10000000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    linkedList.set(0, i);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 141ms
LinkedList: 31ms

LinkedListのほうが速いです。

set（置換位置：最後）

1000万件のリストから、最後の要素を1000万回置き換えます。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    arrayList.set(arrayList.size() - 1, i);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10000000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
    linkedList.set(linkedList.size() - 1, i);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 125ms
LinkedList: 30ms

LinkedListのほうが速いです。

set（置換位置：ランダム）

10万件のリストから、ランダムな位置の要素を10万回置き換えます。

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.set((int) (Math.random() * arrayList.size()), i);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - start1) + "ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.set((int) (Math.random() * linkedList.size()), i);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - start2) + "ms");
ArrayList: 47ms
LinkedList: 4392ms

ArrayListのほうが速いです。

おわりに

ArrayListとLinkedListの処理速度を比較しました。
全体的にリストに対するランダムな操作はArrayListのほうが速いです。
先頭に近い要素に対する操作はLinkedListのほうが速いですが、そのような場面は少ないと思います。
デキュー(Deque)としての役割も兼ねたい場合以外は、無理してLinkedListを使わず、基本的にはArrayListを使うべきでしょう。

最新情報をチェックしよう！

備忘録の最新記事8件