第 1 章: List

List には主に ArrayList と LinkedList が存在している. どちらも配列を扱う List だが, LinkedList の法が ArrayList に比べ挿入, 削除が高速である. よって頻繁に挿入や削除を行うことがわかっている場合, LinkedList を使うべき.

ArrayList と LinkedList の違いはパフォーマンスだけで, 使い方はどちらも同じ.

データの追加と取得

ArrayList1.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;
import java.util.List;

public class ArrayList1{
    public static void main(String[] args){
	List<String> myList = new ArrayList<String>();
	
	myList.add("China");
	myList.add("Japan");
	myList.add("America");
	myList.add("English");
	myList.add("Vietnam");

	System.out.println(myList);

	String s = myList.get(1);
	System.out.println(s);
    }
}

ArrayList1.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList1
[China, Japan, America, English, Vietnam]
Japan

解説:

List<String> myList = new ArrayList<String>();

この部分で String 型を格納することができる ArrayList “myList” を生成している. add 関数はデータを追加する際使用する.

データの取得する際は get 関数を使用する:

String s = myList.get(1);

を呼び出すことで, myList の 2 番目の要素を取り出している.

データ数の取得と削除

ArrayList2.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
import java.util.List;

public class ArrayList2{
    private static final String[] colors = {"RED", "GREEN", "BLUE", "BLACK", "WHITE"};

    public static void main(String[] args){
	List<String> myList = new ArrayList<String>();

	for(String color : colors){
	    myList.add(color);
	}

	System.out.println( "myList size is: " + myList.size() );
	System.out.println( "myList is: " + myList );

	myList.remove(3); // remove "BLACK" from myList
	myList.remove("WHITE");

	System.out.println("myList is: " + myList);
	    
    }
}

ArrayList2.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList2
myList size is: 5
myList is: [RED, GREEN, BLUE, BLACK, WHITE]
myList is: [RED, GREEN, BLUE]

解説:

for(String color : colors){
  myList.add(color);
}

この for-each 文は:

for(int i = 0; i < colors.length; i++){
  myList.add( colors[i] );
}

の省略形.

size 関数は要素数を取得する際使用する.

colors には五つの文字列が格納されているので, size 関数は 5 を返す.

remove は指定した要素を削除する関数:

myList.remove(3);

で, 4 番目の要素 “BLACK” を削除している. インデクスを指定する以外に:

myList.remove("WHITE");

としても要素を消すことができる.

要素に順次アクセスする方法その 1

ArrayList_Iterator2.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayList_Iterator2{
    public static void main(String[] args){
	List<String> myList = new ArrayList<String>();

	myList.add("Aさん");
	myList.add("Bさん");
	myList.add("Cさん");
	myList.add("Dさん");
	myList.add("Eさん");

	// 反復子の生成
	Iterator<String> i = myList.iterator();

	while(i.hasNext()){
	    String name = i.next();
	    System.out.println(name);
	}
    }
}

ArrayList_Iterator2.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList_Iterator2
Aさん
Bさん
Cさん
Dさん
Eさん

解析

追加した要素にアクセスする方法として次のコードが考えられる:

String name = myList.get(0);

このようにして, myList の先頭要素である “Aさん” という名前を取り出すことができる. しかし, データに順次アクセスしていく場合, get 関数を使用する方法は一般的ではない. 通常は, 反復子 (iterator) を介してコレクションの要素にアクセスしていく:

Iterator<String> i = myList.iterator(); // 反復子生成

ここで iterator のメソッドを紹介する:

boolean hasNext();

hasNext メソッドは次に要素が存在する場合 true を返し, そうでない場合は false を返す:

object next()

next メソッドは次の要素を返し, 返した後次の要素へ進む.

今回は, まず hasNext() メソッドで次の要素があるか確認し, ある場合は next() メソッドでその要素を取り出している.

要素に順次アクセスする方法その 2

Member.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Member{
    private String name; // Member の名前
    private int age; // Member の年齢

    public String getName(){
	return name;
    }

    public void setName(String name){
	this.name = name;
    }

    public int getAge(){
	return age;
    }

    public void setAge(int age){
	this.age = age;
    }

    public Member(String name, int age){
	this.name = name;
	this.age = age;
    }
}

ArrayList_Iterator.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayList_Iterator{
    public static void main(String[] args){
	List<Member> member = new ArrayList<Member>(); // HAS-A Relation

	// Member の登録
	member.add( new Member("feifei", 28) );
	member.add( new Member("yangyang", 8) );
	member.add( new Member("yangguang", 2) );
	member.add( new Member("kankan", 1) );

	// 反復子の生成
	Iterator<Member> i = member.iterator();
	while(i.hasNext()){
	    // 要素を返し, 次の要素へと進む
	    Member m = i.next();
	    System.out.print( "Name: " + m.getName() );
	    System.out.println( ", Age: " + m.getAge() );
	}
    }
}

