[Java]List、Queue、Setのクラスメモ

Javaでコーディングを行う際に必ずと言ってもよいほど使用するコレクションについて、今まで使用したことがないものも含めて改めて学習したので備忘録としてまとめてみます。



# Listインターフェース

コレクションでよく使用するやつ。学習した3つの実現クラスについてまとめます。

## Arraylist
内部に配列を持っていて、あらかじめ要素数を決めておかなければならない配列とはことなり、要素数を必要に応じて増やすことが可能です。

要素数が増える場合、最初に内部で持っていた配列より大きな要素数を扱うことができる配列を新たに作成しそこに元の要素をコピーします。そのため、扱う要素数が増えていくにつれて処理が遅くなります。
具体的に言うと値の読み書きは高速ですが、要素の追加、削除は遅いです。



## LinkedList
要素それぞれが前要素の情報と後要素の情報を持っており、繋がっているリスト。各要素にアクセスする際には先頭から順に辿っていくことで要素にアクセスする。
そのためArrayListと比べて要素にアクセスする処理が遅くなります。一方、要素を追加する際にArrayListのように新たな配列を作成する必要がないので追加、削除は早いです。




## Vector
マルチスレッドでも安全に扱えるスレッドセーフなリスト。安全に扱えますがArraylistやLinkedListに比べるパフォーマンスは低いです。




## CopyOnWriteArrayList
こちらもListを実現したスレッドセーフなコレクション。
複数のスレッドでこのインスタンスを共有していて一方で要素の読み取り、一方で要素の追加が行うことができます。
Arraylistなどの場合、上記のようなことを実行しようとするとエラーが発生します。

```ArrayList.java
public static void main(String[] arg) throws Exception {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    new Thread(() -> {
      for(int i = 5; i < 1000; i++) {
        list.add(i);
      }
    }).start();;
    list.stream().forEach(System.out::println);
}
```
出力結果。別スレッドで要素追加中に本スレッドで要素の読み込みを行ったので例外発生。
``` 
--前半の要素出力部分は省略--
968
969
970
971
972
973
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1631)
	at java.base/java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:762)
	at test.test.main(test.java:29)
```

これをCopyOnWriteArrayListを使用すれば要素の追加、更新、削除時にはリストのコピーを作成して行うので安全に処理を実行することができます。

``` CopyOnWriteArrayList.java
public static void main(String[] arg) throws Exception {
    CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.stream().forEach(System.out::println);
    new Thread(() -> {
      for(int i = 5; i < 1000; i++) {
        list.add(i);
      }
    }).start();;
    list.stream().forEach(System.out::println);
  }
```
出力結果。要素の追加はコピー先で行っているので出力されるのは最初に追加した4つの要素のみ。
```
1
2
3
4
```

並列処理が終了した後に読み込みを行うと追加要素が反映されているので出力することができます。

``` CopyOnWriteArrayList.java
public static void main(String[] arg) throws Exception {
    CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    new Thread(() -> {
      for(int i = 5; i < 1000; i++) {
        list.add(i);
      }
    }).start();
    // 別スレッドが終了するまで待機する
    Thread.sleep(6000);
    list.stream().forEach(System.out::println);
  }
```
出力結果
```
--前半の要素出力部分は省略--
996
997
998
999
```


# Queueインターフェース

先入先出のデータ構造の機能を定義したインターフェース。文字通り最初に格納した要素を最初に取り出す構造になっています。

``` Queue.java
public static void main(String[] arg) throws Exception {
    Queue<Integer> queue = new ArrayDeque<>();
    for(int i = 0; i <= 10; i++) {
      queue.add(i);
    }
    queue.stream().forEach(System.out::println);
  }

```
出力結果
```
0
1
2
3
4
5
6
7
8
9
10

```


# Dequeインターフェース
先頭と末尾の両方から要素を追加ができて取り出すことができるコレクションです。

addFirstで先頭に要素を追加し、addLastで末尾に要素を追加します。

``` Deque.java
  public static void main(String[] arg) throws Exception {
    Deque<String> deque = new ArrayDeque<>();
    deque.addFirst("A");
    deque.addFirst("C");
    deque.addLast("D");
    deque.addLast("B");

    deque.stream().forEach(System.out::println);
  }
```

出力結果
```
C
A
D
B
```


# Setインターフェース
重複する要素を許可しないコレクションです。
重複している要素が追加されると上書きされるようになっています。

``` Set.java
public static void main(String[] arg) throws Exception {
    Set<String> set = new HashSet<>();
    set.add("A");
    set.add("B");
    set.add("C");
    set.add("D");
    set.add("A");
    set.stream().forEach(System.out::println);
}
```
出力結果。Aが重複しているので要素数が4つになっています。
```
A
B
C
D
```


何をもって重複していると判断するかは下記の2点を①からチェックしていき当てはまれば重複と判断しています。

①ハッシュコードが一致しているか
②equalsメソッドで戻り値がtrueになっているか


hashCodeメソッドとequalsメソッドをオーバーライドし意図的に重複していると判断されるクラスを作成して確かめてみましょう。

``` Sample.java
public class Sample {
  private String str;

  public Sample(String str) {
    this.str = str;
  }

  public String getStr() {
    return this.str;
  }

  @Override
  public int hashCode() {
    return 1;
  }
  @Override
  public boolean equals(Object obj) {
    return true;
  }
}

```

``` Set.java
  public static void main(String[] arg) throws Exception {
    Set<Sample> sample = new HashSet<>();
    sample.add(new Sample("A"));
    sample.add(new Sample("B"));
    sample.add(new Sample("C"));
    sample.add(new Sample("D"));

    sample.stream().forEach(s -> System.out.println(s.getStr()));
  }
```
出力結果。追加した全ての要素が最初に追加した要素Aと重複していると判断されAしか出力されていない。

```
A

```

## HashSet
要素の並び順を保証しないSet。並び替えをしない分、後続で記載するTreeSetに比べて処理が速いです。

## TreeSet
自然順序に並び替えるか引数で渡したComparatorのソート処理に従って並び替えを行うことができるSet。

``` TreeSet.java
  public static void main(String[] arg) throws Exception {
    Set<String> sample = new TreeSet<>();
    sample.add("D");
    sample.add("B");
    sample.add("A");
    sample.add("C");

    sample.stream().forEach(System.out::println);
  }
```
出力結果。自然順に要素が並び替えられて出力されている。

```
A
B
C
D
```

Comparatorを引数に渡した場合

``` TreeSet.java
public static void main(String[] arg) throws Exception {
    Set<Sample> sample = new TreeSet<>((s1, s2) -> s1.getName().compareTo(s2.getName()));
    sample.add(new Sample("Taro", 10));
    sample.add(new Sample("Ichiro", 33));
    sample.add(new Sample("Yuki", 40));
    sample.add(new Sample("Kanako", 20));

    sample.stream().forEach(s -> System.out.println(s.getName()));
  }
```



出力結果。引数で指定したアルゴリズムに基づいて並び替えられて出力されている。

```
Ichiro
Kanako
Taro
Yuki
```