JavaのListについて

#この記事の目的
Javaには便利に使えるコレクションがたくさんあります。ListやSetなんかがその代表だと思いますが、それぞれの実装によって、挿入は早いけどアクセスは遅いなど、いろいろと特徴があると思います。この記事ではJavaの実装を見ながら、そこらへんの基本的なところをおさらいしようと思います。
今回はコレクションでも多分最もよく使うであろうList系、特にArrayListとLinkedListに絞って調べていきます。
ソースコードは
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList
および
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/LinkedList.java#LinkedList.Node
から引用してます。

#ArrayListとLinkedListの違い
中でのデータの持ち方が違います。
ArrayListは内部にObjectの配列を持っていて、要素はそこに格納されます。LinkedListは要素をNodeに格納し、それを連結することで順序付きのコレクションを実現しています。

ArrayListは

ArrayList.java(134行目あたり)

 transient Object[] elementData; // non-private to simplify nested class access

っていうのが要素の実態で、この配列に対して

ArrayList.java(457行目あたり)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ArrayList.java(428行目あたり)

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

こんな感じでaddしたりgetしたりしてます。
add内で呼ばれているensureCapacityInternalで格納している配列のサイズをチェックして、領域を超えるようだったら更にgrowメソッドを呼び出して、配列を拡張しています。デフォルトでは既存のサイズの1.5倍になるみたいです。

一方、LinkedListは内部クラスでこういうのを持ってます。

LinkedList.java(970行目あたり)

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

このノードは次のノードへの参照と前のノードへの参照を保持してます。
で、LinkedList自体はNodeのfirstとlastを保持してます。
こういう感じで頭、もしくはおしりの方から目的のindexまでノードをたって行く形ですね。

LinkedList.java(566行目あたり)

 Node<E> node(int index) {
// assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

こういう特性を持っているので、一般的にアクセス時間はArrayListの方が圧倒的に早いです。ここらへんはArrayListがマーカーインタフェースでRandomAccessを持ってるあたり、明示的ですね。
ただし、ArrayListはリストの途中に要素を挿入する場合、配列をSystem.arraycopyを用いて配列を複製します。なので、そういう時はLinkedListを使いましょう。

#for, 拡張for, foreachなど
Listの要素をすべてたどるのによくforとか使うけど、書き方がいろいろありますよね。ざっと見たところ、下の4つに分けられると思います。

1: for文

for(int i=0; i<list.size(); i++) {
    list.get(i);
}

2: Iterator

Iterator itr = list.iterator();
while(itr.hasNext()){
    itr.next();
}

3: 拡張for文

for(Object o : list) {
}

4: foreach (Java8から)

list.forEach(o -> { });

今回はこの４つの実装、パフォーマンスについても調べました。
1については今更言う必要ないと思います。
2のIteratorの実装ですが、大体はIteratorをimplementsした内部クラスを持っていて、その中で現在位置を保持するcursorを管理してるみたいです。特に、LinkedListの場合はgetで要素にアクセスしようとした場合、リストの先頭（もしくは最後尾）から探索を開始するので、このIteratorを使ったアクセスのほうが圧倒的に早いです。
3のいわゆる拡張for文ですが、]この記事によると、これはこんな風に動作するらしいです。

for(Object o : list) {
    System.out.println(o.toString());
}

これが

Object o;
for(Iterator it = list.iterator(); it.hasNext(); System.out.println(o.toString()) {
    o = it.next();
}

こうなる。
つまり、内部的にIteratorを呼び出してくれています。拡張for文を使うとIteratorを使った呼び出しが簡単に書けるようになります。

4のforEach。これはjava8から追加された書式です。引数にConsumerを受け取って、各要素に適用していきます。
このforEachですが、そもそもはIterableに実装されてます。

Iterable.java(72行目くらい)

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

つまり、デフォルトでは普通に拡張for文使ってますね。
ちなみに、ArrayListではこのforEachがOverrideされて、以下のようになってます。

ArrayList.java(1241行目くらい)

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

並列アクセスの例外処理系を除くと、１の普通のfor文で要素にアクセスする方法をとってることがわかります。ArrayListはRandomAccessなので、Iteratorを使って要素にアクセスするよりも普通にgetを使ったほうがアクセスが早いので、こういった実装になってるんだと思います。

最後に、せっかくなのでこの４つの方法についてパフォーマンスの計測をしました。対象はJava8のLinkedListとArrayList。検証環境はMacBook Air(11inch) 1.7GHz Core i7 / 8GB RAMです。長さを1000に固定したリストについて、それぞれ全要素へのアクセスを30000回繰り返し、その速度を測定しています。
結果は以下のとおりです。

	LinkedList	ArrayList
for	15020ms	25ms
Iterator	115ms	27ms
拡張for	121ms	22ms
forEach	142ms	101ms

概ね想定通りの値に落ち着いてると思います。Iteratorと拡張forの値がずれてるのが気になりますが、ここらへんは誤差でしょうか？？forEachについてはLambdaを呼び出すオーバーヘッドと捉えていいんでしょうか。こういった値になりました。

##コメントを頂いたので追記。
確かにこれだとLinkedList使えねー、てなりますね。でもArrayListよりもLinkedListが有利なケースはあります。それがリストの途中に要素を挿入するケースですね。
というわけで、リストの途中に要素を挿入し、それを30000回繰り返してパフォーマンスも計測してみました。
結果は以下のとおりです。

	LinkedList	ArrayList
	7ms	88ms
というわけで、圧倒的にLinkedListの方が早いという結果になりました。

#まとめ
ArrayListとLinkedList、Javaで最も使う２つのリストについて、基本的な特性を調べました。ついでに、for, 拡張forなどのイテレーションの方法についてもパフォーマンスの計測などを行って、その特性を調べました。

指摘、コメントなどなどありましたら、ぜひおねがいします！