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は

```java:ArrayList.java(134行目あたり)
 transient Object[] elementData; // non-private to simplify nested class access
```
っていうのが要素の実態で、この配列に対して

```java:ArrayList.java(457行目あたり)
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
```

```java:ArrayList.java(428行目あたり)
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
```

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

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

```java: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までノードをたって行く形ですね。

```java: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文

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

2: Iterator

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

3: 拡張for文

```java
for(Object o : list) {
}
```

4: foreach (Java8から)

```java
list.forEach(o -> { });
```

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

```java
for(Object o : list) {
    System.out.println(o.toString());
}
```
これが

```java
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](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/Iterable.java#Iterable.forEach%28java.util.function.Consumer%29)に実装されてます。

```java:Iterable.java(72行目くらい)
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}
```

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

```java: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などのイテレーションの方法についてもパフォーマンスの計測などを行って、その特性を調べました。

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