ArrayList_Iterator.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList_Iterator
Name: feifei, Age: 28
Name: yangyang, Age: 8
Name: yangguang, Age: 2
Name: kankan, Age: 1

解説

Member クラスは name (名前) と age (年齢) の値を保持している:

member.add( new Member("feifei", 28) );

上記のコードで, member に 名前: feifei, 年齢: 28 歳という要素を追加している. 同様に yangyang, yangguang, kankan の情報も追加していく.

追加して要素にアクセスする方法として次のコードが考えられる:

String name = member.get(0).getName();

しかし, 通常は get 関数を使用せず, 反復子を介してコレクションの要素にアクセスしていく.

要素をソートする方法その 1

ArrayList_Sort.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ArrayList_Sort{
    public static void main(String[] args){
	List<String> myList = new ArrayList<String>();

	myList.add("Bさん");
	myList.add("cさん");
	myList.add("allen");
	myList.add("趙飛");
	myList.add("_wtopia");
	myList.add("Aさん");

	System.out.println( "unsorted: " + myList );

	// アルファベット順に sort する
	Collections.sort(myList);
	System.out.println( "sorted: " + myList );
    }
}

ArrayList_Sort.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList_Sort
unsorted: [Bさん, cさん, allen, 趙飛, _wtopia, Aさん]
sorted: [Aさん, Bさん, _wtopia, allen, cさん, 趙飛]

解説

上記のコードは, String 型の ArrayList をアルファベット順にソートするもので.

ArrayList には sort メソッドは実装されていないので, java.util.Collections クラスを使用してソートを行う. このクラスには, コレクション関連のメソッドがいくつも定義されている:

Collections.sort(myList);

とすることで, アルファベット順にデータがソートされる.

要素をソートする方法その 2

ここで String クラスに備わっている compareTo メソッドについて説明する:

public int compareTo(String anotherString)
この関数は二つの文字列を辞書式に比較する

辞書式とはどのような順番でしょうか? 次のようなコードを書いて, 確認してみる.

ComparableTest.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class ComparableTest{
    public static void main(String[] args){
	String ff = "BBB";

	String yy = "AAA";
	String gg = "BBB";
	String kk = "CCC";

	int x = ff.compareTo(yy); // ff と yy の関係
	int y = ff.compareTo(gg); // ff と gg の関係
	int z = ff.compareTo(kk); // ff と kk の関係

	System.out.println( "ff と yy の関係: " + x );
	System.out.println( "ff と gg の関係: " + y );
	System.out.println( "ff と kk の関係: " + z );
    }
}

ComparableTest.java の実行結果は:

[wtopia java.listsetmap]$ java ComparableTest
ff と yy の関係: 1
ff と gg の関係: 0
ff と kk の関係: -1

この実行結果から分かることは, compareTo メソッドは:

"BBB" <  "AAA" なら -1
"BBB" == "BBB" なら  0
"BBB" >  "CCC" なら  1

を返す.

このことから, 次の特性を揃えた int 型を返すことが分かる:

自分の Object <  比較する Object ならば  負の値
自分の Object == 比較する Object ならば  0
自分の Object >  比較する Object ならば  正の値

sort メソッドは, リストの配列がどのようにソートされるべきかを compareTo メソッドを使って決定している.

よって自作のクラス Member にも compareTo メソッドを作り:

自分 <  相手 ならば  負の値
自分 == 相手 ならば  0
自分 >  相手 ならば  正の値

という処理を実装しなければならない.

では, 具体的なプログラムを見ていこう.

Member2.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Member2 implements Comparable<Member2>{
    private String name; // Member2 の名前
    private int age; // Member2 の年齢

    public String getName(){
	return name;
    }

    public void setName(String name){
	this.name = name;
    }

    public int getAge(){
	return age;
    }

    public void setAge(){
	this.age = age;
    }

    public Member2(String name, int age){ // Constructor with TWO-parameters
	this.name = name;
	this.age = age;
    }

    // it must override compareTo method
    public int compareTo(Member2 obj){ // HAS-A Relation
	return this.getName().compareTo( obj.getName() );
    }
}

ArrayList_Sort2.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class ArrayList_Sort2{
    public static void main(String[] args){
	List<Member2> member = new ArrayList<Member2>();

	// Member の登録
	member.add( new Member2("Bさん", 28) );
	member.add( new Member2("Dさん", 8) );
	member.add( new Member2("Aさん", 2) );
	member.add( new Member2("Cさん", 1) );

	// Member2 で決めた方法でソートする
	Collections.sort(member);

	// 反復子を生成
	Iterator<Member2> i = member.iterator();
	while( i.hasNext() ){
	    Member2 m = i.next();
	    System.out.print( "Name: " + m.getName() );
	    System.out.println( ", Age: " + m.getAge() );
	}

    }
}

ArrayList_Sort2.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList_Sort2
Name: Aさん, Age: 2
Name: Bさん, Age: 28
Name: Cさん, Age: 1
Name: Dさん, Age: 8

解説

Member2 クラスでは:

public class Member2 implements Comparable<Member2> {}

を宣言すると, Comparable インタフェースを実装して, そして, compareTo メソッドを実装することで要素の比較を行うことができる.

今回は, 名前順にしたいので自分の名前と比較相手の名前を比べている.

なお, String 型同士を比較しているので, String の compareTo メソッドを呼び出している.

要素をソートする方法その 3

comparable インタフェースを実装した場合, ソート順序は 1 通りしか作成できない.

ここでは, ソート条件を複数選択できるような実装を考えていきたいと思う.

Collections に存在する sort メソッドを調べると, 次の2つがあることに気づく:

public static void sort(List list)
public static void sort(List list, Comparator c)

Member2.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Member2 implements Comparable<Member2>{
    private String name; // Member2 の名前
    private int age; // Member2 の年齢

    public String getName(){
	return name;
    }

    public void setName(String name){
	this.name = name;
    }

    public int getAge(){
	return age;
    }

    public void setAge(){
	this.age = age;
    }

    public Member2(String name, int age){ // Constructor with TWO-parameters
	this.name = name;
	this.age = age;
    }

    // it must override compareTo method
    public int compareTo(Member2 obj){ // HAS-A Relation
	return this.getName().compareTo( obj.getName() );
    }
}

ArrayList_Sort3.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

public class ArrayList_Sort3{
    public static void main(String[] args){
	List<Member2> member = new ArrayList<Member2>();

	// Member の登録
	member.add( new Member2("Bさん", 21) );
	member.add( new Member2("Dさん", 28) );
	member.add( new Member2("Aさん", 22) );
	member.add( new Member2("Eさん", 23) );
	member.add( new Member2("Cさん", 26) );

	// 昇順ソート
	Collections.sort( member, new NameSort() );
	// 反復子を生成
	Iterator<Member2> i = member.iterator();
	while( i.hasNext() ){
	    Member2 m = i.next();
	    System.out.print( "Name: " + m.getName() );
	    System.out.println( ", Age: " + m.getAge() );
	}

	System.out.println("--------------------");

	// 降順ソート
	Collections.sort(member, new NameReverseSort() );
	// 反復子を生成
	i = member.iterator();
	while ( i.hasNext() ){
	    Member2 m = i.next();
	    System.out.print( "Name: " + m.getName() );
	    System.out.println( ", Age: " + m.getAge() );
	}
    }
}

// 昇順にソートするクラス
class NameSort implements Comparator<Member2>{
    public int compare(Member2 o1, Member2 o2){
	return o1.getName().compareTo( o2.getName() );
    }
}

// 降順にソートするクラス
class NameReverseSort implements Comparator<Member2>{
    public int compare(Member2 o1, Member2 o2){
	return o1.getName().compareTo( o2.getName() ) * (-1);
    }
}

ArrayList_Sort3.java の実行結果は:

[wtopia java.listsetmap]$ java ArrayList_Sort3
Name: Aさん, Age: 22
Name: Bさん, Age: 21
Name: Cさん, Age: 26
Name: Dさん, Age: 28
Name: Eさん, Age: 23
--------------------
Name: Eさん, Age: 23
Name: Dさん, Age: 28
Name: Cさん, Age: 26
Name: Bさん, Age: 21
Name: Aさん, Age: 22

解説

sort メソッドの第 2 引数には, ソートの条件が定義されているクラスを渡している.

Comparator インタフェースは compare というメソッド 1 つしか持っていない. 使い方自体は Comparable インタフェースと非常によく似ている:

...
Collections.sort( member, new NameSort() )
...
Collections.sort( member, new NameReverseSort() )
...

降順にクラスでは, compareTo メソッドが返す結果にマイナスをかけ, 結果を反転させている.

このようにソートしたいインスタンスのクラスとは別のクラスを作成し, sort メソッドの第 2 引数に渡すクラスを変えることによって, 多数のソート順序を作成することができる.

並列処理に対応したリスト

この節では, 並列実装されたリストを紹介していく. ArrayList や LinkedList は, 複数のスレッドから同時にアクセス, 変更された場合, エラーが発生する.

ここではスレッドセーフ (同時にアクセスされてもエラーの発生しないよう) なリストの作り方について解説していく.

リストの間違った利用例

synchronizedList メソッドによるリストの同期

スローダウンとデッドロック問題

CopyOnWriteArrayList によるスローダウン回避

処理速度の検証

ArrayList と LinkedList における追加, 挿入の処理能力

get と Iterator の処理能力

CopyOnWriteArrayList の処理能力

検証に使用したソースコード